GitHub - abner-chenc/bigfft: Big integer multiplication library for Go using Fast Fourier transform

abner-chenc / bigfft Public

forked from remyoudompheng/bigfft

Notifications You must be signed in to change notification settings
Fork 0
Star 0

Big integer multiplication library for Go using Fast Fourier transform

BSD-3-Clause license

0 stars 17 forks Branches Tags Activity

Star

Notifications

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 54 Commits
benchmarks		benchmarks
LICENSE		LICENSE
README		README
arith_386.s		arith_386.s
arith_amd64.s		arith_amd64.s
arith_arm.s		arith_arm.s
arith_arm64.s		arith_arm64.s
arith_decl.go		arith_decl.go
arith_loong64.s		arith_loong64.s
arith_mips64x.s		arith_mips64x.s
arith_mipsx.s		arith_mipsx.s
arith_ppc64x.s		arith_ppc64x.s
arith_s390x.s		arith_s390x.s
calibrate_test.go		calibrate_test.go
fermat.go		fermat.go
fermat_test.go		fermat_test.go
fft.go		fft.go
fft_test.go		fft_test.go
go.mod		go.mod
scan.go		scan.go
scan_test.go		scan_test.go

Repository files navigation

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%