mpn_mul_fft type overflow issue

Torbjorn Granlund tg at
Mon Sep 23 18:34:10 CEST 2013

Mark Sofroniou <marks at> writes:

  Attached is a revised patch for mul_fft.
  I have tested it to confirm that both mpn_mul and mpn_tdiv_qr now
  work with numbers of size 2^32 limbs.

I started looking at this, and noticed two things.

1. The patch does not apply to the current source version:

      Patching file mpn/generic/mul_fft.c using Plan A...
      Hunk #1 succeeded at 67.
      Hunk #2 succeeded at 192.
      Hunk #3 succeeded at 283.
      Hunk #4 succeeded at 314.
      Hunk #5 failed at 428.
      Hunk #6 succeeded at 447.
      Hunk #7 succeeded at 477 with fuzz 1 (offset 5 lines).
      Hunk #8 failed at 499.
      Hunk #9 succeeded at 577 (offset 5 lines).
      Hunk #10 succeeded at 592 (offset 5 lines).
      Hunk #11 succeeded at 630 (offset 5 lines).
      Hunk #12 succeeded at 718 (offset 5 lines).
      Hunk #13 succeeded at 799 (offset 5 lines).
      Hunk #14 succeeded at 819 with fuzz 1 (offset 5 lines).
      Hunk #15 succeeded at 840 (offset 5 lines).

2. You don't make use of mp_bitcnt_t.  Please do.  I think e.g. the d
   parameter of mpn_fft_mul_2exp_modF should use that type.  Callers
   might need type changes or casts (converting the result of an
   arithmetic expression to the parameter type will be too late.)

3. Let's not change types where it is not well motivated.  The 'sh'
   variable of mpn_fft_mul_2exp_modF does not need anything wider than
   int.  (It is a shift count of a limb, so will be 0 ... 63.)

I would appreciate if you could address these things.  We will make
these changes to the 'head' repo, not to the 5.1 repo.  Therefore,
please base your work on the former repo.


More information about the gmp-devel mailing list