Reason for definition of precomputed reciprocals

[Niels Möller]

Albin Ahlbäck <ahlback at lix.polytechnique.fr> writes:

> I'm currently writing routines for computing integer reciprocals, and
> I'm wondering why the definition is `floor((B^2 - 1) / d) - B' instead
> of `floor(B^2 / d) - B - 1'.  The current definition yields a slightly
> faster final iteration written this way, but seemingly at the cost of
> introducing another branch in the division with precomputed
> reciprocals.

I'm not sure what you are after, do you have some improvement to the
algorithm?

Using v = floor((B^2 - 1) / d) - B implies that

  (B + v) d = B^2 - k, with 1 <= k <= d

and the algorithm correctness depends on this range for k. (And the
reason for the "-1" is just to ensure that v < B also for the smallset
allowed d, d = B/2. Except for this cornercase, I think v = floor(B^2 /
d) - B would work just as fine).

With the alternative smaller reciprocal you suggest, it seems that
instead one would get

  (B + v) d = B^2 - k with d <= k < 2d

If you think that is beneficial, please explain.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.