From: Ray Cromwell <rjc@clark.net>
Date: Thu, 31 Aug 95 20:28:32 PDT
To: scmayo@rschp1.anu.edu.au (Sherry Mayo)
Subject: Re: sums with BIG numbers
In-Reply-To: <9509010227.AA28294@toad.com>
Message-ID: <199509010327.XAA25211@clark.net>
MIME-Version: 1.0
Content-Type: text/plain


> 
> Can anyone point me to any books, documentation or
> whatever that will explain the methods used in routines
> like bignum for doing sums with 'too-big' numbers.


Try Knuth's The Art of Computer Programming, Volume 2, Seminumerical 
Algorithms.

Most bignum routines work like this. An integer is represented
as a polynomial p(x) with coefficients a_0, a_1, ..., a_n, where
x is the radix or "base" of the number. The coefficients come from
the ring of integers, modulo the base. For instance, if you are
using base-2 (x=2), the number 28 could be represented as
p(x) = a_4 x^4 + a_3 + x^3 + a_2 x^2 + a_1 x + a_0 

where a_4=a_3=a_2=1 and a_1=a_0=0.  Each a_n is an element of Z mod x

To add two bignums, P(x) and Q(x) simply sum coefficients of like
terms like you would with any polynomial addition, with one simple
modification. If a_k is the coefficient of the x^k term of P(x), and
b_k is the coefficient of the x^k term of Q(x), then the
x^k term of P(x)+Q(x) is a_k+b_k+(carry of previous term) mod x.
(new carry=(a_k+b_k + previous carry)/x)
All this says is, the new term is the sum of the coefficients 
on the x^k terms, modulo x (because your coefficients can not hold
numbers larger than 'x'), plus the carry of the last term. The
carry is 1 if a_k+b_k+previous_carry > x. 

Now you may ask, if our coefficients in our bignum are stored as
32-bit integers, how do I compute the result in C and take into
account overflow?

Well, add the two numbers together. If the result is less than either
of the numbers, an overflow has occured and you must carry (the
machine register has 'rolled over'). For multiplication, you can
either break a 32-bit number into 2 16-bit chunks and perform 4 16-bit
multiplies to get a 64-bit result (using 16x16->32 bit hardware
multiplication) or you can use a number of type "long long int" in C
and let the compiler do it for you.


A short example: let X=123 and Y=789 be bignums represented via the
polynomials P(x)=1 x^2 + 2 x + 3 and Q(x)=7 x^2 + 8 x + 9  with
x=10. let r_n be the coefficients of the resultant polynomial 
R(x)=P(x)+Q(x)

Start at the least significant term. Carry=0
Now r_0=(a_0 + b_0)+carry mod x, or r_0=9+3 mod 10=2, carry=(9+3)/10=1
    r_1=8 + 2 + carry = 11 mod 10 = 1    carry=11/10 = 1 
    r_2=1+7 + carry = 9  carry = 9 / 10 = 0
    
So the result is 912.
  
Explicit modulos are only required if you are working in some base
other then the machine's natural word size. (otherwise the
'roll over' effect gives you the mod for free)

If you are seeking the fastest practical methods of doing multiplication,
division, and modular exponentiation, look up information on 
Karatsuba multiplication, fast reciprocals via Newton's Method,
and Fast Integer Squaring combined with exponent shifting.
(if you are looking at PGP's source code, PGP does not use the
fastest algorithms)

-Ray