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? :)
