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