speed enhancement

Paul Zimmermann Paul.Zimmermann at loria.fr
Wed Sep 29 10:10:17 CEST 2010


>   the reason is simple: with remp=NULL mpn_rootrem computes an extra limb of
>   the k-th root, which in most cases is enough to deduce if the remainder is
>   zero or not (however it seems the code does not cover the corner case).
>   
> Are you implying we might have a bug here, if we elsewhere assume it
> computes floor(A^(1/B))?

the comments say that in case of the recursive call, {sp,sn} is either the
correct root or one too large. But if one too large and sp[0]=0, then returning
{sp+1,sn-1} as we do is incorrect.

However after several millions random tests with mpn_random2, k=2 and
input a square minus 1 (which should be the worst case for {sp,sn}
possibly one too large) I was unable to find a corner case. Maybe
the algorithm always returns the correct {sp,sn}?

>   yes, see my previous mail.
>   
> Which mail?  (Subject+date please.)

http://gmplib.org/list-archives/gmp-devel/2010-September/001657.html

Paul


More information about the gmp-devel mailing list