bigfft

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%