On 9/2/05, Joel Eidsath <jeidsath@gmail.com> wrote:
I've used several different arbitrary precision libraries with C++ and I have always been somewhat disappointed. And now I'm finally disappointed enough to start on my own.
i, too, have started to implement my own, for different reasons (i'm interested in the rational library, but my impression was that to get changes through, we have to have an unlimited precision integer library first)
3) As well as arbitrary precision, it should provide error range math: 2.00 * 2.00 is not generally the same thing as 2.0 * 2.0
if i understood your later comments regarding this issue correctly, this would lock the implementation to a decimal-based radix one (otherwise you can't specify the precision as the number of decimal digits) which seems to be a very severe limitation the most obvious choice for a 32 bit machine is a 2^31-based radix representation and to my understanding your precision requirements rule that out
4) It should use fast algorithms for multiplication and division, but instead of trying to compete with other libraries in computation speed (GMP uses hand-coded assembly in places), it should concentrate on code portability and ease of extension.
my secret hope is that using expression templates GMP and its ilk can be beaten :O) if you want to calculate a+b+c using a C library, you have to make two loops over the digits (e.g. to add a and b, and then to add c to the result), while in C++ you can add together all three in a single loop (iirc GMP does have a few hacks built in for fast computation of frequently appearing cases like x*x+y*y and a+b+c but even if memory serves me right, it is just a few special cases, not a general solution) if GMP really cannot be beaten, then we have to have a wrapper around it for those who need the efficiency and don't care about the licensing
5) I do not envision any fancy memory management. The "big int" class will probably use a std::vector<int> to store it's implementation data.
i do not yet have benchmarks (partly because do not know what to benchmark -- if someone would be willing to develop some benchmarks derived from real-life applications, it would be very helpful), but i suspect that memory management will be an important factor in the speed of the end result currently i have three methods in use: - linked list of single digits (std::list) - a continuos storage for all digits (std::vector) - a linked list of ever-growing slices of digits (atm i have two versions, one has nodes with 1,2,4,8,...2^n digits, and the other with 1,2,3,5,8...F(n) digits) br, andras