大数的分 [英] Division of big numbers

问题描述

我需要一些可以处理大整数（128位）的除法算法。
我已经问过如何通过位移操作符。但是，我当前的实现似乎要求更好的方法

I need some division algorithm which can handle big integers (128-bit). I've already asked how to do it via bit shifting operators. However, my current implementation seems to ask for a better approach

基本上，我存储数字为两个 long long unsigned int 的格式

Basically, I store numbers as two long long unsigned int's in the format

A * 2 ^ 64 + B 与 B ; 2 ^ 64 。

此数字可由 24 整除

This number is divisible by 24 and I want to divide it by 24.

我目前的方法是将它转换为

My current approach is to transform it like

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 。

(Note that floor is A / 24 and that mod is A % 24. The normal divisions are stored in long double, the integers are stored in long long unsigned int.

c $ c> 24 在二进制中等于 11000 ，第二个被加数应该不会改变第四个被加数的范围内的某些东西，因为它是

Since 24 is equal to 11000 in binary, the second summand shouldn't change something in the range of the fourth summand since it is shifted 64 bits to the left.

因此，如果 A * 2 ^ 64 + B 可被24整除，

So, if A * 2 ^ 64 + B is divisible by 24, and B is not, it shows easily that it bugs since it returns some non-integral number.

我的实现中的错误是什么？

What is the error in my implementation?

推荐答案

我想到的最简单的方法是将128位数字视为四个32位数字：

The easiest way I can think of to do this is to treat the 128-bit numbers as four 32-bit numbers:

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位数字的除法，所以这应该只能用整数操作。

Where X_Y means X*2^32 + Y. Then the answer is E_F_G_H with remainder T. At any point you only need division of 64-bit numbers, so this should be doable with integer operations only.

这篇关于大数的分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！