Re: [boost] Interest in an arbitrary precision library?

From: Andras Erdei (aerdei_at_[hidden])
Date: 2005-09-06 02:55:58

On 9/2/05, Joel Eidsath <jeidsath_at_[hidden]> 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