Shared toom evaluation functions

Torbjorn Granlund tg at
Thu Nov 19 15:56:06 CET 2009

nisse at (Niels Möller) writes:

  Torbjorn Granlund <tg at> writes:
  > I think we might want to make our lives in toom more difficult:
  > We should add, to gmp-mparam.h, cycle counts for available mpn functions
  > as first degree polynomials.  Measurements for that can easily be added
  > to tuneup.c.
  I was about to suggest something similar, but a little simpler, with
  only a cycles/limb value for each of the O(n) functions. Do you think
  the constant overhead is important here?
Perhaps not here, but it will be useful elsewhere.  It is not hard to
measure one paramater when we measure the other.

If we in toom thin the cnstat term is irrelevent, then of course we can
just compare the x^1 term.  Much simpler indeed.

  The first conditional (add_n_sub_n, which I guess should always be
  used when available natively) appears in toom32_mul. It's more
  relevant for the variuos interpolation functions, i.e., from
  toom33/toom42 and up, where there are several possible strategies for
  division and multiplication by constants.
  My gut feeling is that the constant term shouldn't be so significant
  for the choices for toom interpolation.
Perhaps not.  But when working with operands that are known to be small
(say in toom22) three calls might be slower than two calls, even if the
three calls are asymptotically faster.

We might have such a situation with the new toom22 code compared to the
old kara code; we have one more add_n call but n/2 less adding.  This is
surely not always a good idea, on all machines.  The constant term is
needed to determine that.


More information about the gmp-devel mailing list