whats happening ?

[Kevin Ryde]

Jason Moxham <J.L.Moxham@maths.soton.ac.uk> writes:
>
> mpz_rootexact (like mpz_divexact but for roots)  using varible precision , 
> division free p-adic newton method

Not sure if there'd be much direct use for that.  When would one know
a number is an exact power?

> mpz_perfect_power_p using parts of the above fn's

If it finds a use there then it'd be fine.

> mpz_invert_2exp (like mpz_invert but 2^n modulas) again using above p-adics

I looked at that as part of the redc, since it wants such an inverse.
The function would match mpz_invert nicely, but again I'm not sure
quite how much use it would get.

Paul Z had some ideas about efficiency which I've (still) yet to look
at properly.  Efficiency isn't a big deal for the prospective mpm
since the inverse is calculated just once at the start.

> I suppose I should also look at the generalization of the karatsuba square 
> root method .

Paul might have a cube root along those lines, but I don't think we've
got a general one.

> One other thing , I also have a (slow)implementation of mpz_kronecker using 
> the accelerated gcd algorithm , its only twice as fast for about 100000 limbs

That or the lehmer multi-step algorithm should help that routine quite
a lot, since right now it nibbles away one bit at a time.