Allan Steel (July 1, 2005)

**NOTE** (20/4/06):
This page is now historical. I would have removed it after it became
obsolete, but apparently it gets many hits via published reference,
so it is better to keep it so as to make clear what it was demonstrating
originally and accurately. Objective evaluation of software
(with completely natural input parameters) is surely preferable
to childish (and completely misguided)
taunts in officially published material.

When written, this page compared the official releases of Magma and GMP, as they were in July 2005. Since April 20, 2006 (version 2.12-21 and onwards), Magma now links in GMP 4.2 (March 2006), according to the LGPL. The FFT-based multiplication code has been improved in GMP 4.2 (but Magma 2.12-21 still calls its independent FFT code when it is faster for large integer multiplication, or when multiplying polynomials via the direct-FFT method).

(July 1, 2005)

Magma V2.12-1 (released in July 2005) contains new FFT code for large integer multiplication. This is faster in general than the GMP 4.1.4 large integer FFT multiplication code, as the following tables show.

For each table line, the times are given for multiplying two random integers with the given number of bits in GMP 4.1.4 and Magma V2.12-1. Note that as one increases the bit lengths between powers of two, the timings can jump in non-smooth patterns in both GMP and Magma (because of the nature of the FFT algorithm), but Magma remains faster than GMP for all non-power-of-2 bit lengths tried on the processors listed here.

Multiplication of very large integers has many applications. In particular, one can multiply polynomials over the integers by using the Kronecker-Schoenhage method (also known as segmentation), whereby one evaluates the polynomials at an appropriate power of two B, multiplies the resulting integers, and expands the integer product in base B to obtain the polynomial product.

Magma V2.12-1 not only uses the Kronecker-Schoenhage method when applicable, but also has a direct FFT polynomial multiplication method, which can be even faster (the appropriate method is selected automatically). For example, on an Opteron 150 (2.4GHz) Magma V2.12-1 can multiply two polynomials, each having degree 1000 and 1000-bit integer coefficients, in 0.0125 secs using the direct polynomial FFT method, compared with 0.0307 secs using the Kronecker-Schoenhage method (which involves multiplying two integers close to 2^21 bits each plus the extra overhead of the polynomial expansion and contraction, so is slightly slower than the 2^21-bits Magma timing in the table below).

Note: Magma uses GMP (according to the LGPL) for small- and moderately-sized integer multiplication, since GMP has excellent machine language code for most processors. This GMP multiplication code is simply called via an externally-linked GMP library. The FFT-based multiplication code in Magma for very large integer multiplication is completely independent of the GMP FFT-based multiplication code, and this page simply compares these two implementations of large integer multiplication algorithms.

NB: Both the GMP and the Magma timings here use the AMD64 assembly code of Pierrick Gaudry for the base operations (which is is vastly superior to the official GMP 4.1.4 running on AMD64 processors).

Bits | GMP | Magma | Speedup |
---|---|---|---|

2^18 | 0.00338 | 0.00238 | 1.42 |

2^19 | 0.00984 | 0.00531 | 1.85 |

2^20 | 0.0225 | 0.0114 | 1.97 |

2^21 | 0.0539 | 0.0274 | 1.96 |

2^22 | 0.119 | 0.0592 | 2.01 |

2^23 | 0.286 | 0.132 | 2.17 |

2^24 | 0.630 | 0.300 | 2.10 |

2^25 | 1.51 | 0.640 | 2.36 |

2^26 | 3.19 | 1.56 | 2.04 |

2^27 | 6.96 | 3.30 | 2.11 |

2^28 | 15.27 | 8.54 | 1.79 |

2^29 | 33.04 | 17.67 | 1.87 |

Bits | GMP | Magma | Speedup |
---|---|---|---|

2^17 | 0.00530 | 0.00445 | 1.19 |

2^18 | 0.0126 | 0.00806 | 1.56 |

2^19 | 0.0316 | 0.0191 | 1.66 |

2^20 | 0.0804 | 0.0400 | 2.01 |

2^21 | 0.164 | 0.0890 | 1.84 |

2^22 | 0.408 | 0.205 | 1.99 |

2^23 | 0.965 | 0.425 | 2.27 |

2^24 | 1.90 | 1.17 | 1.62 |

2^25 | 3.78 | 2.47 | 1.53 |

2^26 | 7.98 | 5.78 | 1.38 |

2^27 | 18.14 | 12.15 | 1.49 |

2^28 | 38.54 | 30.88 | 1.25 |

2^29 | 98.54 | 65.51 | 1.50 |

Bits | GMP | Magma | Speedup |
---|---|---|---|

2^18 | 0.01034 | 0.00572 | 1.81 |

2^19 | 0.0220 | 0.0126 | 1.75 |

2^20 | 0.0482 | 0.0270 | 1.79 |

2^21 | 0.110 | 0.0581 | 1.89 |

2^22 | 0.266 | 0.132 | 2.01 |

2^23 | 0.598 | 0.320 | 1.87 |

2^24 | 1.60 | 0.782 | 2.04 |

2^25 | 3.08 | 1.70 | 1.81 |

2^26 | 6.66 | 4.33 | 1.54 |

2^27 | 14.18 | 8.89 | 1.59 |

2^28 | 30.55 | 23.34 | 1.31 |

2^29 | 69.96 | 48.46 | 1.44 |

Bits | GMP | Magma | Speedup |
---|---|---|---|

2^18 | 0.0359 | 0.0196 | 1.83 |

2^19 | 0.0814 | 0.0425 | 1.92 |

2^20 | 0.197 | 0.0946 | 2.08 |

2^21 | 0.415 | 0.203 | 2.04 |

2^22 | 1.07 | 0.498 | 2.15 |

2^23 | 2.34 | 1.06 | 2.22 |

2^24 | 4.98 | 2.87 | 1.74 |

2^25 | 10.24 | 6.08 | 1.68 |

2^26 | 23.03 | 15.85 | 1.45 |

2^27 | 51.43 | 32.80 | 1.57 |

2^28 | 112.90 | 85.04 | 1.33 |

2^29 | 254.18 | 175.03 | 1.45 |