Отдел больших чисел

Question

Мне нужен алгоритм деления, который может обрабатывать большие целые числа (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

Однако это ошибка.

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

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

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

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

Answer 1

Самый простой способ сделать это - обработать 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-битных чисел, так что это должно выполняться только с целочисленными операциями.

Answer 2

Может ли это быть решено с помощью обратного умножения? Первое, что нужно отметить, это то, что 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. Есть объяснение, как это сделать в wikipedia . Вам также придется реализовать функциональность для умножения на 128-битные числа.

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

/ * 1022 A.B. *

Answer 3

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

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

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

Answer 4

Не.

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

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

Answer 5

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