Discover Packages
github.com/skycoin/cx
goyacc
biggfft
package
Version:
v0.7.5
Opens a new window with list of versions in this module.
Published: Feb 28, 2021
License: BSD-1-Clause, BSD-3-Clause, BSD-2-Clause
Opens a new window with license information.
Imports: 2
Opens a new window with list of imports.
Imported by: 0
Opens a new window with list of known importers.
README
README
¶
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%
Expand ▾
Collapse ▴
Documentation
¶
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.
FromDecimalString converts the base 10 string
representation of a natural (non-negative) number
into a *big.Int.
Its asymptotic complexity is less than quadratic.
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.
Source Files
¶
Click to show internal directories.
Click to hide internal directories.