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

Niels Möller nisse at lysator.liu.se
Fri Oct 9 23:58:27 CEST 2009

```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
```

More information about the gmp-devel mailing list