
Boost : 
From: Joel Eidsath (jeidsath_at_[hidden])
Date: 20050907 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.openstd.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, SchonhageStrassen 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 noninteger 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk