1 files changed, 54 insertions, 0 deletions
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%
+