| 1 | This library is a toy proof-of-concept implementation of the
|
|---|
| 2 | well-known Schonhage-Strassen method for multiplying integers.
|
|---|
| 3 | It is not expected to have a real life usecase outside number
|
|---|
| 4 | theory computations, nor is it expected to be used in any production
|
|---|
| 5 | system.
|
|---|
| 6 |
|
|---|
| 7 | If you are using it in your project, you may want to carefully
|
|---|
| 8 | examine the actual requirement or problem you are trying to solve.
|
|---|
| 9 |
|
|---|
| 10 | # Comparison with the standard library and GMP
|
|---|
| 11 |
|
|---|
| 12 | Benchmarking math/big vs. bigfft
|
|---|
| 13 |
|
|---|
| 14 | Number size old ns/op new ns/op delta
|
|---|
| 15 | 1kb 1599 1640 +2.56%
|
|---|
| 16 | 10kb 61533 62170 +1.04%
|
|---|
| 17 | 50kb 833693 831051 -0.32%
|
|---|
| 18 | 100kb 2567995 2693864 +4.90%
|
|---|
| 19 | 1Mb 105237800 28446400 -72.97%
|
|---|
| 20 | 5Mb 1272947000 168554600 -86.76%
|
|---|
| 21 | 10Mb 3834354000 405120200 -89.43%
|
|---|
| 22 | 20Mb 11514488000 845081600 -92.66%
|
|---|
| 23 | 50Mb 49199945000 2893950000 -94.12%
|
|---|
| 24 | 100Mb 147599836000 5921594000 -95.99%
|
|---|
| 25 |
|
|---|
| 26 | Benchmarking GMP vs bigfft
|
|---|
| 27 |
|
|---|
| 28 | Number size GMP ns/op Go ns/op delta
|
|---|
| 29 | 1kb 536 1500 +179.85%
|
|---|
| 30 | 10kb 26669 50777 +90.40%
|
|---|
| 31 | 50kb 252270 658534 +161.04%
|
|---|
| 32 | 100kb 686813 2127534 +209.77%
|
|---|
| 33 | 1Mb 12100000 22391830 +85.06%
|
|---|
| 34 | 5Mb 111731843 133550600 +19.53%
|
|---|
| 35 | 10Mb 212314000 318595800 +50.06%
|
|---|
| 36 | 20Mb 490196000 671512800 +36.99%
|
|---|
| 37 | 50Mb 1280000000 2451476000 +91.52%
|
|---|
| 38 | 100Mb 2673000000 5228991000 +95.62%
|
|---|
| 39 |
|
|---|
| 40 | Benchmarks were run on a Core 2 Quad Q8200 (2.33GHz).
|
|---|
| 41 | FFT is enabled when input numbers are over 200kbits.
|
|---|
| 42 |
|
|---|
| 43 | Scanning large decimal number from strings.
|
|---|
| 44 | (math/big [n^2 complexity] vs bigfft [n^1.6 complexity], Core i5-4590)
|
|---|
| 45 |
|
|---|
| 46 | Digits old ns/op new ns/op delta
|
|---|
| 47 | 1e3 9995 10876 +8.81%
|
|---|
| 48 | 1e4 175356 243806 +39.03%
|
|---|
| 49 | 1e5 9427422 6780545 -28.08%
|
|---|
| 50 | 1e6 1776707489 144867502 -91.85%
|
|---|
| 51 | 2e6 6865499995 346540778 -94.95%
|
|---|
| 52 | 5e6 42641034189 1069878799 -97.49%
|
|---|
| 53 | 10e6 151975273589 2693328580 -98.23%
|
|---|
| 54 |
|
|---|
