Cyclotomic polynomial: Difference between revisions
m
J: remove unnecessary implementation of FFT -- defer to the FFT page for that.
m (J: mention fftw addon) |
m (J: remove unnecessary implementation of FFT -- defer to the FFT page for that.) |
||
Line 2,147:
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 [[j:Essays/FFT|fast fourier transform]] for polynomial multiplication and division.
<lang J>
require'math/fftw'▼
cyclotomic000=: {{ assert.0<y
if. y = 1 do. _1 1 return. end.
'q p'=. __ q: y
Line 2,157 ⟶ 2,160:
,(y%*/q) {."0 cyclotomic */q
else.
lgl=. {:$ ctlist=. cyclotomic "0 }:*/@>,{1,each q NB. ctlist is 2-d table of polynomial divisors
lgd=. # dividend=. _1,(-y){.1 NB. (x^n) - 1, and its size
lg=. >.&.(2&^.) lgl >. lgd NB. required lengths of all polynomials for fft transforms
NB. really, "divisor" is the fft of the divisor!
divisor=. */
unpad roundreal
end.
}}
This
▲roundreal =: [: <. 0.5 + 9&o.</lang>
This approach gave slightly over a
▲This approach for polynomial division is only valid when there's no remainder to be concerned with (which is the case, here).
▲This approach gave slightly over a 2x speedup for <tt>taskorder 10</tt>, from a 2 element cache, with an approximately 50% increased memory footprint. (Remember, of course, that benchmarks and benchmark ratios have dependencies on computer architecture and language implementation, and the host environment.)
▲require'math/fftw'
=={{header|Java}}==
| |||