Anomaly in mpn_sqrtrem and mpn_rootrem

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   There are divisions also in the newton iteration, right? Then a single
>   division in the computation of the initial value is likely a win, if it
>   saves two or more iterations in the loop.
>   
> There are GMP division operations, but these are not likely going to hit
> any hardware division.

They're doing an expensive preinv per iteration, IIRC. So a preinv (or
even plain division) involving k should pay off, if it saves a few
iterations.

> Surely the most important k is 3 (assuming 2 is always handled by the
> sqrt code).

Elaborate? Are you thinking of any particular algorithm using cube
roots, or just the general observation that smaller numbers tend to be
more common?

Regards,
/Niels

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