Decimal arithmetic
Richard B. Kreckel
kreckel at ginac.de
Fri Apr 13 00:49:41 CEST 2007
Hi!
Paul Zimmermann wrote:
> 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.
But that constant could be made quite small by using base 10^9 on a
32-bit machine or 10^19 on a 64-bit machine, right? The effect of
avoiding radix conversion would still be the same.
However, I am still sceptical about those closed-source programs I'm not
going to name when Torbjorn is around doing base-10 arithmetic. Is there
any real evidence they really do that?
> Thus my personal point of view is that it is better to compute in radix 2
> as GMP does.
Me too. :)
> 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).
Fascinating. I'll have to look where the division comes in. As far as I
recall, there is no need for division.
Bye!
-richy.
--
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>
More information about the gmp-discuss
mailing list