speed of unbalanced multiplication

[Zimmermann Paul]

       Marco,

> Date: Sat, 26 Jan 2013 16:21:28 +0100 (CET)
> From: bodrato at mail.dm.unipi.it
> 
> Ciao,
> 
> Il Sab, 26 Gennaio 2013 4:01 pm, bodrato at mail.dm.unipi.it ha scritto:
> > I mean, which timing do you obtain with the following?
> > ./speed -s $((1000000+775660)/2) mpn_mul_n mpn_mul_n
> 
> Sorry... I mean:
> 
> ./speed -s $[(1000000+775660)/2] mpn_mul_n mpn_mul_n

here is another example:

frite% ./speed -s 600000 mpn_mul.1000000 mpn_mul.1000000 mpn_mul.1000000
overhead 0.000000002 secs, precision 10000 units of 3.33e-10 secs, CPU freq 3000.00 MHz
        mpn_mul.1000000 mpn_mul.1000000 mpn_mul.1000000
600000   #0.716044000   0.720045000   0.716045000

frite% ./speed -s 800000 mpn_mul_n mpn_mul_n mpn_mul_n
overhead 0.000000002 secs, precision 10000 units of 3.33e-10 secs, CPU freq 3000.00 MHz
            mpn_mul_n     mpn_mul_n     mpn_mul_n
800000    0.676042000   0.680043000  #0.672042000

In the FTT range, multiplying n limbs by m limbs should not be more expensive
then multiplying two numbers of (n+m)/2 limbs.

In that case, we get a 6.5% slowdown with respect to that strategy.

Note that I did not try to get the largest possible slowdown.

Paul