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

StackOverflow https://stackoverflow.com/questions/1808485

  •  05-07-2019
  •  | 
  •  

Вопрос

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

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

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 - нет, это легко показывает, что это ошибка, поскольку оно возвращает некоторое нецелое число.

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

Это было полезно?

Решение

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

Другие советы

Можно ли решить эту проблему с помощью обратного умножения?Первое, на что следует обратить внимание, это то, что 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.

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

  

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

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

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

Не надо.

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top