Деление больших чисел

Мне нужен алгоритм деления, который может обрабатывать большие целые числа (128 бит). Я уже спрашивал, как это сделать с помощью операторов битового сдвига. Однако моя текущая реализация, похоже, требует лучшего подхода.

По сути, я храню числа как две long long unsigned int в формате

A * 2 ^ 64 + B с B < 2 ^ 64.

Это число делится на 24, и я хочу разделить его на 24.

Мой текущий подход состоит в том, чтобы преобразовать его как

A * 2 ^ 64 + B     A             B
--------------  = ---- * 2^64 + ----
      24           24            24

           A               A mod 24                    B         B mod 24
= floor( ---- ) * 2^64 +  ---------- * 2^64 + floor( ---- ) +   ----------
           24               24.0                      24           24.0

Однако это глючит.

(Обратите внимание, что этаж — это A / 24, а mod — это A % 24. Обычные деления хранятся в long double, а целые — в long long unsigned int.

Поскольку 24 равно 11000 в двоичном виде, второе слагаемое не должно ничего менять в диапазоне четвертого слагаемого, поскольку оно сдвинуто на 64 бита влево.

Таким образом, если A * 2 ^ 64 + B делится на 24, а B нет, это легко показывает, что оно содержит ошибку, поскольку возвращает какое-то нецелое число.

В чем ошибка в моей реализации?


c++ division biginteger
person Etan    schedule 27.11.2009    source источник
comment
В чем проблема с подходом с битовым сдвигом?   -  person Andreas Brinck    schedule 27.11.2009
comment
это кажется излишним, когда вы уже можете разделить int64   -  person Etan    schedule 27.11.2009

Ответы (5)


arrow_upward
13
arrow_downward

Самый простой способ, который я могу придумать, - это рассматривать 128-битные числа как четыре 32-битных числа:

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

А затем выполните длинное деление на 24:

E = A/24 (with remainder Q)
F = Q_B/24 (with remainder R)
G = R_C/24 (with remainder S)
H = S_D/24 (with remainder T)

Где X_Y означает X*2^32 + Y. Тогда ответ E_F_G_H с остатком T. В любой момент вам нужно только деление 64-битных чисел, поэтому это должно быть выполнимо только с целочисленными операциями.

person interjay    schedule 27.11.2009
comment
Это не мешает вашему алгоритму работать вообще, но F, G и H могут быть больше 2^32. Мне было трудно согласовать это с тем фактом, что нотация E_F_G_H выглядит как конкатенация, но как только это понято, это очень хороший алгоритм. - person Pascal Cuoq; 27.11.2009
comment
На самом деле F,G и H будут меньше 2^32, потому что Q, R и S меньше 24. Таким образом, нотация E_F_G_H является конкатенацией. - person interjay; 27.11.2009
comment
Верно! Я забыл свое деление карандашом и бумагой ... Я вспомнил, что была неприятная часть угадывания, но это когда делитель имеет слишком много цифр. Пока сам делитель достаточно короток, чтобы попасть в диапазон, для которого работает примитивное деление (как в данном случае), никогда не нужно угадывать при применении алгоритма деления карандашом и бумагой. Извините за путаницу. - person Pascal Cuoq; 27.11.2009

arrow_upward
2
arrow_downward

Можно ли это решить обратным умножением? Первое, что нужно отметить, это то, что 24 == 8 * 3 поэтому результат

a / 24 == (a >> 3) / 3

Пусть x = (a >> 3), тогда результат деления равен 8 * (x / 3). Теперь осталось найти значение x / 3.

Модульная арифметика утверждает, что существует число n такое, что n * 3 == 1 (mod 2^128). Это дает:

x / 3 = (x * n) / (n * 3) = x * n

Осталось найти константу n. Объяснение того, как это сделать, есть в Википедии. Вам также придется реализовать функциональность для умножения на 128-битные числа.

Надеюсь это поможет.

/A.B.

person Andreas Brinck    schedule 27.11.2009

arrow_upward
1
arrow_downward

Вы не должны использовать long double для своих «обычных делений», но также и целые числа. long double не имеет достаточного количества значащих цифр, чтобы получить правильный ответ (и в любом случае весь смысл в том, чтобы сделать это с целочисленными операциями, верно?).

person Andrew Jaffe    schedule 27.11.2009
comment
весь смысл в том, чтобы просто разделить 128-битное целое число на 24, что на данный момент приводит к эпическому провалу. Long double имеет 64-битную мантиссу, так что это не должно создавать проблем. или это так? - person Etan; 27.11.2009
comment
Итан должен был сделать ссылку на их первоначальный вопрос. Кажется, что цель состоит не в том, чтобы сделать это с целыми числами, а в том, чтобы сделать это вообще. Кроме того, long double может быть таким же маленьким, как 64-битный двойник, но также может быть и больше (скажем, 10-байтовый расширенный двойник, но на самом деле вообще что угодно... IEEE 754 в основном параметричен в отношении битовых размеров). Следовательно, он может иметь необходимую точность (я не говорю, что использование вычислений с плавающей запятой для чего-то столь же простого, как 128-битная целочисленная арифметика, является хорошей идеей). - person Pascal Cuoq; 27.11.2009
comment
Как разделить его без длинного двойника? - person Etan; 27.11.2009
comment
@ Андрей Ты имеешь в виду assert (sizeof(long long int) >= 16); d = a/24; :) - person Pascal Cuoq; 27.11.2009

