Shared toom evaluation functions

Niels Möller nisse at
Thu Nov 19 16:37:58 CET 2009

bodrato at writes:

> I tried the other way, look if you like the code:

I find the MP_PTR_SWAP somewhat ugly.

I would have tried doing the first additions differently depending on
k&1, something like

  if (k & 1)
      xp = x_{k-3} + 4*x_{k-1};
      tp = x_{k-2} + 4*x_k;      // With x_k of smaller size
      xp = x_{k-2} + 4*x_k;      // With x_k of smaller size
      tp = x_{k-3} + 4*x_{k-1};

  /* Loops adding further full-size terms to tp and xp using
     addlsh2_n, and no further dependencies on whether or not k is
     odd. */

The first additions need *some* special handling anyway since they have
different source operands than the additions in the loop, although the
above implies some extra coded duplication.

Or maybe an even better organization would be to always collect the k,
k-2, ... terms in one variable, the k-1, k-3, ... in another, and then
only check k & 1 until you get to the subtraction step. That almost
makes sense, one must also add a shift of the variable corresponding
to the odd terms, so one would would be something like

  mpn_lshift ((k & 1) ? xp2 : tp, ...);

  neg = mpn_cmp(...);
  if (neg)
    addsub(...); /* Opposite argument order */

  return neg ^ (k & 1);


More information about the gmp-devel mailing list