6
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;
    }
8
  • перевести его в десятичную системы счисления - и затем вывести
    – Grundy
    25 июл 2019 в 16:34
  • а мне кажется или был вопрос про умножение? он решился?
    – Grundy
    25 июл 2019 в 16:35
  • Про умножение был недавно, но глупый я его удалил. А про вывод не было. Не подскажите как в десятичную перевести, а потом вывести? 25 июл 2019 в 16:40
  • @Grundy если вы точно уверены, что ваше предложение верно можете пожалуйста написать реализацию идеи вашей в виде ответа. И протестировать его с массивом Bits = {1, 0, 4294967294, 4294967295} 25 июл 2019 в 16:57
  • алгоритм перевода можешь взять из предыдущего вопроса, единственное отличие основание системы должно стать 10 или степень 10, а умножаться вместо 10 на 2^32 :)
    – Grundy
    25 июл 2019 в 17:13

1 ответ 1

3

Код основан на моей имплементации 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).

6
  • Спасибо за ответ! Жалко только я не понимаю что происходит, но надеюсь когда поднакоплю знаний разберусь. А так я сам уже решил проблему не факт что эффективным по скорости алгоритмом, но достаточно простым для понимая. 25 июл 2019 в 21:03
  • @ПавелЕриков тут всё просто. Вот смотрите, когда вы делаете обычным способом - вы делите на 10 и смотрите остаток. И получаете одну цифру. Вы можете делить сразу на 100, и получить 2 цифры. Для процессора нет разницы, делить на 10 или 100, это занимает одно и тоже время. В моем коде я делю сразу на 1 миллиард и получаю по 9 цифр за 1 раз.
    – Zergatul
    25 июл 2019 в 21:27
  • Да не этот момент мне понятен. Мне не понятна реализация метода DivideByUInt32. 25 июл 2019 в 22:34
  • 1
    @Павел Ериков При школьном делении столбиком на каждом шаге у вас остаётся остаток (remainder), к которому приписывается очередная цифра из делимого. Это соответствует сдвигу в старший десятичный разряд и добавлению новой цифры в младший. То же самое и здесь.
    – MBo
    26 июл 2019 в 5:43
  • А вот эту строчку можете пожалуйста объяснить? remainder = (remainder << 32) | dividend[i]; 26 июл 2019 в 12:46

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.