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
_______________________________________________
gmp-discuss mailing list
gmp-discuss swox.com
http://s
wox.com/mailman/listinfo/gmp-discuss
|