Как эмулировать 256-битные целочисленные математические операции в системе с 32-битным int

Question

Я хотел бы написать класс deadsimple bignum, используя серию (беззнаковых) целых чисел.Я свободно вижу, как будут работать сложение и вычитание, но деление и умножение - это другая история.Я знаю, что 32-битные компиляторы могут эмулировать 64-битные int, разделяя int64 на два int32.Я ищу эффективный метод для этого.

Я хотел бы иметь C ++ код, а не сборку.Скорость не имеет первостепенного значения, но всегда приятно иметь самое эффективное решение без сборки.

Answer 1

Возможно, , этот может служить отправной точкой.Он реализует до 2048-разрядных целых чисел без знака, используя представление base-65,536.Это означает, что каждая цифра умещается в 16 бит, и мы можем тривиально обнаружить переполнение (даже при умножении), просто используя 32 бита для результатов.

Однако это код на C, но он должен быть тривиальным для переноса на C ++или просто использовать как вдохновение.Он очень оптимизирован для удобства чтения, а не для скорости, так как это не совсем то, что я умею делать.:)

Answer 2

Лучше всего взгляните на арифметику произвольной точности , которая объяснит, что стоит за процессом эмуляции процессоров с более высокой точностью, чем тот, на котором работает ваш код.

Answer 3

Купите книгу в твердом переплете под названием ЧИСЛЕННЫЕ РЕЦЕПТЫ В C ++, и вы найдете то, что ищете, на страницах, начиная с 20,6 стр. С916 по стр. 925

Answer 4

для произвольных размеров, дайте GMP вращение, оно также должно работать для вашей 64-битной математики на 32-битной, если по какой-то причине вы не можете полагаться на компилятор, который сделает это за вас.

Answer 5

Использовать простой байтовый массив. Вы можете иметь любой размер целого числа *. Вам просто нужно работать в двоичном формате и учитывать порядковые номера (ваши биты будут 7-6-5-4-3-2-1-0-15-14-13 ...)

* ОЗУ ограничено

Answer 6

Что не так с использованием long long? Это гарантированно будет в минимум 64 бита. В противном случае ваш Кнут (т. 2) должен предоставить основные алгоритмы.