mpn_powm not documented -- an oversight?
Torbjorn Granlund
tg at gmplib.org
Mon Oct 1 23:26:05 CEST 2012
Will Galway <galway at math.uiuc.edu> 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
is!
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
<http://gmplib.org:8000/factoring/file/tip/factor.c>.
(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.)
--
Torbjörn
More information about the gmp-discuss
mailing list