Paul.Zimmermann at loria.fr
Thu Apr 12 11:48:46 CEST 2007
> 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
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).
More information about the gmp-discuss