分数大

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

然而,这是错误的.

(需要注意的是地板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位数字,所以这应该仅适用于整数运算.