fixed-size mpn_mul_n for small n?

Niels Möller nisse at
Mon Feb 13 15:07:45 CET 2012

Zimmermann Paul <Paul.Zimmermann at> 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 mailing list