From 1a57267a17c2fc17fb6e104846fabc3e363c326c Mon Sep 17 00:00:00 2001 From: Emile Date: Fri, 16 Aug 2024 19:50:26 +0200 Subject: initial commit --- vendor/github.com/remyoudompheng/bigfft/README | 54 ++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) create mode 100644 vendor/github.com/remyoudompheng/bigfft/README (limited to 'vendor/github.com/remyoudompheng/bigfft/README') diff --git a/vendor/github.com/remyoudompheng/bigfft/README b/vendor/github.com/remyoudompheng/bigfft/README new file mode 100644 index 0000000..0fcd39d --- /dev/null +++ b/vendor/github.com/remyoudompheng/bigfft/README @@ -0,0 +1,54 @@ +This library is a toy proof-of-concept implementation of the +well-known Schonhage-Strassen method for multiplying integers. +It is not expected to have a real life usecase outside number +theory computations, nor is it expected to be used in any production +system. + +If you are using it in your project, you may want to carefully +examine the actual requirement or problem you are trying to solve. + +# Comparison with the standard library and GMP + +Benchmarking math/big vs. bigfft + +Number size old ns/op new ns/op delta + 1kb 1599 1640 +2.56% + 10kb 61533 62170 +1.04% + 50kb 833693 831051 -0.32% +100kb 2567995 2693864 +4.90% + 1Mb 105237800 28446400 -72.97% + 5Mb 1272947000 168554600 -86.76% + 10Mb 3834354000 405120200 -89.43% + 20Mb 11514488000 845081600 -92.66% + 50Mb 49199945000 2893950000 -94.12% +100Mb 147599836000 5921594000 -95.99% + +Benchmarking GMP vs bigfft + +Number size GMP ns/op Go ns/op delta + 1kb 536 1500 +179.85% + 10kb 26669 50777 +90.40% + 50kb 252270 658534 +161.04% +100kb 686813 2127534 +209.77% + 1Mb 12100000 22391830 +85.06% + 5Mb 111731843 133550600 +19.53% + 10Mb 212314000 318595800 +50.06% + 20Mb 490196000 671512800 +36.99% + 50Mb 1280000000 2451476000 +91.52% +100Mb 2673000000 5228991000 +95.62% + +Benchmarks were run on a Core 2 Quad Q8200 (2.33GHz). +FFT is enabled when input numbers are over 200kbits. + +Scanning large decimal number from strings. +(math/big [n^2 complexity] vs bigfft [n^1.6 complexity], Core i5-4590) + +Digits old ns/op new ns/op delta +1e3 9995 10876 +8.81% +1e4 175356 243806 +39.03% +1e5 9427422 6780545 -28.08% +1e6 1776707489 144867502 -91.85% +2e6 6865499995 346540778 -94.95% +5e6 42641034189 1069878799 -97.49% +10e6 151975273589 2693328580 -98.23% + -- cgit 1.4.1