Decimal arithmetic
Décio Luiz Gazzoni Filho
decio at decpp.net
Fri Apr 13 02:35:58 CEST 2007
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
More information about the gmp-discuss
mailing list