Decimal arithmetic

[Vincent Lefevre]

On 2007-04-13 00:49:41 +0200, Richard B. Kreckel wrote:
> 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?

When Paul was saying "radix 10", I'm quite sure he was thinking of
a power of 10 (more probably 10 to an even number, such as 10^8 or
10^18, as this is much better for the multiplication).

The constant is probably not very large, but large enough to be
noticeable in practice. If you think we are wrong, I suggest you
start writing the addition and multiplication in radix 10^k and
see by yourself by comparing with GMP...

Carry propagation in the addition is slower in radix 10^k, and I'd
say in particular on processors where a branch is needed, whereas
in radix 2^k (where k = register size), there is often nothing to
do (support for carry propagation in hardware). Concerning the
multiplication, one needs to split a number < 10^k into two numbers
< 10^(k/2). In radix 2^k, this is easy thanks to shifts. But in
radix 10^k, this is much slower.

-- 
Vincent Lefèvre <vincent at vinc17.org> - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)