| Conclusions | Source code | Download |
Factorial Benchmark
Note that this benchmark and the tables were made with the program SilverFactorial. You can download this program and the sources from GitHub. The implementations of the algorithms can be seen here.
MPIR Factorial Benchmark (2013)
CPU: AMD Athlon II X4 640, 3.0 GHz, RAM: 4.0 GB, OS: Ubuntu 12.04 (64 bit)
C++ and MPIR-2.6.0 Factorial Benchmark (Mar 01 2013)
| (N x 10^6) ! | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 100 |
| ParallelPrimeSwing | 0.25 | 0.60 | 1.35 | 2.98 | 6.58 | 14.43 | 31.40 | 53.80 |
| ParallelPrimeSchoenhage | 0.25 | 0.60 | 1.35 | 3.10 | 6.91 | 15.32 | 33.54 | 57.58 |
| PrimeSwing | 0.22 | 0.58 | 1.36 | 3.15 | 7.10 | 15.83 | 34.80 | 59.98 |
| PrimeSchoenhage | 0.23 | 0.58 | 1.37 | 3.17 | 7.14 | 15.90 | 34.97 | 60.06 |
| MPIR-Library | 0.23 | 0.58 | 1.37 | 3.21 | 7.21 | 16.05 | 35.26 | 60.63 |
- Overall about 10% faster compared to the 2011 (MPIR-2.4.0) benchmark.
- For values n ≤ 2*10^6 the parallel versions do not pay anything, quite the opposite.
- PrimeSwing seems to be better suited for parallelization than PrimeSchoenhage.
Silver Factorial Benchmark (2013)
CPU: AMD Athlon II X4 640, 3.0 GHz, RAM: 4.0 GB, OS: Win 7 (64 bit)
C# + MPIR-2.6.0 Factorial Benchmark (Mar 01 2013)
Prime based factorials
Timings (in seconds)
| n! where n = | 160000 | 320000 | 640000 | 1280000 | 2560000 | 5120000 | 10240000 |
| ParallelSplitPrimeSwing | 0,04 | 0,07 | 0,17 | 0,37 | 0,76 | 1,85 | 4,66 |
| ParallelPrimeSwing | 0,04 | 0,08 | 0,15 | 0,38 | 0,89 | 1,94 | 5,46 |
| ParallelPrimeSplit | 0,05 | 0,07 | 0,19 | 0,40 | 0,79 | 1,90 | 4,44 |
| PrimeSwingList | 0,03 | 0,08 | 0,19 | 0,45 | 0,96 | 2,15 | 5,24 |
| PrimeSwing | 0,03 | 0,10 | 0,23 | 0,43 | 0,95 | 2,22 | 5,36 |
| PrimeShoenhage | 0,06 | 0,08 | 0,19 | 0,44 | 0,99 | 2,24 | 5,33 |
The smaller the value the better.
Red = best, blue = second.
Time-ranking relative to 'ParallelPrimeSwing'
| n! where n = | 160000 | 320000 | 640000 | 1280000 | 2560000 | 5120000 | 10240000 |
| ParallelSplitPrimeSwing | 1,19 | 0,88 | 1,18 | 0,99 | 0,85 | 0,95 | 0,85 |
| ParallelPrimeSwing | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 |
| ParallelPrimeSplit | 1,36 | 0,88 | 1,32 | 1,07 | 0,89 | 0,98 | 0,81 |
| PrimeSwingList | 0,81 | 0,99 | 1,32 | 1,19 | 1,08 | 1,11 | 0,96 |
| PrimeSwing | 0,81 | 1,21 | 1,56 | 1,15 | 1,07 | 1,14 | 0,98 |
| PrimeShoenhage | 1,78 | 1,00 | 1,32 | 1,18 | 1,12 | 1,16 | 0,98 |
The smaller the value the better.
Red values <= 1 indicate excellent performance,
Blue values <= 2 indicate good performance.
Efficiency (decimal digits per millisecond)
| n! where n = | 160000 | 320000 | 640000 | 1280000 | 2560000 | 5120000 | 10240000 |
| ParallelSplitPrimeSwing | 17748 | 21928 | 19759 | 19572 | 20203 | 17404 | 14453 |
| ParallelPrimeSwing | 21199 | 19318 | 23388 | 19312 | 17242 | 16561 | 12344 |
| ParallelPrimeSplit | 15575 | 21928 | 17722 | 18018 | 19310 | 16909 | 15159 |
| PrimeSwingList | 26316 | 19550 | 17722 | 16245 | 15914 | 14978 | 12843 |
| PrimeSwing | 26316 | 15909 | 15013 | 16770 | 16064 | 14472 | 12563 |
| PrimeShoenhage | 11925 | 19318 | 17722 | 16354 | 15401 | 14330 | 12639 |
The larger the value the better.
Red = best, blue = second.
Ranking by average efficiency in the test range
| Algorithm | Average Efficiency |
| ParallelSplitPrimeSwing | 18723 |
| ParallelPrimeSwing | 18480 |
| ParallelPrimeSplit | 17803 |
| PrimeSwingList | 17652 |
| PrimeSwing | 16729 |
| PrimeShoenhage | 15384 |
The larger the value the better.
- The three top performer are ParallelPrimeSwing, ParallelPrimeSplit and ParallelSplitPrimeSwing.
- There is no definitive winner in this category, my recommendation goes for now with the simpler ParallelPrimeSwing although theoretically ParallelSplitPrimeSwing should take the lead for very large values; things depend much on the threading model and its implementation.
Simple factorial functions
(ParallelPrimeSwing is included in the tables only for
the purpose of comparison.)
Timings (in seconds)
| n! where n = | 160000 | 320000 | 640000 | 1280000 | 2560000 | 5120000 | 10240000 |
| ParallelPrimeSwing | 0,06 | 0,13 | 0,17 | 0,40 | 0,81 | 2,19 | 5,25 |
| ParallelSwing | 0,06 | 0,19 | 0,50 | 1,07 | 2,35 | 5,31 | 11,68 |
| Swing | 0,06 | 0,23 | 0,52 | 1,20 | 2,65 | 5,78 | 13,19 |
| Split | 0,17 | 0,38 | 0,70 | 1,62 | 3,34 | 7,18 | 15,72 |
| SquaredDiffProd | 0,21 | 0,36 | 0,80 | 1,50 | 3,26 | 6,98 | 14,27 |
| Balkan | 0,26 | 0,36 | 0,80 | 1,67 | 3,26 | 6,79 | 14,08 |
The smaller the value the better.
Red = best, blue = second.
Time-ranking relative to 'ParallelPrimeSwing'
| n! where n = | 160000 | 320000 | 640000 | 1280000 | 2560000 | 5120000 | 10240000 |
| ParallelPrimeSwing | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 | 1,00 |
| ParallelSwing | 0,98 | 1,53 | 2,88 | 2,70 | 2,90 | 2,43 | 2,23 |
| Swing | 1,11 | 1,80 | 3,02 | 3,04 | 3,27 | 2,64 | 2,51 |
| Split | 3,02 | 3,01 | 4,06 | 4,09 | 4,12 | 3,28 | 3,00 |
| SquaredDiffProd | 3,66 | 2,83 | 4,66 | 3,80 | 4,02 | 3,19 | 2,72 |
| Balkan | 4,57 | 2,82 | 4,63 | 4,22 | 4,03 | 3,10 | 2,68 |
The smaller the value the better.
Red values <= 1 indicate excellent performance,
Blue values <= 2 indicate good performance.
Efficiency (decimal digits per millisecond)
| n! where n = | 160000 | 320000 | 640000 | 1280000 | 2560000 | 5120000 | 10240000 |
| ParallelPrimeSwing | 13628 | 12777 | 19988 | 18337 | 18881 | 14670 | 12831 |
| ParallelSwing | 13876 | 8364 | 6945 | 6780 | 6505 | 6048 | 5766 |
| Swing | 12309 | 7086 | 6612 | 6036 | 5771 | 5558 | 5106 |
| Split | 4516 | 4248 | 4918 | 4485 | 4580 | 4478 | 4284 |
| SquaredDiffProd | 3723 | 4520 | 4292 | 4828 | 4697 | 4605 | 4718 |
| Balkan | 2981 | 4533 | 4319 | 4340 | 4687 | 4730 | 4782 |
The larger the value the better.
Red = best, blue = second.
Ranking by average efficiency in the test range
| Algorithm | Average Efficiency |
| ParallelPrimeSwing | 15873 |
| ParallelSwing | 7754 |
| Swing | 6925 |
| Split | 4501 |
| SquaredDiffProd | 4483 |
| Balkan | 4338 |
The larger the value the better.
- In this category we have a definitive winner: Swing! Choose ParallelSwing on a multi-core machine or for large values and Swing on a machine with a single-core processor or for small values. Second-placed are Split, Balkan and SquaredDiffProd. Balkan is a new (2013) algorithm by F. Cihana, F. Aydinb and A. F. Kocamaz. I was not able to reproduce the benchmark results of these authors and suspect that they are based on Microsoft's BigInteger library, which is totally inapt for such a benchmark as this library is not based on the fast arithmetical algorithms which are implemented in MPIR and GMP.
MPIR Factorial Benchmark (2011)
CPU: AMD Athlon II X4 640, 3.0 GHz, RAM: 4.0 GB, OS: Win 7 (64 bit)
MPIR-2.4.0 Factorial Benchmark (Jun 14 2011)
| (N x 10^6) ! | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 100 |
| ParallelPrimeSwing | 0.25 | 0.58 | 1.70 | 3.81 | 7.85 | 16.69 | 35.86 | 56.92 |
| ParallelPrimeSchoenhage | 0.25 | 0.62 | 1.83 | 4.10 | 8.50 | 18.21 | 38.86 | 62.03 |
| PrimeSwing | 0.28 | 0.66 | 1.92 | 4.21 | 8.81 | 18.86 | 41.62 | 65.01 |
| PrimeSchoenhage | 0.27 | 0.66 | 1.92 | 4.24 | 8.89 | 18.95 | 40.67 | 65.33 |
| MPIR-Library | 0.27 | 0.66 | 1.90 | 4.26 | 8.89 | 19.06 | 41.03 | 66.16 |
MPIR Factorial Benchmark (2010)
CPU: AMD 64 X2 Dual Core 4400, 2.31 GHz, RAM: 2.0 GB, OS: Win XP (32 bit)
MPIR-1.3.0 Factorial Benchmark (Jan 29 2010)
| (N x 10^6) ! | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 100 |
| ParallelPrimeSwing | 0.9 | 1.9 | 4.2 | 9.2 | 20.6 | 45.5 | 101.8 | 181.1 |
| ParallelPrimeSchoenhage | 0.9 | 2.1 | 4.6 | 10.2 | 22.6 | 50.2 | 112.1 | 197.4 |
| PrimeSwing | 1.0 | 2.1 | 4.8 | 10.7 | 23.9 | 53.1 | 118.9 | 209.0 |
| PrimeSchoenhage | 1.0 | 2.1 | 4.8 | 10.7 | 23.9 | 53.2 | 119.0 | 209.2 |
| MPIR-Library | 1.0 | 2.2 | 4.8 | 10.7 | 24.1 | 53.4 | 119.3 | 209.6 |
GMP-5.0.1 Factorial Benchmark (Feb 07 2010)
| (N x 10^6) ! | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 100 |
| ParallelPrimeSwing | 0.8 | 1.9 | 4.6 | 10.9 | 25.0 | 58.1 | 129.7 | 218.5 |
| ParallelPrimeSchoenhage | 0.9 | 2.2 | 5.1 | 11.9 | 27.1 | 62.9 | 140.3 | 237.1 |
| PrimeSwing | 0.9 | 2.2 | 5.2 | 12.4 | 28.3 | 65.5 | 146.9 | 249.5 |
| PrimeSchoenhage | 0.9 | 2.2 | 5.3 | 12.4 | 28.4 | 65.8 | 147.2 | 249.7 |
| GMP-Library | 1.6 | 3.7 | 9.3 | 21.8 | 51.2 | 117.9 | 276.9 | 468.7 |
Note that this benchmark only compares a tiny fraction of the two multiple precision libraries. It compares the factorial function as provided by the libraries and it compares how some factorial functions implemented on the more basic functions of the libraries perform. So basically only the multiplication algorithms are tested. GMP 5.0.1 performs relatively poor compared to MPIR-1.3.0. It might be the case that earlier versions of GMP perform better. However, I did not test this. (I know that the developers of GMP are hard working to improve things.)
The following plot sums our findings up. It shows in units of [dd/ms] (decimal digits per millisecond) the performance of ParallelPrimeSwing (red) with MPIR 1.3.0 and the GMP library function (blue) in the region tested (higher figures are better here).
PPSMPIR := listplot([[1,6472],[2,6157],[4,5935],[8,5624],[16,5256],[32,4970],[64,4635],[100,4178]],color=red): LIBGMP := listplot([[1,3525],[2,3142],[4,2663],[8,2376],[16,2114],[32,1920],[64,1705],[100,1615]],color=blue):
You might also be interested to compare different implementations of the double factorial function. On that page you can also find the source code (see the class diagram below) of the above benchmark. Benchmark yourself on your favorite system!
MPIR Binomial Benchmark (2011)
CPU: AMD Athlon II X4 640, 3.0 GHz, RAM: 4.0 GB, OS: Win 7 (64 bit)
MPIR-2.4.0 Factorial Benchmark (Jun 14 2011)
Testing binomial: 100000, 33333 ParallelBinomial: 0.001 sec PrimeBinomial: 0.001 sec MPIR-Binomial: 0.037 sec Testing binomial: 200000, 66666 ParallelBinomial: 0.003 sec PrimeBinomial: 0.003 sec MPIR-Binomial: 0.177 sec Testing binomial: 400000, 133333 ParallelBinomial: 0.005 sec PrimeBinomial: 0.006 sec MPIR-Binomial: 0.710 sec Testing binomial: 800000, 266666 ParallelBinomial: 0.010 sec PrimeBinomial: 0.014 sec MPIR-Binomial: 2.842 sec Testing binomial: 1600000, 533333 ParallelBinomial: 0.022 sec PrimeBinomial: 0.033 sec MPIR-Binomial: 11.39 sec Testing binomial: 3200000, 1066666 ParallelBinomial: 0.051 sec PrimeBinomial: 0.076 sec MPIR-Binomial: 45.57 sec Testing binomial: 6400000, 2133333 ParallelBinomial: 0.117 sec PrimeBinomial: 0.179 sec MPIR-Binomial: 333.4 sec
You can download the source code here.
Java Factorial Benchmark (2011)
Java 1.6.0_25 Sun VM server (64 bit)
Arithmetic: Apfloat Library 1.6.2
by Mikko Tommila
CPU: AMD Athlon II X4 640, 3.0 GHz, RAM: 4.0 GB, OS: Win 7 (64 bit)
You can download the source code here.
Timings (seconds)
| (N x 10^6)! | 1 | 2 | 4 | 8 | 16 | 32 |
| ParallelPrimeSwing | 2,3 | 3,4 | 6,8 | 14,4 | 30,4 | 61,7 |
| ParallelPrimeSplit | 1,8 | 3,4 | 7,0 | 14,5 | 29,8 | 63,4 |
| PrimeSchoenhage | 1,9 | 4,2 | 8,7 | 18,1 | 37,6 | 79,6 |
| PrimeSwingList | 1,9 | 4,4 | 8,7 | 19,1 | 38,3 | 80,7 |
| PrimeSwing | 2,1 | 4,6 | 8,8 | 19,3 | 40,2 | 84,5 |
| PrimeVardi | 2,0 | 4,5 | 9,0 | 19,9 | 40,1 | 82,8 |
| ParallelSplit | 3,8 | 8,1 | 17,2 | 38,0 | 72,8 | 149,1 |
| ParallelSwing | 4,0 | 8,9 | 18,3 | 39,5 | 77,8 | 158,8 |
| Split | 6,0 | 13,4 | 27,5 | 90,5 | 121,9 | 234,3 |
| Swing | 6,6 | 14,4 | 31,3 | 69,4 | 134,4 | 255,9 |
Ranking relative to PrimeSwing
| (N x 10^6)! | 1 | 2 | 4 | 8 | 16 | 32 |
| ParallelPrimeSwing | 1,1 | 0,7 | 0,8 | 0,7 | 0,8 | 0,7 |
| ParallelPrimeSplit | 0,9 | 0,7 | 0,8 | 0,8 | 0,7 | 0,8 |
| PrimeSchoenhage | 0,9 | 0,9 | 1,0 | 0,9 | 0,9 | 0,9 |
| PrimeSwingList | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 |
| PrimeSwing | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 |
| PrimeVardi | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 |
| ParallelSplit | 1,8 | 1,8 | 1,9 | 2,0 | 1,8 | 1,8 |
| ParallelSwing | 2,0 | 1,9 | 2,1 | 2,0 | 1,9 | 2,0 |
| Split | 2,9 | 2,9 | 3,1 | 4,7 | 3,0 | 2,8 |
| Swing | 3,2 | 3,1 | 3,5 | 3,6 | 3,3 | 3,0 |
Timing: Red = first, blue = second.
Ranking: The smaller the value the better.
Values p <= 1 (red) indicate excellent performance,
values p <= 2 (blue) indicate good performance.
Java Factorial Benchmark (2009)
Java 1.7.0 Sun VM server (32 bit)
Arithmetic: Apfloat Library 1.5.2
(int32-based) by Mikko Tommila
CPU: AMD 64 X2 Dual, 2.3 GHz, RAM: 2.0 GB, OS: Win XP (32 bit)
Timings (seconds)
| (N x 10^6) ! | 1 | 2 | 4 | 8 | 16 | 32 |
| ParallelPrimeSwing | 4,2 | 8,5 | 18,1 | 39,1 | 84,5 | 174,7 |
| ParallelPrimeSplit | 4,3 | 9,1 | 18,8 | 40,0 | 101,1 | 180,1 |
| PrimeSwing | 4,3 | 9,5 | 20,1 | 49,0 | 106,8 | 192,2 |
| PrimeSchoenhage | 4,3 | 9,6 | 20,6 | 43,5 | 104,0 | 197,4 |
| PrimeVardi | 4,4 | 9,8 | 20,7 | 43,8 | 102,6 | 195,0 |
| PrimeSwingList | 4,4 | 9,8 | 20,7 | 44,1 | 104,0 | 199,4 |
| ParallelSplit | 6,9 | 15,0 | 33,3 | 80,2 | 188,2 | 366,8 |
| ParallelSwing | 8,8 | 18,7 | 40,6 | 88,2 | 224,6 | 425,0 |
| Split | 9,5 | 20,8 | 44,8 | 97,1 | 211,0 | 460,1 |
Ranking relative to PrimeSwing
| (N x 10^6) ! | 1 | 2 | 4 | 8 | 16 | 32 |
| ParallelPrimeSwing | 0,9 | 0,9 | 0,9 | 0,9 | 0,9 | 0,9 |
| ParallelPrimeSplit | 1,0 | 0,9 | 0,9 | 0,9 | 0,9 | 0,9 |
| PrimeSwing | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 |
| PrimeSchoenhage | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 |
| PrimeVardi | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 |
| PrimeSwingList | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 | 1,0 |
| ParallelSplit | 1,7 | 1,6 | 1,6 | 1,7 | 1,9 | 1,9 |
| ParallelSwing | 2,0 | 2,0 | 2,0 | 2,1 | 2,2 | 2,2 |
| Split | 2,2 | 2,2 | 2,2 | 2,2 | 2,4 | 2,4 |