Adventures of a Programmer: Parser Writing Peril XVI

Back to the experiment with balancing multiplicands which failed despite the advantage it must have shown based on the theory and if the margin of this blog post would have been wider I could even proof that it is better!
*stomps foot*
And it is better! All I have done was to comment the wrong line out and instead of getting two distinct benchmarks the second benchmark was the sum of both that let me think that balancing needs about twice the time than normal multiplication.
Moral of the story: if some results look suspicious, they mostly are. Or would you buy a machine that generates energy for free?

So, how does the real benchmark look?
Well, differently πŸ˜‰

The method is as described before but let me talk a bit about the numbers to be tested.
It should be obvious that the balancing will make sense only for numbers large enough to pass the cut-off point of the Toom-Cook algorithms (T-C 2 {Karatsuba} and 3 are implemented in Libtommath) otherwise it would slow the multiplication down—costly overhead without any effect. The cut-off points will differ from architecture to architecture and mine are (in mp_digits): TC2 = 48,TC3 190 and for the very big numbers FFT=4000 (which is oversimplified but I’m working at it).
The tests for the small numbers run 1,000 times each. Time is in seconds.

</tr

Number Pair Normal Multiplication Balanced Multiplication
50 * 100 0.04 0.07
100 * 150 0.14 0.15
100 * 200 0.18 0.19
150 * 300 0.35 0.34
100 * 400 0.37 0.44
200 * 400 0.79 0.61
300 * 400 0.98 0.91
150 * 500 0.62 0.63
250 * 500 1.13 0.81
350 * 500 1.38 1.19
400 * 500 1.35 1.28
450 * 500 1.30 1.30
50 * 600 0.53 0.54
100 * 600 1.00 0.60
150 * 600 1.42 0.75
200 * 600 1.31 1.12
250 * 600 1.44 1.14
300 * 600 1.78 1.37
350 * 600 1.81 1.45
400 * 600 1.83 1.78
450 * 600 1.86 1.57
500 * 600 1.74 1.68
550 * 600 1.62 1.88
50 * 700 0.61 0.63
100 * 700 1.18 1.21
150 * 700 1.69 0.97
200 * 700 2.83 1.39
250 * 700 3.23 1.55
300 * 700 2.16 1.91
350 * 700 2.22 1.44
400 * 700 2.34 1.87
450 * 700 2.35 2.06
500 * 700 2.32 2.27
550 * 700 2.26 2.09
600 * 700 2.68 2.76
650 * 700 2.39 2.53
50 * 800 0.69 0.74
100 * 800 1.36 1.42
150 * 800 1.95 1.91
200 * 800 3.34 1.70
250 * 800 3.84 1.90
300 * 800 4.46 2.35
350 * 800 3.18 2.25
400 * 800 2.85 1.70
450 * 800 2.91 2.22
500 * 800 2.93 2.60
550 * 800 2.88 2.70
600 * 800 3.73 3.07
650 * 800 3.51 3.51
700 * 800 3.16 3.37
750 * 800 2.82 2.96
50 * 900 0.78 0.83
100 * 900 1.54 1.57
150 * 900 2.21 2.15
200 * 900 3.94 3.43
250 * 900 4.48 2.20
300 * 900 5.29 2.64
350 * 900 5.72 2.42
400 * 900 6.00 2.29
450 * 900 6.20 2.01
500 * 900 3.58 2.64
550 * 900 3.55 2.99
600 * 900 4.91 3.56
650 * 900 4.79 3.76
700 * 900 4.33 5.07
750 * 900 4.07 4.21
800 * 900 3.73 4.07
850 * 900 3.68 3.89
50 * 1000 0.87 0.93
100 * 1000 1.72 1.78
150 * 1000 2.50 2.49
200 * 1000 4.35 4.01
250 * 1000 5.12 4.38
300 * 1000 5.99 3.03
350 * 1000 6.55 3.07
400 * 1000 6.96 2.80
450 * 1000 7.25 2.62
500 * 1000 7.44 2.32
550 * 1000 7.57 2.96
600 * 1000 5.86 3.64
650 * 1000 5.74 3.99
700 * 1000 5.55 4.40
750 * 1000 5.35 6.00
800 * 1000 5.08 6.12
850 * 1000 5.08 5.26
900 * 1000 4.87 5.01
950 * 1000 4.28 4.51

Some points a more off than others, that might have a reason in the actual numbers which get produced with a cheap PRNG and are used over the whole loop. Let me repeat the last round ([50,950] * 1,000) with a different number each time. (Generating thousands of large numbers takes some time but we can ignore it, it is the same for both)

