integer arithmetic
Author Message
integer arithmetic

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.

any help is greatly appreciated,

putt

--
------------------------------------------------------------------------

Sat, 08 Jan 2000 03:00:00 GMT
integer arithmetic

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.

Sounds like "multiple precision arithmetic".  It's somewhere in Knuth,
probably Vol. 1 (fundamental algorithms).

Mon, 10 Jan 2000 03:00:00 GMT
integer arithmetic

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

operations based on m-bit operations

Quote:
> (typically n > m, m = 32) used for
> unlimited-size integer arithmetics.

If you know any engineers, get them to decribe how a look ahead carry chip
works.  If you can muddle thorugh logic drawings on your own, you might be
able to figure it out from a clatalog from someone such as Motorola.

Tue, 11 Jan 2000 03:00:00 GMT
integer arithmetic

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

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.

Tue, 11 Jan 2000 03:00:00 GMT
integer arithmetic

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.

> any help is greatly appreciated,

If what you really want is code that you can run, you could try the
GNU multiple precision package. For popular CPUs, many of the lower
level routines have been written in assembly language (but portable C
versions exist too.)  The documentation concentrates on how to use the
library rather than on how the algorithms work.

See:  ftp://prep.ai.mit.edu/pub/gnu/gmp-2.0.2.tar.gz

Thu, 13 Jan 2000 03:00:00 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages