Anomaly in mpn_sqrtrem and mpn_rootrem

[bodrato at mail.dm.unipi.it]

Ciao,

Il Mer, 8 Luglio 2015 4:20 pm, Torbjörn Granlund ha scritto:
> bodrato at mail.dm.unipi.it writes:
>
>   The code above should give a range for the first 5 bits (the first is 1
>   anyway), and it should work for any k.

> But I spotted "% k" and "/ k" there, and those are very expensive,
> unless you table inverses of k, of course...

There is already a single (there are two currently, but we can avoid one)
division by k in the code, it is used to compute the first single-bit
estimate. The trick I suggest consists in adding some fractional digits of
log2(n), by table lookup, then use log2(n)/k to estimate a few of the
highest digits of n^(1/k), not just one.

I still have to analyse the maximal error, but I believe we can use the
trick to skip some iterations.

Best regards,
m

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