Cyclotomic polynomial: Difference between revisions
J: FFT speedup for polynomial multiplication and division
(Oops, that last edit was supposed to be a preview, not a save page...) |
(J: FFT speedup for polynomial multiplication and division) |
||
Line 2,142:
9 6545
10 10465</lang>
=== 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 [[j:Essays/FFT|fast fourier transform]] for polynomial multiplication and division.
<lang J>cyclotomic000=: {{ assert.0<y
if. y = 1 do. _1 1 return. end.
'q p'=. __ q: y
if. 1=#q do.
,(y%*/q) {."0 q#1
elseif.2={.q do.
,(y%*/q) {."0 (* 1 _1 $~ #) cyclotomic */}.q
elseif. 1 e. 1 < p do.
,(y%*/q) {."0 ct */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=. */ fft"1 lg{."1 ctlist NB. FFT article doesn't deal with lists of multiplicands
unpad roundreal ifft"1 divisor %~ fft lg{.dividend NB. similar to article's multiplication
end.
}}
NB. discard high order zero coefficients in representation of polynomial
unpad=: {.~ 1+0 i:~0=]
NB. Fast Fourier Transform:
cube =: ($~ q:@#) :. ,
rou =: [: (, j.) [: (, (j.~%:0.5) , |."1&.:+.@|.@}.) [: ^@o.@:j. i.@(%&8) % -: NB. roots of unity
floop =: {{for_r. i.#$x do. (y=.{."1 y) ] x=.(+/x) ,&,:"r (-/x)*y end.}}
fft =: ( ] floop&.cube rou@#) f. :. ifft
ifft =: (# %~ ] floop&.cube +@rou@#) f. :. fft
roundreal =: [: <. 0.5 + 9&o.</lang>
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.)
=={{header|Java}}==
| |||