whats happening ?
Wed, 23 Oct 2002 10:08:22 +1000
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.