Как число в 2^32 системе счисления спарсить в строку

#c_sharp

private uint[] Bits; //Массив в котором хранятся коэффициенты разложения числа в
обратном подядке
private int Sign; //Отвечает за знак числа
private int Length; //Длина массива
public const Int64 Base = (long)UInt32.MaxValue + 1; //Основание системы счисление 2^32

public BigInt(UInt64 value) //Один из конструкторов
    {
        Sign = 1;
        if (value <= Int32.MaxValue)
        {
            Bits = new uint[] { (uint)value };
            Length = 1;
        }
        else
        {
            Bits = new uint[2];
            Bits[0] = unchecked((uint)value);
            Bits[1] = (uint)(value >> 32);
            Length = 2;
        }
    }

public static BigInt Multiplication(BigInt x, BigInt y) //Сам алгоритм умножения
"в столбик"
    {
        uint[] result = new uint[x.Length + y.Length];
        ulong c = 0;
        for(int i = 0; i < y.Length; i++)
        {
            ulong d = 0;
            int j = 0;
            for(; j < x.Length; j++)
            {
                c = (d + ((ulong)x.Bits[j] * (ulong)y.Bits[i]) + result[i+j]) % Base;
                d = (d + ((ulong)x.Bits[j] * (ulong)y.Bits[i]) + result[i+j]) / Base;
                result[i + j] = (uint)c;
            }
            result[i + j] = (uint)d;
        }
        result = Normalize(result);
        return new BigInt(result, 1);
    }


При умножении 

BigInt test = new BigInt(UInt64.MaxValue);
test *= new BigInt(UInt64.MaxValue);


Я получаю BigInt, в котором массив Bits = {1, 0, 4294967294, 4294967295} то есть
в десятичной системе счисления 340282366920938463426481119288644075520. А как мне получить
это число из массива Bits?

То есть примерно что-то такое должно быть.

public string ToString(BigInt value)
    {
        string result = "";
        if (value.Sign == -1) result += "-";
        //Сам алгоритм
        return result;
    }

    

Ответы

Ответ 1

Код основан на моей имплементации BigInteger:
https://github.com/Zergatul/ZergatulLib/blob/master/Zergatul/Math/BigInteger.cs#L737

// деление числа в системе 2^32 на uint
// возвращает частное в системе 2^32
// его длину
// и остаток
private static (uint[], int, uint) DivideByUInt32(uint[] dividend, uint divisor)
{
    var quotient = new uint[dividend.Length];
    long remainder = 0;
    for (int i = quotient.Length - 1; i >= 0; i--)
    {
        remainder = (remainder << 32) | dividend[i];
        quotient[i] = (uint)(remainder / divisor);
        remainder = remainder % divisor;
    }
    int length = dividend.Length;
    while (length > 0 && quotient[length - 1] == 0)
        length--;
    return (quotient, length, (uint)remainder);
}

static void Main(string[] args)
{
    uint[] x = new uint[] { 1, 0, 4294967294, 4294967295 };

    // самое длинное число 10^RadixLength, которое помещается в uint
    const uint RadixUInt32 = 1000000000;
    const uint RadixLength = 9;

    int length = x.Length;

    var sb = new StringBuilder();
    while (length > 0) // пока длина частного > 0
    {
        uint remainder;
        // делим
        (x, length, remainder) = DivideByUInt32(x, RadixUInt32);
        // добавляем остаток в результат
        sb.Insert(0, remainder.ToString().PadLeft(RadixLength, '0'));
    }

    Console.WriteLine(sb.ToString());
}


Результат: 000000340282366920938463426481119284349108225

Код придется доделать, но основная идея должна быть понятна. Операции с целыми числами
сведены к минимуму, нужно оптимизировать работу с памятью (не использовать StringBuilder
с динамическим размером, не создавать массив каждый раз в методе DivideByUInt32).