Anomaly in mpn_sqrtrem and mpn_rootrem
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Tue Jul 14 09:48:44 UTC 2015
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/
More information about the gmp-devel
mailing list