Decimal arithmetic

[Décio Luiz Gazzoni Filho]

Le Apr 12, 2007 à 6:48 AM, Paul Zimmermann a écrit :

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

I guess that depends on how often you need to do the base conversion.  
Now I can't go into details, because the person I'm asking on behalf  
of is doing his best to hide from me what he's trying to accomplish.  
The most I was able to learn is that he's working with  
cryptographically sized values. But as I understand he's doing very  
few operations between digit extractions, so the ratio of arithmetic  
to base conversion should be low, with base conversion probably not  
worth it.

Still, I don't think the loss is significant with decimal arithmetic.  
OK, so with binary you can have (on a 32-bit processor) radix-2^32  
arithmetic rather than radix-10^9 arithmetic for an extra 2 bits per  
limb. Still, I've seen a move to radices smaller than the CPU word  
size -- for instance, look at what Dan Bernstein's been producing,  
say the NIST P224 code, which I believe uses something like  
radix-2^27 or 2^29 to avoid explicit carries which serialize the  
computation (terrible for current wide-issue superscalar CPUs). Even  
in FFT range, the choice of radix highly depends on operand size, and  
for certain choices decimal may actually be superior to binary.

> 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).

Again, I think that depends on the ratio of arithmetic to base  
conversion. A blanket statement like that is bound to be wrong  
sometimes.

Décio