Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)

[Niels Möller]

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

> Anyway, I think hensel division or divexact by d = 2^60 - 1 should be
> fairly efficient, or at least multiplication free. Even id we do it
> one full limb at a time.

I was confused by the multiplication q * d, it's easy enough because
of the form of d = 2^60 - 1, no need to make things more complicated
by also using the form of q like I did in the previous mail...

Looking at the innerloop of generic/dive_1.c, division by 2^60 - 1
would be the innerloop

      do
	{
          /* This should be floor(2^{-64} (2^{60} - 1) l), hope I got
	     it right. */
          h = (l >> 4) - (l > (l << 60));
	  c += h;

	  s = src[i];
	  SUBC_LIMB (c, l, s, c);

	  l = l + (l << 60);
	  dst[i] = l;
	  i++;
	}
      while (i < size);

and division by 45 would be

      do
	{         
          h = (l >> 4) - (l > (l << 60));
	  c += h;

	  s = src[i];
	  SUBC_LIMB (c, l, s, c);

	  l = l + (l << 60);
          umul_ppmm (ph, pl, l, ((1L << 60) - 1) / 45);
          add_ssaaaa (hi, pl, ph, pl, 0, hi);
	  dst[i] = pl;
	  i++;
	}
      while (i < size);

Does that make sense?

Regards,
/Niels