Number Pair Normal Multiplication Balanced Multiplication
50 * 1000 5.03 3.87
100 * 1000 5.05 3.84
150 * 1000 4.99 3.85
200 * 1000 4.99 3.86
250 * 1000 5.00 3.89
300 * 1000 5.00 3.85
350 * 1000 5.00 3.86
400 * 1000 5.00 3.92
450 * 1000 4.99 3.85
500 * 1000 5.05 3.87
550 * 1000 4.99 3.89
600 * 1000 5.05 3.86
650 * 1000 4.98 3.88
700 * 1000 5.08 3.86
750 * 1000 5.05 3.88
800 * 1000 4.98 3.84
850 * 1000 5.01 3.94
900 * 1000 5.12 3.86
950 * 1000 5.03 3.85

Oh?
Let’s use libtomath’s own tool mp_rand,too:

Number Pair Normal Multiplication Balanced Multiplication
50 * 1000 8.50 7.34
100 * 1000 8.50 7.37
150 * 1000 8.49 7.38
200 * 1000 8.47 7.35
250 * 1000 8.48 7.34
300 * 1000 8.50 7.39
350 * 1000 8.48 7.36
400 * 1000 8.49 7.35
450 * 1000 8.47 7.30
500 * 1000 8.47 7.33
550 * 1000 8.49 7.37
600 * 1000 8.47 7.33
650 * 1000 8.47 7.32
700 * 1000 8.47 7.34
750 * 1000 8.51 7.34
800 * 1000 8.46 7.36
850 * 1000 8.49 7.37
900 * 1000 8.47 7.33
950 * 1000 8.46 7.38

The function mp_rand is more exact as it makes sure that the MSD is always different from zero. This gives an interesting effect: the balanced version is even faster when both multiplicands have been ordered to have the same size. So let me get something to read while the following script runs:

for i in `seq 50 50  1000`;
 do  for j in `seq 50 50  $i`;
   do ./testbalancing $i $j;done;done

The last round is the most significant:

Number Pair Normal Multiplication Balanced Multiplication
1000 * 50 1.31 1.32
1000 * 100 1.72 1.67
1000 * 150 2.03 1.90
1000 * 200 2.75 2.30
1000 * 250 2.99 2.35
1000 * 300 3.26 2.60
1000 * 350 3.37 2.66
1000 * 400 3.49 2.79
1000 * 450 3.57 2.98
1000 * 500 3.66 3.31
1000 * 550 3.73 3.63
1000 * 600 4.26 4.20
1000 * 650 4.49 4.41
1000 * 700 4.85 4.86
1000 * 750 5.15 5.18
1000 * 800 5.63 5.40
1000 * 850 6.28 5.88
1000 * 900 6.92 6.30
1000 * 950 7.67 6.80
1000 * 1000 8.47 7.36

As I said at the start of this post: “If some result look suspicious, they mostly are.”, so let’s do a check:
Mmh…

  n = strtoul(argv[1],NULL,10);
  m = strtoul(argv[2],NULL,10);
---
  for(n=0;n<1000;n++){
...
    mp_rand(&a,n);
    mp_rand(&b,m);
  }

Ouch!
Now if that’s not embarassing, I don’t know what else is πŸ˜‰
Ok, now on with the real one. The round with one thousand first to see if the results are reasonable now.

Number Pair Normal Multiplication Balanced Multiplication
50 * 1000 0.920000 1.060000
100 * 1000 1.770000 1.930000
150 * 1000 2.400000 2.460000
200 * 1000 4.640000 4.070000
250 * 1000 5.140000 4.560000
300 * 1000 6.380000 2.880000
350 * 1000 7.080000 2.980000
400 * 1000 7.420000 2.860000
450 * 1000 7.210000 2.520000
500 * 1000 7.360000 2.410000
550 * 1000 7.560000 2.980000
600 * 1000 5.940000 3.630000
650 * 1000 5.910000 3.600000
700 * 1000 5.760000 4.270000
750 * 1000 5.440000 6.060000
800 * 1000 5.210000 5.880000
850 * 1000 5.460000 5.380000
900 * 1000 5.190000 5.100000
950 * 1000 4.410000 4.400000
1000 * 1000 3.540000 3.530000

Yepp, that makes more sense; the data supports the theory. There is a jump about 300*1,000, increases smoothly (more or less) up to about 700*1,000 and…oh, forgot to switch off the shortcuts. Aaaaaand again πŸ˜‰

