In theory, the FFT should handle very unbalance operands just fine.
But as you can see it is a matter of tuning at some points.
Obviously we should be using something else at this size.
The right way to handle really unbalanced operands like this is to
keep the smaller operand in Toom format and step along the larger
operand completing a whole bunch of small multiplications.
Currently we don't do this, and just keep putting the smaller operand
into Toom format over and over again.
Anyhow, if you can come up with a better tuning strategy, we can alter
this in the next MPIR. Remember that our FFT is completely different
to the one in GMP though, so simply using their strategy may work at
this point, but is not guaranteed to be the right strategy for our
multiplication code overall.
Bill.
On 9 March 2013 11:28, Fredrik Johansson <fredrik.johans...@gmail.com> wrote:
> There seems to be a pretty serious tuning issue with (highly)
> unbalanced multiplication in mpir-2.6.0:
>
> 380000 x 1400 bits takes 155 us
> 390000 x 1400 bits takes 895 us
>
> This is with
>
> model name : Intel(R) Xeon(R) CPU X5675 @ 3.07GHz
>
> and
>
> gmp-mparam.h -> mpn/x86_64/nehalem/westmere/gmp-mparam.h
>
> I'm trying to understand what's going on in mpn_mul.
> MUL_KARATSUBA_THRESHOLD is 64 (= 1024 bits), which means it should be
> moving on in both cases to
>
> if (ABOVE_THRESHOLD (un + vn, 2*MUL_FFT_FULL_THRESHOLD))
> {
> mpn_mul_fft_main (prodp, up, un, vp, vn);
>
> MUL_FFT_FULL_THRESHOLD is 3008 (= 192512) bits, so it seems to be
> entering the FFT in both cases and there must be a tuning issue in the
> FFT.
>
> The condition for entering the FFT code seems wrong in the first place,
> though.
>
> Shouldn't it first check if the *smallest* operand size (vn) is in
> range of any of the available Karatsuba/Tooms, and use FFT only when
> the smallest operand is roughly FFT sized?
>
> I peeked at the current GMP mpn_mul and it does not try using FFT
> multiplication if BELOW_THRESHOLD(3 * vn, MUL_FFT_THRESHOLD)... this
> sounds more sensible.
>
> Fredrik
>
> --
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to mpir-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to mpir-devel@googlegroups.com.
> Visit this group at http://groups.google.com/group/mpir-devel?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
--
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to mpir-devel+unsubscr...@googlegroups.com.
To post to this group, send email to mpir-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/mpir-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
