Cyclotomic polynomial: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 14:
=={{header|C++}}==
{{trans|Java}}
<
#include <iostream>
#include <initializer_list>
Line 532:
return 0;
}</
{{out}}
<pre>Task 1: cyclotomic polynomials for n <= 30:
Line 581:
{{trans|Java}}
{{works with|C sharp|8}}
<
using System.Collections;
using System.Collections.Generic;
Line 816:
};
}
}</
{{out}}
<pre>
Line 865:
=={{header|D}}==
{{trans|Kotlin}}
<
import std.exception;
import std.format;
Line 1,303:
}
}
}</
{{out}}
<pre>Task 1: cyclotomic polynomials for n <= 30:
Line 1,351:
=={{header|Fermat}}==
This isn't terribly efficient if you have to calculate many cyclotomics- store them in an array rather than using recursion instead if you need to do that- but it showcases Fermat's strength at polynomial expressions.
<
&(J=x); {adjoin x as the variable in the polynomials}
Line 1,381:
od;
!!(m,' : ',i);
od;</
=={{header|Go}}==
{{trans|Java}}
<
import (
Line 1,824:
}
}
}</
{{out}}
Line 1,877:
Uses synthetic polynomial division and simple memoization.
<
import Data.Numbers.Primes (primeFactors)
Line 1,915:
-- general case
(p, m):ps -> let cm = cyclotomics !! (n `div` (p ^ m))
in lift (lift cm p `shortDiv` cm) (p^(m-1))</
Simple examples
Line 1,930:
The task solution
<
showPoly p = foldl1 (\r -> (r ++) . term) $
dropWhile null $
Line 1,965:
skipBy n [] = []
skipBy n lst = let (x:_, b) = splitAt n lst in x:skipBy n b</
Result
Line 2,017:
For values up to 70, we can find cyclotomic polynomials by finding a polynomial with roots of unity relatively prime to the order of the polynomial:
<
This approach suggests that cyclotomic polynomial zero should be <tt>f<sub>0</sub>(x)= 1</tt>
Line 2,023:
Routine to find the nth cyclotomic polynomial:
<
cyclotomic=: {{
Line 2,067:
end.
end.q
}}</
If you take all the divisors of a number. (For example, for 12, the divisors are: 1, 2, 3, 4, 6 and 12) and find the product of their cyclotomic polynomials (for example, for 12, x-1, x+1, x<sup>2</sup>+x+1, x<sup>2</sup>+1, x<sup>2</sup>-x+1, and x<sup>4</sup>-x<sup>2</sup>+1) you get x<sup>n</sup>-1 (for 12, that would of course be x<sup>12</sup>-1).
Line 2,082:
Task examples:
<
c=. ":each j=.cyclotomic y
raw=. rplc&'_-' ;:inv}.,'+';"0|.(*|j)#c('(',[,],')'"_)each '*x^',&":L:0 <"0 i.#c
Line 2,141:
8 6545
9 6545
10 10465</
=== Another approach ===
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 [[Fast Fourier transform#J|fast fourier transform]] for polynomial multiplication and division.
<
require'math/fftw'
Line 2,169:
}}
roundreal =: [: <. 0.5 + 9&o.</
This variation for polynomial division is only valid when there's no remainder to be concerned with (which is the case, here). The article mentioned in the comments is an essay on using [[j:Essays/FFT|fft for polynomial multiplication]]
Line 2,176:
=={{header|Java}}==
<
import java.util.ArrayList;
import java.util.Collections;
Line 2,703:
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,752:
=={{header|Julia}}==
<
# memoize cache for recursive calls
Line 2,809:
println("The cyclotomic polynomial Φ(", abs(n), ") has a coefficient that is ", n < 0 ? -i : i)
end
</
<pre>
First 30 cyclotomic polynomials:
Line 2,856:
=={{header|Kotlin}}==
{{trans|Java}}
<
import kotlin.math.abs
import kotlin.math.pow
Line 3,312:
} else coefficient.toString() + "x^" + exponent
}
}</
{{out}}
<pre>Task 1: cyclotomic polynomials for n <= 30:
Line 3,359:
=={{header|Maple}}==
<
for n to 30 do lprint(Phi(n,x)) od:
Line 3,396:
[seq(ListTools:-SelectFirst(s->member(n,s),PhiSet,output=indices),n=1..20)];
#[1, 105, 385, 1365, 1785, 2805, 3135, 6545, 6545, 10465, 10465,
# 10465, 10465, 10465, 11305, 11305, 11305, 11305, 11305, 11305]</
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
i = 1;
n = 10;
Line 3,420:
];
i++;
]</
{{out}}
<pre>-1+x
Line 3,469:
We use Java algorithm with ideas from C#, D, Go and Kotlin. We have kept only algorithm number 2 as other algorithms are much less efficient. We have also done some Nim specific improvements in order to get better performances.
<
type
Line 3,803:
echo &"Φ{'(' & $n & ')':7} has coefficient with magnitude = {i}"
dec n
break</
{{out}}
Line 3,854:
=={{header|PARI/GP}}==
Cyclotomic polynomials are a built-in function.
<
for(n=1,30,print(n," : ",polcyclo(n)))
Line 3,860:
for(d=1,10,i=1; while(contains_coeff(i,d)==0,i=i+1);print(d," : ",i))
</syntaxhighlight>
{{out}}<pre>
Line 3,907:
=={{header|Perl}}==
Conveniently, the module <code>Math::Polynomial::Cyclotomic</code> exists to do all the work. An <code>exponent too large</code> error prevents reaching the 10th step of the 2nd part of the task.
<
use List::Util qw(first);
use Math::Polynomial::Cyclotomic qw(cyclo_poly_iterate);
Line 3,924:
$n++;
}
}</
{{out}}
<pre>First 30 cyclotomic polynomials:
Line 3,972:
{{trans|Julia}}
Uses several routines from [[Polynomial_long_division#Phix]], tweaked slightly to check remainder is zero and trim the quotient.
<!--<
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Cyclotomic_Polynomial.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 4,087:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</
{{out}}
If you disable the cheating, and if in a particularly self harming mood replace it with n+=1, you will get exactly the same output, eventually.<br>
Line 4,136:
=={{header|Python}}==
<
from collections import deque
Line 4,257:
while want in c or -want in c:
print(f'C[{want}]: {n}')
want += 1</
{{out}}
Only showing first 10 polynomials to avoid clutter.
Line 4,303:
Uses the same library as Perl, so comes with the same caveats.
<syntaxhighlight lang="raku"
say 'First 30 cyclotomic polynomials:';
Line 4,326:
sub super ($str) {
$str.subst( / '^' (\d+) /, { $0.trans([<0123456789>.comb] => [<⁰¹²³⁴⁵⁶⁷⁸⁹>.comb]) }, :g)
}</
<pre>First 30 cyclotomic polynomials:
Φ(1) = (x - 1)
Line 4,372:
=={{header|Sidef}}==
Solution based on polynomial interpolation (slow).
<
Poly.string_config(Hash(fold_sign => true, prefix => "", suffix => ""))
Line 4,392:
})
say "Φ(#{k}) has coefficient with magnitude #{n}"
}</
Slightly faster solution, using the '''Math::Polynomial::Cyclotomic''' Perl module.
<
require('Math::Polynomial::Cyclotomic')
Line 4,412:
})
say "Φ(#{k}) has coefficient with magnitude = #{n}"
}</
{{out}}
Line 4,460:
=={{header|Visual Basic .NET}}==
{{trans|C++}}
<
Module Module1
Line 4,942:
End Sub
End Module</
{{out}}
<pre>Task 1: cyclotomic polynomials for n <= 30:
Line 4,995:
{{libheader|Wren-fmt}}
Second part is very slow. Limited to first 7 to finish in a reasonable time - 5 minutes on my machine.
<
import "/sort" for Sort
import "/math" for Int, Nums
Line 5,334:
}
}
}</
{{out}}
|