Re: big number arithmetic

[email protected] wrote:
> Dear list members,
> 
> i am trying to imlement multiplication function for two 64 bit number.
> I wondered which would it be the best possible algorithm for such a
> feat? May someone suggest one?
> After have implemented, what about make it generic, i.e., for n bits?

What kind of cpu are you working on?

Do you need a 128-bit full product, or just the low half?

The latter is easy, since any conforming C(++) compiler has to support 
t_uint64 and t_int64 these days.

If your building blocks are shorter multiplies, maybe 32x32->64, then 
you can combine those to generate the full product you need.

Assuming you have a cpu with no multiplication support at all, then you 
need to do some more work:

Either a full 64-iteration loop using shift & add, or you can construct 
a small multiplier using lookup tables:

  (a+b)^2 = a^2 + 2ab + b^2
  (a-b)^2 = a^2 - 2ab + b^2

so (a+b)^2 - (a-b)^2 = 4ab.

With a lookup table of the first 2N squares, you can use this to 
multiply 2 N-bit numbers!

unsigned mul8x8(unsigned a, unsigned b)
{
   static unsigned square[512] = {0,1,4,9,16,25,36,49....};
   if (a < b) { unsigned t = a; a = b; b = t};
   unsigned prod = (square[a+b] - square[a-b]) >> 2;
   return prod;
}

If we note that the sum and difference of two even numbers will both be 
even, the sum/diff of an odd and an even number will both be odd, and 
the square of an odd number is odd, then we realize that the table can 
store the truncated half of each square, it will still come out correct, 
and we'll only need a single shift at the end.

Terje

-- 
- <[email protected]>
"almost all programming can be viewed as an exercise in caching"