Skip to content

Commit 04a3392

Browse files
authored
Merge pull request cp-algorithms#739 from shoryak/master
fixes typo in fft.md
2 parents 479a02f + a441c36 commit 04a3392

1 file changed

Lines changed: 1 addition & 1 deletion

File tree

src/algebra/fft.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ Notice, that the FFT algorithm presented here runs in $O(n \log n)$ time, but it
1313
It can easily handle polynomials of size $10^5$ with small coefficients, or multiplying two numbers of size $10^6$, but at some point the range and the precision of the used floating point numbers will not no longer be enough to give accurate results.
1414
That is usually enough for solving competitive programming problems, but there are also more complex variations that can perform arbitrary large polynomial/integer multiplications.
1515
E.g. in 1971 Schönhage and Strasser developed a variation for multiplying arbitrary large numbers that applies the FFT recursively in rings structures running in $O(n \log n \log \log n)$.
16-
And recently (in 2019) Harvey and van der Hoeven published an algorithm that runs in true $O(\log n)$.
16+
And recently (in 2019) Harvey and van der Hoeven published an algorithm that runs in true $O(n \log n)$.
1717

1818
## Discrete Fourier transform
1919

0 commit comments

Comments
 (0)