Number Pair Normal Multiplication Balanced Multiplication
50 * 1000 1.040000 0.870000
100 * 1000 1.870000 2.010000
150 * 1000 2.670000 2.400000
200 * 1000 4.610000 3.980000
250 * 1000 5.180000 4.510000
300 * 1000 6.330000 3.000000
350 * 1000 6.770000 2.850000
400 * 1000 7.030000 2.890000
450 * 1000 7.490000 2.430000
500 * 1000 7.600000 2.450000
550 * 1000 7.730000 2.980000
600 * 1000 5.680000 3.620000
650 * 1000 6.110000 3.990000
700 * 1000 5.890000 4.350000
750 * 1000 5.630000 5.910000
800 * 1000 5.150000 6.110000
850 * 1000 5.360000 5.250000
900 * 1000 5.180000 5.090000
950 * 1000 4.620000 4.340000
1000 * 1000 4.160000 4.290000

Nearly the same. There are two peaks where the differences are close to the Toom-Cook cut-off point. I’ll put the full table after the fold but the conclusion is that this kind of balancing makes most sense between about 3/10 and 7/10 and both multiplicands should be larger than the Toom-Cook 3 cut-off.

Number Pair Normal Multiplication Balanced Multiplication
50 * 50 0.030000 0.020000
100 * 50 0.080000 0.050000
100 * 100 0.060000 0.170000
150 * 50 0.030000 0.100000
150 * 100 0.200000 0.140000
150 * 150 0.230000 0.240000
200 * 50 0.120000 0.150000
200 * 100 0.220000 0.210000
200 * 150 0.280000 0.220000
200 * 200 0.480000 0.340000
250 * 50 0.150000 0.140000
250 * 100 0.250000 0.230000
250 * 150 0.320000 0.250000
250 * 200 0.550000 0.290000
250 * 250 0.410000 0.490000
300 * 50 0.170000 0.140000
300 * 100 0.200000 0.310000
300 * 150 0.410000 0.330000
300 * 200 0.600000 0.430000
300 * 250 0.490000 0.560000
300 * 300 0.680000 0.750000
350 * 50 0.160000 0.290000
350 * 100 0.430000 0.380000
350 * 150 0.490000 0.370000
350 * 200 0.670000 0.500000
350 * 250 0.870000 0.580000
350 * 300 0.860000 0.760000
350 * 350 0.960000 0.970000
400 * 50 0.230000 0.190000
400 * 100 0.370000 0.410000
400 * 150 0.500000 0.570000
400 * 200 0.830000 0.700000
400 * 250 0.890000 0.680000
400 * 300 0.990000 0.820000
400 * 350 0.970000 0.920000
400 * 400 1.010000 1.130000
450 * 50 0.280000 0.210000
450 * 100 0.450000 0.540000
450 * 150 0.550000 0.600000
450 * 200 0.950000 0.680000
450 * 250 1.080000 0.810000
450 * 300 1.190000 1.120000
450 * 350 1.170000 1.070000
450 * 400 1.070000 1.070000
450 * 450 1.330000 1.190000
500 * 50 0.310000 0.180000
500 * 100 0.490000 0.580000
500 * 150 0.600000 0.710000
500 * 200 0.990000 0.980000
500 * 250 1.300000 0.940000
500 * 300 1.430000 1.180000
500 * 350 1.380000 1.380000
500 * 400 1.580000 1.150000
500 * 450 1.360000 1.380000
500 * 500 1.400000 1.460000
550 * 50 0.420000 0.330000
550 * 100 0.510000 0.700000
550 * 150 0.700000 0.700000
550 * 200 1.130000 1.150000
550 * 250 1.320000 0.940000
550 * 300 1.680000 1.030000
550 * 350 1.480000 1.490000
550 * 400 1.670000 1.240000
550 * 450 1.720000 1.340000
550 * 500 1.460000 1.460000
550 * 550 1.650000 1.730000
600 * 50 0.520000 0.460000
600 * 100 1.070000 0.580000
600 * 150 1.640000 0.720000
600 * 200 1.330000 1.180000
600 * 250 1.550000 1.170000
600 * 300 1.870000 1.160000
600 * 350 1.790000 1.460000
600 * 400 1.840000 1.620000
600 * 450 1.950000 1.650000
600 * 500 1.780000 1.680000
600 * 550 1.800000 1.930000
600 * 600 1.970000 1.940000
650 * 50 0.590000 0.650000
650 * 100 1.210000 0.510000
650 * 150 1.760000 0.870000
650 * 200 2.790000 1.230000
650 * 250 1.740000 1.270000
650 * 300 2.180000 1.480000
650 * 350 2.130000 1.540000
650 * 400 2.160000 1.920000
650 * 450 2.230000 1.880000
650 * 500 2.190000 1.830000
650 * 550 1.960000 1.930000
650 * 600 2.100000 2.110000
650 * 650 2.230000 2.260000
700 * 50 0.730000 0.660000
700 * 100 1.170000 1.160000
700 * 150 1.940000 0.930000
700 * 200 2.810000 1.500000
700 * 250 3.530000 1.430000
700 * 300 2.270000 1.650000
700 * 350 2.360000 1.440000
700 * 400 2.460000 1.880000
700 * 450 2.270000 2.190000
700 * 500 2.040000 2.380000
700 * 550 2.560000 1.970000
700 * 600 2.800000 2.640000
700 * 650 2.490000 2.460000
700 * 700 2.530000 2.430000
750 * 50 0.730000 0.810000
750 * 100 1.380000 1.250000
750 * 150 1.960000 1.780000
750 * 200 3.660000 1.710000
750 * 250 3.880000 1.720000
750 * 300 2.360000 1.960000
750 * 350 2.490000 1.670000
750 * 400 2.530000 1.860000
750 * 450 2.650000 2.210000
750 * 500 2.810000 2.290000
750 * 550 2.770000 2.680000
750 * 600 3.130000 3.070000
750 * 650 3.150000 3.070000
750 * 700 2.860000 2.580000
750 * 750 2.540000 2.710000
800 * 50 0.700000 0.760000
800 * 100 1.540000 1.480000
800 * 150 2.000000 1.960000
800 * 200 3.620000 1.690000
800 * 250 3.980000 1.930000
800 * 300 4.870000 2.260000
800 * 350 3.090000 2.090000
800 * 400 2.770000 1.580000
800 * 450 3.050000 2.290000
800 * 500 3.470000 2.480000
800 * 550 3.370000 2.600000
800 * 600 3.900000 3.390000
800 * 650 4.080000 3.460000
800 * 700 3.460000 3.430000
800 * 750 2.940000 3.160000
800 * 800 2.660000 2.890000
850 * 50 0.790000 0.770000
850 * 100 1.740000 1.370000
850 * 150 2.340000 1.900000
850 * 200 4.060000 3.080000
850 * 250 4.580000 1.920000
850 * 300 5.260000 2.170000
850 * 350 6.120000 2.030000
850 * 400 5.400000 2.390000
850 * 450 3.320000 1.960000
850 * 500 3.650000 2.400000
850 * 550 3.650000 2.900000
850 * 600 4.100000 3.230000
850 * 650 4.240000 4.810000
850 * 700 4.020000 3.740000
850 * 750 3.650000 3.540000
850 * 800 3.090000 3.370000
850 * 850 3.270000 3.620000
900 * 50 0.860000 0.790000
900 * 100 1.690000 1.500000
900 * 150 2.100000 2.140000
900 * 200 4.360000 3.310000
900 * 250 4.850000 2.060000
900 * 300 5.600000 2.670000
900 * 350 5.820000 2.300000
900 * 400 6.260000 2.210000
900 * 450 6.280000 1.990000
900 * 500 3.700000 2.510000
900 * 550 3.720000 2.960000
900 * 600 5.030000 3.470000
900 * 650 4.810000 3.620000
900 * 700 4.310000 5.100000
900 * 750 4.110000 4.260000
900 * 800 4.070000 3.950000
900 * 850 3.960000 3.840000
900 * 900 3.760000 3.850000
950 * 50 0.800000 0.730000
950 * 100 1.930000 1.660000
950 * 150 2.520000 2.400000
950 * 200 4.100000 3.800000
950 * 250 5.140000 4.000000
950 * 300 5.910000 2.430000
950 * 350 6.650000 2.650000
950 * 400 6.780000 2.510000
950 * 450 6.900000 2.290000
950 * 500 7.520000 2.520000
950 * 550 4.320000 2.670000
950 * 600 5.510000 3.680000
950 * 650 5.310000 3.810000
950 * 700 5.190000 5.470000
950 * 750 5.030000 5.460000
950 * 800 4.550000 4.800000
950 * 850 4.820000 4.560000
950 * 900 4.250000 4.140000
950 * 950 3.710000 4.020000
1000 * 50 0.850000 0.930000
1000 * 100 1.920000 1.770000
1000 * 150 2.610000 2.490000
1000 * 200 4.690000 3.830000
1000 * 250 5.500000 4.200000
1000 * 300 6.470000 2.940000
1000 * 350 6.930000 2.900000
1000 * 400 7.110000 2.590000
1000 * 450 7.920000 2.260000
1000 * 500 8.020000 2.290000
1000 * 550 7.880000 3.000000
1000 * 600 6.180000 3.680000
1000 * 650 6.150000 3.910000
1000 * 700 5.730000 4.320000
1000 * 750 5.450000 6.040000
1000 * 800 5.110000 6.090000
1000 * 850 5.480000 5.310000
1000 * 900 5.200000 4.980000
1000 * 950 4.310000 4.530000
1000 * 1000 4.280000 4.270000
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s