Decimal arithmetic

[Richard B. Kreckel]

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/>