mpz_perfect_power companion

[Marco Bodrato]

Ciao,

Il Mar, 26 Marzo 2019 10:09 pm, Seth Troisi ha scritto:
> Add companion for mpz_perfect_power_p that returns the exponent and
> optionally the root. Possible name mpz_rootexact.

> I have experience using gmp and writing C++ code but not a lot of
> experience writing clean performant C code. It would be nice to confirm
> that the current maintainers have time to review (and help improve)
> patches that I'd be writing.

Now, that some work started on gcd, I think that the release of a new GMP
version will not happen in short times. So yes, I think I'll have the time
to review your code!

> I thought a good first step would be to add support for the two related
> functions (mpz_perfect_power_p, mpz_perfect_square_p) in tune/speed which
> I already started on.

I just pushed two optimisations that should impact on mpz_perfect_power_p:

https://gmplib.org/repo/gmp/rev/042ea5bf2ed1
Changed brootinv.c to always exploit the fact that all exponentiations use
an even exponent, so that they can be computed as (x^2)^(e/2).

https://gmplib.org/repo/gmp/rev/d863c8b31626
Some copying around of values is avoided with a flipflop that tracks where
the value is and should be... Moreover unneeded initialisations are
skipped for small exponents.

> https://github.com/sethtroisi/libgmp/pull/1/files
> https://patch-diff.githubusercontent.com/raw/sethtroisi/libgmp/pull/1.patch

I believe that you measure functions should be able to detect if the two
patches above are effective in speeding-up mpz_perfect_power_p.

A couple of comments about them:

in both SPEED_ROUTINE_MPN_PERFECT_{POWER,SQUARE} you use:
s->size * GMP_LIMB_BYTES
but I think you are using the wrong constant. You need to estimate the
exponent e such that p^e has a given number of limbs, right?

The number of bits stored in each limb is GMP_NUMB_BITS. That's why I'd
suggest:
s->size * GMP_NUMB_BITS
instead.


Maybe it's better to use mpz_ui_pow_ui and mpz_mul_ui, to avoid storing
small numbers in mpz_t variables, if not needed?


in SPEED_ROUTINE_MPN_PERFECT_POWER, maybe using
p = 2^16+1; r = 2^17 - 1; and log2(r) = 17, can be more clean than using
nextprime on fixed constants...

For the same reason, I'd suggest the same r for
SPEED_ROUTINE_MPN_PERFECT_SQUARE too. But, why not simply squaring a
random number of half the size?


Of course in both cases you may need some special handling for small sizes
on CPUs with small bit sizes (i.e. when you get power <= 1).


In general, a couple of functions more that can be timed is always a nice
enhancement for the library...


Ĝis,
m

-- 
http://bodrato.it/papers/