Reason for definition of precomputed reciprocals
Paul Zimmermann
Paul.Zimmermann at inria.fr
Thu Jun 25 15:26:39 CEST 2026
Niels,
> Using v = floor((B^2 - 1) / d) - B implies that
>
> (B + v) d = B^2 - k, with 1 <= k <= d
>
> With the alternative smaller reciprocal you suggest, it seems that
> instead one would get
>
> (B + v) d = B^2 - k with d <= k < 2d
I agree with the above, and it seems the first is more accurate.
In fact the first is the best one if you want to avoid k=0
(which occurs only for d=B/2 when B=2^b, where it would give v=B which does not fit
in one limb).
Paul
More information about the gmp-devel
mailing list