Division of big numbers
biginteger, c++, division
Solution
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
And then do long division by 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)
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.
Problem
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 Basically, I store numbers as two `long long unsigned int`'s in the format `A * 2 ^ 64 + B` with `B < 2 ^ 64`. 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 ``` However, this is buggy. (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`. 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. 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?