Division of big numbers

Question

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?

Answer 1

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.