mpn_powm not documented -- an oversight?

Torbjorn Granlund tg at
Mon Oct 1 23:26:05 CEST 2012

Will Galway <galway at> writes:

  I've just run a test comparing the speed of mpz_powm(...) against that
  of mpn_powm(...).  (Not against gmp_powm--of course there is no
  gmp_powm despite my typo in my earlier message.)
  Mytest was run on a Core i7-870 processor, where type mp_limb_t is a
  64-bit unsigned integer.  The test computed 2^A modulo B, for many
  64-bit values of B and with A fixed at roughly 30000.  I found
  mpn_powm(...) to be less than 10% faster than mpz_powm(...). Of
  course, other people's experience might vary, depending on the
  architecture they're using.
  I'd expect the speed difference to be even less when working with
  multi-limb arguments, so I feel there is no need to make mpn_powm(...)
  "public".  It's alsoa spectacular example of just how efficient GMP
I suspect mpz_powm/mpn_powm is perhaps an example that makes the
overhead of GMP look less than it is.  You would see much more
difference when using mpz_mul/mpn_mul, I'm afraid.

The reason for that is that mpn_powm actually need to make quite a large
computation, even for such tiny arguments as used in your test.

We recently implemented single-word and dual-word powm, for GNU factor.
These might end up GMP.  It would be interesting to see speed comparison
bewteen this and mpn_powm.  Please see

(These work in a non-standard representation of the ring mod n, where
ring operands are multiplied by \beta (for powm) and \beta^2 (for
powm2).  The operand 'one' is \beta mod n and \beta^2 mod n,
respectively, i.e., the number 1 in the non-standard ring
representation.  Use redcify/redcify2 to get into that representation.)


More information about the gmp-discuss mailing list