arrow_upward
1
arrow_downward

Так как 24 равно 11000 в двоичном формате, второе слагаемое не должно ничего менять в диапазоне четвертого слагаемого, так как оно сдвинуто на 64 бита влево.

Ваша формула написана действительными числами. (Мод 24) / 24 может иметь произвольное количество десятичных знаков (1/24, например, 0,041666666...) и, следовательно, может мешать четвертому члену в вашем разложении, даже если его умножить на 2 ^ 64.

Свойство Y * 2 ^ 64 не мешает двоичным цифрам с меньшим весом в сложении, работает только тогда, когда Y является целым числом.

person Pascal Cuoq    schedule 27.11.2009
comment
Это мешает десятичным дробям, поскольку вы не можете записать их точно там. В двоичном формате он имеет ограниченную реализацию, поскольку 1/24 можно записать в виде конечного количества цифр. - person Etan; 27.11.2009
comment
@Итан Правда? Сколько цифр нужно, чтобы точно представить 1/24 в двоичном виде? (Если это слишком сложный вопрос, начните с количества двоичных цифр, необходимых для точного представления 1/3) - person Pascal Cuoq; 27.11.2009
comment
1/24 = двоичное число 0,00001010101010101... последовательность продолжается вечно. - person dave4420; 27.11.2009
comment
Блин ^^ Вы правы. Итак, идея кажется правильной, и к результату нужно просто добавить сумму обоих модулей? - person Etan; 27.11.2009
comment
Я лишь способствовал отладке вашего мыслительного процесса. Я думаю, что писать формулу, которая верна только для вещественных чисел, а затем аппроксимировать эти вещественные числа числами с плавающей запятой (даже длинными удвоениями) — плохая идея. В нем будут ужасные ошибки, которые возникают только при делении больших чисел (и только некоторых из них). - person Pascal Cuoq; 27.11.2009

arrow_upward
1
arrow_downward

Не надо.

Возьмите библиотеку, чтобы сделать это — вы будете невероятно благодарны, что выбрали ее при отладке странных ошибок.

Некоторое время назад на сайте Snippets.org была библиотека C/C++ BigInt, Google также обнаружил следующее: http://mattmccutchen.net/bigint/

person Adam Frisby    schedule 27.11.2009
comment
Я должен сделать это вручную, так как это связано с проблемой ACM ICPC. - person Etan; 27.11.2009