A perfect power, and then?

Niels Möller nisse at lysator.liu.se
Thu Oct 25 18:36:46 CEST 2012

Torbjorn Granlund <tg at gmplib.org> writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>   My bsqrt uses an iteration converging to a^{-1/2}, and broot uses an
>   iteration converging to a^{1/n - 1}. Both division free.
> So binv_sqroot (from mpn/generic/perfpow.c and your bsqrt seem to
> compute the same function.

Do you think we should have an advertised binv_sqrt function returning
a^{-1/2}? (And if so, should we have something analogous also for
euclidean square root? And for nth roots?)

My bsqrt first computes a^{-1/2}, but then it multiplies it by a before
returning a^{1/2}.

How do we make some progress here? I'm tempted to first commit my broot
and corresponding test code (since that has less interface subtleties
than bsqrt).

>   They should use mulmod_bnm1 rather than mullo for larger sizes, but they
>   currently don't. I haven't done any serious benchmarking.
> That's just like the perfpow.c functions, then.

I do take some advantage of cancellation though.


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list