writes:

Quote:

>I'm looking for fast algorithms how to implement binary n-bit integer

>operations based on m-bit operations (typically n > m, m = 32) used for

>unlimited-size integer arithmetics.

Have a look in Knuth, Fundamental Algorithms vol 2: Semi Numerical

Algorithms. See also Lipson, Elements of algebra and algebraic computing.

There are three I can think of off hand:

FFT (many variants, Pollard, Schonhage-Strassen, etc..)

Fast convolution

Residue arithmetic.

All just a tad worse than n log n.

Also, at n^(log2 3), about n^1.6, is karatsuba's (???) method -

reduces one multipication of 2 n-bit numbers to 3 multiplciations

of n/2 bits numbers recursviely (plus the odd add & shift).

Write a * b as (a1 * 2^k + a2) * (b1 * 2^k + b2) & rearrange

it to get ... exercise for the reader.

HTH Al.