Decimal arithmetic

[Paul Zimmermann]

> I've been asked off-list by a former member about digit extraction  
> functions in GMP. I've given the usual lecture about how digit  
> extraction is a slow operation if the library does binary arithmetic,  
> since it requires a base-2 to base-10 conversion. With that said, a  
> base-10 library would provide efficient digit extraction while not  
> sacrificing much performance.
>
> So what are the choices of libraries that support base-10 arithmetic?  
> Can GMP itself be easily modified to support it? As far as I know, Pi- 
> calculating programs such as QuickPi and PiFast do the arithmetic in  
> decimal since the result will be eventually printed out (in decimal,  
> of course). But these programs are generally closed-source, and even  
> if they weren't, I assume they wouldn't provide a proper library  
> interface.

Base-2 to base-10 conversion costs O(M(n) log(n)) for n-bits numbers,
where M(n) denotes the multiplication cost. There is indeed a log(n)
overhead, but most computations are much more expensive. If you implement
arithmetic in radix 10, you will loose a constant factor on your ***whole***
computation, which will kill the small speedup on the base conversion.
Thus my personal point of view is that it is better to compute in radix 2
as GMP does. Of course this assumes the base conversion really has complexity
O(M(n) log(n)), which is not completely true with gmp-4.2.1: the base-2 to
base-10 conversion implements a subquadratic algorithm, but relies on the
division, which has cost O(M(n) log(n)) in 4.2.1 instead of O(M(n)) in 5.0.
Thus the current base 2 -> base 10 conversion has cost O(M(n) log(n)^2).

Paul