Подразделение больших чисел
5 ответов
Самый простой способ, который я могу придумать, - это рассматривать 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-битные числа.
Надеюсь, это поможет.
/ AB
Вы не должны использовать long double для «нормального деления», но также и целые числа. 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/