fixed-size mpn_mul_n for small n?
nisse at lysator.liu.se
Mon Feb 13 15:07:45 CET 2012
Zimmermann Paul <Paul.Zimmermann at loria.fr> writes:
> agreed. But to avoid this dependent multiplication, I believe
> Montgomery-Svoboda has more potential. Instead of performing n addmul_1 calls
> with N, you perform n-1 call with k*N such that the low limb of k*N is -1
> (thus the quotient selection is trivial) and one call with N.
Ah, that's clever. I wasn't aware of that method.
> for GMP-ECM, the most important range is from 10 to 20 limbs, i.e., about 200
> to 400 decimal digits.
Using completely unrolled code for all these sizes (I'm now primarily
thinking of squaring) seems a bit impractical. Maybe one could do
something reasonable with specialcase code for collecting the
off-diagonal terms (long code with jumpts into), and then a plain loop
for the diagonal and the final shift + add.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel