Re: [boost] Interest in an arbitrary precision library?

From: Joel Eidsath (jeidsath_at_[hidden])
Date: 2005-09-07 09:07:12

Paul A Bristow wrote:

>We definitely need a big int and an arbitrary precision in Boost, but I am
>unclear how to proceed (and I am not volunteering ;-).
>  
>

Well here is how I'm starting off with the big integer side of things:

I am implementing most of the interface of N1744:  
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1744.pdf

What I am saving for last or never is the bitshift operators.

Multiplication will use a Fast Fourier Transform, so it should equal GMP 
multiplication with large enough numbers.  Knuth claims that this 
method, Schonhage-Strassen is O(n) for practical purposes.

The division algorithm uses the multiplication algorithm, and presents a 
complexity of that times a constant.

Evaluation of powers will use a binary algorithm from Knuth.

GCD will use the binary gcd algorithm.

That's pretty much what I've got so far.

On the non-integer side of things, I have not spent much time looking 
for algorithms yet, but I'll probably get most of them from Knuth.

A number of these algorithms can be improved on for special cases.  
That's too much work for one person though, so I'll just concentrate on 
getting a library out that can be tweaked later, once it's working.

Joel Eidsath