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

  Alan MacDonald  writes and asks:

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
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.



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  
 
 [ 5 post ] 

 Relevant Pages 

1. integer arithmetic

2. floating point or integer arithmetic?

3. mp (Multiple Precision Integer Arithmetic Package)

4. Wanted: arbitrary precision integer arithmetic

5. 64bit Integer Arithmetic

6. Huge integer arithmetic.

7. large integer arithmetic

8. Big integer arithmetic

9. Need C sources for 64-bit integer arithmetic

10. 64 bit integer arithmetic with two 32 bit integers?

11. 64 bit integer arithmetic with two 32 bit integers?

12. Floating point arithmetic using integers

 

 
Powered by phpBB® Forum Software