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:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk