Large Integer Computing - Introduction to Cryptography with Java Applets - page 63

Multiplication and division in binary is particularly easy and fast to implement,
since it involves mostly just shifting to the right or left, and adding. For example, to mul-
tiply 5 by 9 we take

00000101
00001001

Which we note is simply 00000101 base 2 plus 00101000 base 2 (which is 00000101 base 2
shifted to the left 3 places). This gives us 00101101 base 2 , or 45 in decimal, which is
correct.
Now, with all of this in mind, rewrite the Int class.

4. If you prefer using base 10 for the Int() class (it ' s much easier to convert these to and

from strings, for example), you may consider using base 1 billion. A number in this
base can be written as

a n · 1000000000 n + a n- 1 · 1000000000 n- 1 + . . . + a 1 · 1000000000 1 + a 0 · 1000000000 0 .

where each a i is an integer between 0 and 999999999.
The array (or list) of ints which hold the “ digits ” can store a number in this range.
The size of this data structure will clearly be much smaller. Conversion between base
1 billion and base 10 is easy because 1 billion = 10 9 . You may also consider using an
array (or list) of type long, using as your base the maximum power of 10 which does
not exceed the maximum positive long value 2 63

1.