Large number separation

Question

I need a division algorithm that can handle large integers (128 bits). I already asked how to do this using bit shift operators. However, my current implementation seems to require a better approach.

Basically, I save the numbers as two long long unsigned int in the format

A * 2 ^ 64 + B with B < 2 ^ 64 .

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

My current approach is to convert it like

 A * 2 ^ 64 + BAB -------------- = ---- * 2^64 + ---- 24 24 24 AA mod 24 BB mod 24 = floor( ---- ) * 2^64 + ---------- * 2^64 + floor( ---- ) + ---------- 24 24.0 24 24.0 

However, this is a mistake.

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

Since 24 is equal to the binary value of 11000 , the second term should not change anything in the range of the fourth term, since it is shifted 64 bits to the left.

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

What is the error in my implementation?

Answer 1

The easiest way to do this is to treat 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 a 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 the remainder T At any moment you only need to divide 64-bit numbers, so this should only be done with whole operations.

Answer 2

Not.

Go take a library to do this - you will be incredibly grateful for choosing strange errors when debugging.

Snippets.org had some BigInt C / C ++ library on this site, Google also found the following: http://mattmccutchen.net/bigint/

Answer 3

Can this be solved using inverse multiplication? The first thing to note is 24 == 8 * 3 , so the result

 a / 24 == (a >> 3) / 3 

Let x = (a >> 3) , then the result of division is 8 * (x / 3) . Now it remains to find the value x / 3 .

Modular arithmetic claims that there is a number n such that n * 3 == 1 (mod 2^128) . This gives:

 x / 3 = (x * n) / (n * 3) = x * n 

It remains to find the constant n . It explains how to do this on wikipedia . You will also have to implement the functionality for multiplying by 128-bit numbers.

Hope this helps.

/ AB

Answer 4

You should not use long double for your "normal divisions", but integers. long double does not have enough significant digits for the correct answer (and in any case, the whole point is to do this with the help of whole operations, right?).

Answer 5

Since 24 is equal to the binary number 11000, the second term should not change anything in the range of the fourth term, since it is shifted 64 bits to the left.

Your formula is written in real numbers. (A mod 24) / 24 can have an arbitrary number of decimal places (1/24, for example, 0.041666666 ...), and therefore it can interfere with the fourth term in your expansion, even once multiplied by 2 ^ 64.

The property that Y * 2 ^ 64 does not interfere with the least significant binary digits in the complement works only when Y is an integer.