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.)



More information about the gmp-devel mailing list