Arbitrary-Precision Arithmetic

Date: 08/08/2003 at 19:30:48
From: Kurt
Subject: Multiplying beyond floating point calculations

The programming language I use (QBasic V4.5) can display all digits 
of numbers up to 10^15. Suppose I wanted to multiply numbers that are 
greater than 10^15, say 8641578146853213165*998574385979598791785978. 
How could I use the programming language's math to compute that 
larger number in the quickest way, and yet display every single digit 
in the product?

The problem I would have is checking my answer, because I don't 
know of many ways I could actually multiply numbers that big.

I thought maybe I could divide each number into separate groups of 
seven digits because 9999999*9999999 would be the biggest possible 
multiplication of seven digits and it is small enough to work. Then 
maybe I could multiply each group of seven by all the other groups of 
sevens the way you do one digit at a time in pencil and paper 
multiplication. Would this work? Is there a faster or easier method? 

I just like to try difficult things like this for the fun of it. 
Thanks so much.

Date: 08/09/2003 at 22:26:28
From: Doctor Warren
Subject: Re: Multiplying beyond floating point calculations

Hi Kurt,

Thanks for writing to Dr. Math.

What you're looking to do is called "arbitrary-precision arithmetic." 
Using arbitrary-precision arithmetic, you can store and operate on
numbers as big as your computer's RAM, or, if you're really clever, as
big as your computer's RAM and hard disk space combined!

The simplest conceivable arbitrary-precision system would use an array
of bytes, and have each byte store one decimal digit.  To perform
arithmetic on these arrays of digits, you would just perform the
normal grade-school algorithms, adding digit-by-digit and keeping
track of the carries, subtracting digit-by-digit and keeping track of
the borrows, and so on.

This is a very naive approach, however, because it's obviously not
very efficient to use an entire byte to store a single decimal digit.
However, I recommend you start with this kind of program, because it's 
very easy to debug, and you'll get the hang of the methods involved.  
When you're ready, you can step up to more efficient approaches.

Arbitrary-precision arithmetic is nothing new. There are in fact many
many libraries on the Web that you can use in your programs. Some
programming languages (like Lisp and Java but not QBasic, I suppose) 
even have arbitrary-precision functions built into them. Here's a page 
full of arbitrary-precision libraries:

   List of Arbitrary Precision C packages - Mark Riordan
   http://www.csc.fi/math_topics/Mail/FAQ/msg00015.html 

It's not terribly up-to-date, but that's okay. The one I've used
personally is called "BigNum."  You can get a copy of it from:

   /afs/athena.mit.edu/contrib/bignum
   http://www.mit.edu/afs/athena.mit.edu/contrib/bignum/ 

It's in C though, so you might need to learn some things before you
can fully understand it. These libraries are also very much optimized
for the kind of operations done in cryptography (the technique of
encoding messages so that they can't be read by anyone but the
intended recipient), like exponentiation modulo some integer.

And just to make it easy for you to check your BIG results, here's a
calculator (written in Java) that runs in your Web browser.

   Arbitrary-precision Integer Calculators
   http://www.cis.ksu.edu/~howell/calculator/calc.html 

Let me know if you have any more questions.

- Doctor Warren, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 08/12/2003 at 23:18:34
From: Kurt Bachtold
Subject: Arbitrary precision division

How do you calculate one number divided by another number if the 
numbers are larger than what is allowed on the computer?

In QBasic, the programming language I use, I can divide any two 
numbers up to fifteen digits long. But suppose I want to divide a 
by b and a is 60 digits long, while b is 30 digits long. I figured I 
could divide each number into groups of 15 digits as follows:

a = jjjjjjjjjjjjjjjkkkkkkkkkkkkkkklllllllllllllllmmmmmmmmmmmmmmm
b = xxxxxxxxxxxxxxxyyyyyyyyyyyyyyy

The next step (I think) is to divide each fifteen-digit part in a by 
each fifteen-digit part in b and do something with the results, but I 
do not know what that something is. Please tell me how to go about 
doing this so I can continue my project on arbitrary precision math.

Thanks!

P.S. I just want to tell you that I love browsing through the 
questions and I am glad that you take the time to answer mine. I 
don't know what I would do without your help :).

Date: 08/13/2003 at 00:17:08
From: Doctor Warren
Subject: Re: Arbitrary precision division

Hi again Kurt,

I responded to your last question about how to do arbitrary-precision
arithmetic and I hope my reply helped you get started. Did you choose 
to represent your arbitrary-precision numbers as arrays of decimal 
digits as I suggested?

Performing division on arrays of decimal digits is very easy - it's
just grade-school long division, just as you remember doing in
elementary school. The reason this algorithm is useful to 
schoolchildren is that it breaks down a very large number into small 
pieces, each of which can be handled mentally. Your computer is going 
to have to do the same thing - it's going to have to break down a 
division of a really big number into pieces that can individually fit 
into its processor.

When you store your numbers as an array of decimal digits, you are
quite obviously working in decimal, base ten. You can also do long 
division in a different base, and the rules don't change at all. For 
example, here's a long division problem in hexadecimal:

       1149
     -------
 76 | 7F812
      76
      --
       98
       76
       --
       221
       1D8
       ---
        492
        426
        ---
         6C

Do this long division on your own if you need to prove to yourself it
works exactly the same as it does in decimal. You're going to program
your computer to do the exact same things that you do when you do the
division by hand - testing for the largest multiple of the divisor
(up to N-1), subtracting, and bringing down the next digit.

Now, here's the trick that will make this seem easy: there's no limit
to the arithmetic base we can use. In hexadecimal, each digit is
represented by exactly four bits. If you chose to implement your
arbitrary-precision system with four bit units, it would be rather
awkward, however - so how about a bigger base?

Your computer is very capable of dealing with 8-bit quantities 
(bytes).  An 8-bit number can range from 0 to 255. If you work with
8-bit quantities, you're effectively working in base 256. If you
store your arbitrary-precision numbers as arrays of 8-bit numbers,
you're essentially representing them as strings of base-256 digits.

Here's an example:

         bytes: 00100101 11010001 01010101
        digits:    (37)    (209)     (85)
  place values:   256^2    256^1    256^0

This three-byte number is composed of three base-256 "digits."  To
figure out what the whole number means, just as in any other base,
you multiply each digit by the value of its place. The digit (37) is
in the 256^2 place.  The total number is 37*256^2 + 209*256 + 85, or
2,478,421.

Now, as I said, there's no limit to what base you can do your
arithmetic in.  You can do long division on base-256 numbers exactly
the same way as you do it on base-10 numbers. So here's the algorithm
written up in pseudocode:

DIVIDE(a by b) {
   LET current_segment = most signifcant digit of a;
  
   WHILE there are digits left in a
      LET accumulator = 0;
      LOOP WITH i FROM 0 TO N-1
         LET previous_accumulator = accumulator;
         LET accumulator = accumulator + b;
         IF (accumulator > current_segment) {
            OUTPUT i;
            BREAK OUT OF LOOP;
         }
      END LOOP

      LET remainder = current_segment - previous_accumulator;
      LET current_segment = remainder followed by next digit of a;
   END WHILE
END DIVIDE

(Make sure that you completely understand this pseudocode algorithm
before you begin to code it in real code.  Test it out on a base-16
problem by hand!) 

Does this help?  Feel free to ask more questions!

- Doctor Warren, The Math Forum
  http://mathforum.org/dr.math/