Hipo wrote:

Hi.

My problem seems to be simple, but I can not figure out a solution.

Problem: I have a number that consists of 128 bit. I want to compute its

modulo (modulo is at the range < 2^16). So that there is no 128 bit

datatype in C++ I just cannot imagine how I can work out qa solution for

that.

Long division!

Suppose you only have 32 bit numbers to work with, and your machine is

capable of dividing a 64 bit number by a 32 bit number to yield 32 bit

remainder and quotient. What you can do is pretend that the 128 number

is four digit number in base 4-billion-something, each digit being 32

bits wide.

It's convenient to use hexadecimal for this. For instance consider this

128 bit number as your n:

1ADFCBE3 391AF76B 1FFC0104 EDA9F034

I wrote it as four groups of 32 bits. You can think of these as four

huge digits in a large base, base 2^32. I.e. the number can be written

as the sum of these four numbers

1ADFCBE3 00000000 00000000 00000000

391AF76B 00000000 00000000

1FFC0104 00000000

EDA9F034

Suppose we give the symbolic names A, B, C and D to those four 32 bit

digits. This number n then takes the form A * 2^96 + B * 2^64 + C *

2^32 + D.

We can then just hide all that and write the number in a condensed way

as

A B C D // A B C D are 32 bit chunks

So now you can do long division by M (using 32 bit digits!!!) and find

the remainder:

________

M | A B C D

First find how many times M goes into A, blah blah blah. You know the

routine from grade school, except that the digits go from 0 to 4.7

billion instead of 0 to 9 and the machine does the work.

Let's work through it, using 7D0 hex (2000 decimal) as M.

______________________________________

7D0 |1ADFCBE3 391AF76B 1FFC0104 EDA9F034

How many times does 7D0 go into A? Or rather into 1ADFCBE3? Of

course, we make the computer divide them. And it knows how to do that

because we are dealing only with 32 bit quantities. The answer is

3709D, with a remainder of 153 (all hex). So let's write that in:

____3709D________________________________

7D0 |1ADFCBE3 391AF76B 1FFC0104 EDA9F034

153

So now we combine the 153 remainder with the next 32-bit-digit to make

153391AF76B. We now do 64/32 division to get the next quotient and

remainder, which are 2B6BA956 and 78B, respectively. Put 'em in:

____3709D_2B6BA956_______________________

7D0 |1ADFCBE3 391AF76B 1FFC0104 EDA9F034

153 391AF76B

78B

Hoo wee, this is getting exciting: the number is emerging. We "bring

down" the 1FFC0104, combine it with the remainder to get 78B1FFC0104,

and keep going:

____3709D_2B6BA956_F72F1A1C______________

7D0 |1ADFCBE3 391AF76B 1FFC0104 EDA9F034

153 391AF76B

78B 1FFC0104

644

We are only seconds away from the final answer. Drum roll! Bring it

down, another 64-32 division and remainder and ...

____3709D_2B6BA956_F72F1A1C_CD6E4B00_____

7D0 |1ADFCBE3 391AF76B 1FFC0104 EDA9F034

153 391AF76B

78B 1FFC0104

644 EDA9F034

34

Tada, the remainder is 34, and the quotient is

3709D2B6BA956F72F1A1CCD6E4B00.

If you have a 64 bit type available as an extension in your C++

compiler (the C language has a 64 bit type as of 1999) you can do it

like this. Or you can stick with 32 bit types; the number is broken

into eight 16 bit groups instead.

If you're not interested in the quotient, you just throw it away,

because all you need is the remainder from each division to feed into

the next one.

The most productive solution, however, is to get a bignum library. But

then you would never learn how it's done, right? :)