Invariant multiplier in Karatsuba/Toom

Torbjorn Granlund tg at
Sun Feb 29 16:54:30 CET 2004

I and Kalle (kha at are working on division with
invariant divisors, allowing users to pre-compute an approximate
inverse, storing the result in an opaque type ("mpz_prediv_t").
We will also introduce new division functions accepting
mpz_prediv_t in addition to the dividend and divisor operands.

The exact format of the pre-computed data will vary with operand
sizes and perhaps with the exact value.  For large enough
operands, we will typically just compute an approximate inverse
of the divisor.  The divisions will then use Barrett's algorithm;
divisions will be replaced by invariant multiplications.

The multiplications in Barrett's algorithm will thus use an
invariant multiplier.

Has anybody on this list looked into invariant-operand Karatsuba
or Toom multiplication?  (For FFT, it is trivial.)  Also, has
anybody looked into non-recursive variants of Karatsuba or Toom?
It seems much easier to deal with a pre-computed operand with
non-recursive variants of these algorithms.


More information about the gmp-devel mailing list