Faster integer remainder

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> One could attempt to omit q_1 and instead compute a more accurate q_0 as
>
>   q_0 = LO(u_1 * v) + u_0 + HI(u_0 * v)
>
> and remainder would then hopefully be
>
>   r = HI(f * d)
>
> That's one more multiplication, if I'm not missing something, 

Had a closer look, and this won't work. To get close to working, one
needs a more accurate recipropcal, say

  {v_1, v_0} = floor [(B^3 - 1)/d] - B^2

and add one more term to the fraction:

  q_0 = LO(u_1 * v_1) + u_0 + HI(u_0 * v_1) + HI(u_1 * v_0)

So that's yet another multiplication, and I think it's still not
accurate enough to get a correct remainder. HI(q_0 * d) will now be
close, but I think it can still be one off.

If one adds in the carry from the next lower fraction limb, LO(u0 * v1)
+ LO(u1 * v0) + HI(u0 * v0) it will probably work, but that's yet
another multiply and a couple of additions. *Maybe* one can get away
with only the LO parts.

So with a two-limb reciprocal, the multiplication is

  +---+---+---+---+
  |u_1|u_0|u_0*v_0|
  +---+---+---+---+
  |u_1*v_1|
  +---+---+---+
      |u_0*v_1|
      +-------+
      |u_1*v_0|
  +---+---+---+---+
  |q_1|q_0|q_{low}|
  +---+---+-------+

The "direct" method only needs q_0, but it needs it to be computed
accurately, with contributions from all four products (*maybe* one could
omit u_0*v0).

While udiv_rnnd_preinv needs q_1 and a crude version of q_0, and gets by
with only the top corner, omitting all products involving u_0 or v_0.

So I doubt the direct method can be faster for 2/1 modulo.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.