Деление больших чисел
-
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/