Boost logo

Boost :

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.

Joel Eidsath

Boost list run by bdawes at, gregod at, cpdaniel at, john at