new Toom-Cook 3-way code

Torbjorn Granlund
23 Aug 2003 13:39:38 +0200

[Background to gmp-devel readers: Paul just made improvements to
the toom3 multiply code, and is now working on gcd.  I've been
suggesting that we extend the low-level mpn functions with some
combined operations like shift-add and shift-sub.] (Paul Zimmermann) writes:

     A different question is whether to extend the low level function
     set somewhat.  E.g., mpn_addmul_1 could be complemented with
     mpn_addmul_2exp (or if we choose to call it mpn_addlsh).
     (Analogously with mpn_submul_2exp/mpn_sublsh.)
     If a += 2b is in practice the only power-of-2 multiplier that
     will be used, perhaps we could implement just that.  I expect
     that to be faster on x86 then a general mpn_addmul_2exp.
  A general mpn_addlsh (for a shift 0 <= k < GMP_NUMB_BITS) would be
  highly welcome, especially in the mpfr addition.
  Here are some first results on the gcd front:
  norroy% ./gcd 50000 # 50000-limbs numbers
  mpz_gcdnew took 6580ms
  mpz_gcd took 34260ms
This is great news.  You're busy hacking GMP these days!

When it comes to gcd, please coordinate with
He recently mailed new code to
(I am ashamed to say that nobody reacted to his posting yet.)