Cyclotomic polynomial: Difference between revisions
Content added Content deleted
m (J: remove unnecessary implementation of FFT -- defer to the FFT page for that.) |
m (J: fft reference should be to rosettacode page, details can be handled there, also add missing </lang> tag) |
||
| Line 2,145: | Line 2,145: | ||
=== Another approach === |
=== Another approach === |
||
As noted in the [http://jsoftware.com/pipermail/programming/2022-March/060209.html J programming forum], we can improve the big-O character of this algorithm by using the [[ |
As noted in the [http://jsoftware.com/pipermail/programming/2022-March/060209.html J programming forum], we can improve the big-O character of this algorithm by using the [[Fast Fourier transform]] for polynomial multiplication and division. |
||
<lang J>NB. install'math/fftw' |
<lang J>NB. install'math/fftw' |
||
| Line 2,169: | Line 2,169: | ||
}} |
}} |
||
roundreal =: [: <. 0.5 + 9&o. |
roundreal =: [: <. 0.5 + 9&o.</lang> |
||
This variation for polynomial division is only valid when there's no remainder to be concerned with (which is the case, here). |
This variation for polynomial division is only valid when there's no remainder to be concerned with (which is the case, here). |
||