Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

math/big: Implement fft algorithm #42267

Open
SparrowLii opened this issue Oct 29, 2020 · 5 comments
Open

math/big: Implement fft algorithm #42267

SparrowLii opened this issue Oct 29, 2020 · 5 comments

Comments

@SparrowLii
Copy link
Contributor

@SparrowLii SparrowLii commented Oct 29, 2020

From #30943. I think it's time for us to add fft to the big package. This implements Schönhage–Strassen algorithm in math/big and increased the multiplication speed several times to tens of times (depending on the length of the input). Although it is still not as fast as in GMP( which uses an advanced and more complex algorithm), it should solve the bottleneck of Go in multiplication of very large numbers(#30943, for example).
The benchmark test data is as follows:
Mul-4 12.5ms ± 1% 6.9ms ± 3% -45.08% (p=0.016 n=4+5)
NatMul/10-4 251ns ± 3% 267ns ± 6% +6.28% (p=0.008 n=5+5)
NatMul/100-4 8.64µs ± 3% 8.80µs ± 1% ~ (p=0.310 n=5+5)
NatMul/1000-4 358µs ± 5% 355µs ± 3% ~ (p=0.841 n=5+5)
NatMul/10000-4 12.6ms ± 2% 7.0ms ± 5% -44.11% (p=0.008 n=5+5)
NatMul/100000-4 545ms ± 4% 90ms ± 3% -83.43% (p=0.008 n=5+5)
NatMul/1000000-4 21.2s ± 2% 1.2s ± 4% -94.33% (p=0.008 n=5+5)

@gopherbot
Copy link

@gopherbot gopherbot commented Oct 29, 2020

Change https://golang.org/cl/266201 mentions this issue: math/big: implement Schönhage–Strassen fft algorithm

Loading

@SparrowLii
Copy link
Contributor Author

@SparrowLii SparrowLii commented Oct 29, 2020

@bmkessler Hi brain, could you help looking it? @griesemer

Loading

@advancedwebdeveloper
Copy link

@advancedwebdeveloper advancedwebdeveloper commented Oct 29, 2020

@dcmartin , could give an advice here?

Loading

@andig
Copy link
Contributor

@andig andig commented Oct 13, 2021

Seems comments have been addressed- what's missing for merging?

Loading

@griesemer
Copy link
Contributor

@griesemer griesemer commented Oct 13, 2021

This probably could use another round of reviews. This is a complex algorithm and the chance for subtle bugs is high, possibly security critical. The Go team is currently pre-occupied with the Go 1.18 release.

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants