By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,551 Members | 2,622 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,551 IT Pros & Developers. It's quick & easy.

Understanding problem of long numbers

P: n/a
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.

greets, Hipo
Jun 15 '06 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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.


Basically you need to do a division with remainder. Think about how you
do division with pencil and paper and try to apply this to the problem.
You would need to represent your 128 bit quantity as several smaller
integers that are representable in C++.

Jun 15 '06 #2

P: n/a

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.

greets, Hipo


Surely there's a big number library that does this? Maybe something
like: http://indigo.ie/~mscott/

I've not used the library, but there's plenty of others around too.

Jun 15 '06 #3

P: n/a
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? :)

Jun 15 '06 #4

P: n/a
Great thanks. That helps me a lot.

greets, Hipo
Jun 16 '06 #5

This discussion thread is closed

Replies have been disabled for this discussion.