Cyclotomic polynomial: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|C sharp}}: Regularize header markup to recommended on category page) |
(J) |
||
Line 2,012: | Line 2,012: | ||
Computations take a while... |
Computations take a while... |
||
=={{header|J}}== |
|||
Implementation of routine to find nth cyclotomic polynomial: |
|||
<lang J>{{ if.0>nc<'cache' do.cache=:y end.}} a:;_1 1 |
|||
cyclotomic=: {{ |
|||
if.y<#cache do. |
|||
if.#c=. y{::cache do. |
|||
c return. |
|||
end. |
|||
end. |
|||
c=. unpad cyclotomic000 y |
|||
if. y>:#cache do. cache=:(100+y){.cache end. |
|||
cache=: (<c) y} cache |
|||
c |
|||
}} |
|||
cyclotomic000=: {{ assert.0<y |
|||
'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 cyclotomic */q |
|||
else. |
|||
(_1,(-y){.1) pDiv unpad +//.@(*/)/ cyclotomic"0}:*/@>,{1,each q |
|||
end. |
|||
}} |
|||
NB. discard high order zero coefficients in representation of polynomial |
|||
unpad=: {.~ 1+0 i:~0=] |
|||
NB. polynomial division, optimized for somewhat sparse polynomials |
|||
pDiv=: {{ |
|||
q=. $j=. 2 + x -&# y |
|||
'x y'=. x,:y |
|||
while. j=. j-1 do. |
|||
if. 0={.y do. j=. j-i=. 0 i.~ 0=y |
|||
q=. q,j#0 |
|||
x=. j |.!.0 x |
|||
else. |
|||
q=. q, r=. x %&{. y |
|||
x=. 1 |.!.0 x - y*r |
|||
end. |
|||
end.q |
|||
}}</lang> |
|||
Task examples: |
|||
<lang J>taskfmt=: {{ |
|||
c=. ":each j=.cyclotomic y |
|||
raw=. rplc&'_-' ;:inv}.,'+';"0|.(*|j)#c('(',[,],')'"_)each '*x^',&":L:0 <"0 i.#c |
|||
txt=. raw rplc'(1*x^0)';'1';'(-1*x^0)';'(-1)';'*x^1)';'*x)' |
|||
LF,~'CP[',y,&":']= ',rplc&('(x)';'x';'+ (-1)';'- 1')txt rplc'(1*';'(';'(-1*';'(-' |
|||
}} |
|||
taskorder=: {{ |
|||
r=.$k=.0 |
|||
while.y>#r do.k=.k+1 |
|||
if.(1+#r) e.|cyclotomic k do. |
|||
r=. r,k |
|||
k=. k-1 |
|||
end. |
|||
end.r |
|||
}} |
|||
;taskfmt each 1+i.30 |
|||
CP[1]= x - 1 |
|||
CP[2]= x + 1 |
|||
CP[3]= (x^2) + x + 1 |
|||
CP[4]= (x^2) + 1 |
|||
CP[5]= (x^4) + (x^3) + (x^2) + x + 1 |
|||
CP[6]= (x^2) + (-x) + 1 |
|||
CP[7]= (x^6) + (x^5) + (x^4) + (x^3) + (x^2) + x + 1 |
|||
CP[8]= (x^4) + 1 |
|||
CP[9]= (x^6) + (x^3) + 1 |
|||
CP[10]= (x^4) + (-x^3) + (x^2) + (-x) + 1 |
|||
CP[11]= (x^10) + (x^9) + (x^8) + (x^7) + (x^6) + (x^5) + (x^4) + (x^3) + (x^2) + x + 1 |
|||
CP[12]= (x^4) + (-x^2) + 1 |
|||
CP[13]= (x^12) + (x^11) + (x^10) + (x^9) + (x^8) + (x^7) + (x^6) + (x^5) + (x^4) + (x^3) + (x^2) + x + 1 |
|||
CP[14]= (x^6) + (-x^5) + (x^4) + (-x^3) + (x^2) + (-x) + 1 |
|||
CP[15]= (x^8) + (-x^7) + (x^5) + (-x^4) + (x^3) + (-x) + 1 |
|||
CP[16]= (x^8) + 1 |
|||
CP[17]= (x^16) + (x^15) + (x^14) + (x^13) + (x^12) + (x^11) + (x^10) + (x^9) + (x^8) + (x^7) + (x^6) + (x^5) + (x^4) + (x^3) + (x^2) + x + 1 |
|||
CP[18]= (x^6) + (-x^3) + 1 |
|||
CP[19]= (x^18) + (x^17) + (x^16) + (x^15) + (x^14) + (x^13) + (x^12) + (x^11) + (x^10) + (x^9) + (x^8) + (x^7) + (x^6) + (x^5) + (x^4) + (x^3) + (x^2) + x + 1 |
|||
CP[20]= (x^8) + (-x^6) + (x^4) + (-x^2) + 1 |
|||
CP[21]= (x^12) + (-x^11) + (x^9) + (-x^8) + (x^6) + (-x^4) + (x^3) + (-x) + 1 |
|||
CP[22]= (x^10) + (-x^9) + (x^8) + (-x^7) + (x^6) + (-x^5) + (x^4) + (-x^3) + (x^2) + (-x) + 1 |
|||
CP[23]= (x^22) + (x^21) + (x^20) + (x^19) + (x^18) + (x^17) + (x^16) + (x^15) + (x^14) + (x^13) + (x^12) + (x^11) + (x^10) + (x^9) + (x^8) + (x^7) + (x^6) + (x^5) + (x^4) + (x^3) + (x^2) + x + 1 |
|||
CP[24]= (x^8) + (-x^4) + 1 |
|||
CP[25]= (x^20) + (x^15) + (x^10) + (x^5) + 1 |
|||
CP[26]= (x^12) + (-x^11) + (x^10) + (-x^9) + (x^8) + (-x^7) + (x^6) + (-x^5) + (x^4) + (-x^3) + (x^2) + (-x) + 1 |
|||
CP[27]= (x^18) + (x^9) + 1 |
|||
CP[28]= (x^12) + (-x^10) + (x^8) + (-x^6) + (x^4) + (-x^2) + 1 |
|||
CP[29]= (x^28) + (x^27) + (x^26) + (x^25) + (x^24) + (x^23) + (x^22) + (x^21) + (x^20) + (x^19) + (x^18) + (x^17) + (x^16) + (x^15) + (x^14) + (x^13) + (x^12) + (x^11) + (x^10) + (x^9) + (x^8) + (x^7) + (x^6) + (x^5) + (x^4) + (x^3) + (x^2) + x + 1 |
|||
CP[30]= (x^8) + (x^7) + (-x^5) + (-x^4) + (-x^3) + x + 1 |
|||
(,.~#\) taskorder 10 |
|||
1 1 |
|||
2 105 |
|||
3 385 |
|||
4 1365 |
|||
5 1785 |
|||
6 2805 |
|||
7 3135 |
|||
8 6545 |
|||
9 6545 |
|||
10 10465</lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |