bigfft

README

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%

Documentation

Overview

Package bigfft implements multiplication of big.Int using FFT.

The implementation is based on the Schönhage-Strassen method using integer FFT modulo 2^n+1.

Index

• func FromDecimalString(s string) *big.Int
• func Mul(x, y *big.Int) *big.Int
• type Word

Functions

func FromDecimalString

func FromDecimalString(s string) *big.Int

FromDecimalString converts the base 10 string representation of a natural (non-negative) number into a *big.Int. Its asymptotic complexity is less than quadratic.

func Mul

func Mul(x, y *big.Int) *big.Int

Mul computes the product x*y and returns z. It can be used instead of the Mul method of *big.Int from math/big package.

Types

type Word

type Word = big.Word