Iterative Toom-Cook-2.5 (Toom32) method for unbalanced multiplication

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> Last year, Niels Möller implemented toom22 (aka karatsuba) using
> separate "transforms" of one or both operands.  IIRC, he saw savings of
> around 10% per pre-transformed operand.

For fun, I tried to extend this idea to support both toom22 and toom32.
Unlike Alberto's code, the attached code doesn't try to do anything
clever in evaluation and interpolation, and it's not terribly useful in
the current form. Instead, I've tried to get a reasonable structure that
can be extended to other multiplication variants.

Algorithm choice (basecase, toom22, toom32, toom23 (toom32 but with the
smaller operand invariant), or "other" (implemented as a call to plain
mpn_mul) is based on the logic in mul.c.

Two main functions:

  mp_size_t
  mul_pre_eval (mp_ptr pe, mp_srcptr up, mp_size_t un, mp_size_t vn);

This evaluates polynimials related to u, to be multiplied by some number
of size vn. It determines the algorithms to use all the way down to
basecase, and precomputes all needed polynomial evaluations. Returns the
size of the precomputed data, and if the passed in pe is NULL, it just
computes and returns the amount of needed storage.

  void
  mul_invariant (mp_ptr rp, mp_srcptr up, mp_size_t un, mp_srcptr pe,
	         mp_srcptr vp, mp_size_t vn);
               
Multiplies u times v, using the previously precomputed data pe
corresponding to u. v can be of arbitrary size, but the precomputed data
is used only as long as the size of v fits the algorithm choices
corresponding to the precomputation.

Regards,
/Niels

-------------- next part --------------
A non-text attachment was scrubbed...
Name: mul_invariance.c
Type: text/x-csrc
Size: 13832 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20091227/73720932/attachment.bin>
-------------- next part --------------

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