Anomaly in mpn_sqrtrem and mpn_rootrem

bodrato at bodrato at
Tue Jul 14 09:48:44 UTC 2015


Il Mer, 8 Luglio 2015 4:20 pm, Torbjörn Granlund ha scritto:
> bodrato at 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,


More information about the gmp-devel mailing list