Cyclotomic polynomial: Difference between revisions
→{{header|Wren}}: Added a second much faster version.
(An alternative version using a compact and efficient algorithm from an academic paper. The existing post was retained.) |
(→{{header|Wren}}: Added a second much faster version.) |
||
Line 5,144:
=={{header|Wren}}==
===Version 1===
{{trans|Go}}
{{libheader|Wren-iterate}}
Line 5,533 ⟶ 5,534:
CP[2805] has coefficient with magnitude = 6
CP[3135] has coefficient with magnitude = 7
</pre>
===Version 2===
{{trans|Java}}
A translation of the alternative version which completes the second part in about 33 seconds.
<syntaxhighlight lang="wren">import "./math" for Int
import "./fmt" for Fmt
class CP {
// Return the Cyclotomic Polynomial of order 'cpIndex' as a list of coefficients,
// where, for example, the polynomial 3x^2 - 1 is represented by the list [3, 0, -1].
static cycloPoly(cpIndex) {
var polynomial = [1, -1]
if (cpIndex == 1) return polynomial
if (Int.isPrime(cpIndex)) return List.filled(cpIndex, 1)
var primes = Int.distinctPrimeFactors(cpIndex)
var product = 1
for (prime in primes) {
var numerator = substituteExponent(polynomial, prime)
polynomial = exactDivision(numerator, polynomial)
product = product * prime
}
return substituteExponent(polynomial, Int.quo(cpIndex, product))
}
// Return the Cyclotomic Polynomial obtained from 'polynomial'
// by replacing x with x^'exponent'.
static substituteExponent(polynomial, exponent) {
var result = List.filled(exponent * (polynomial.count - 1) + 1, 0)
for (i in polynomial.count-1..0) result[i*exponent] = polynomial[i]
return result
}
// Return the Cyclotomic Polynomial equal to 'dividend' / 'divisor'.
// The division is always exact.
static exactDivision(dividend, divisor) {
var result = dividend.toList
for (i in 0..dividend.count - divisor.count) {
if (result[i] != 0) {
for (j in 1...divisor.count) {
result[i+j] = result[i+j] - divisor[j] * result[i]
}
}
}
return result[0..result.count - divisor.count]
}
// Return whether 'polynomial' has a coefficient of equal magnitude
// to 'coefficient'.
static hasHeight(polynomial, coefficient) {
for (i in 0..Int.quo(polynomial.count + 1, 2)) {
if (polynomial[i].abs == coefficient) return true
}
return false
}
}
System.print("Task 1: Cyclotomic polynomials for n <= 30:")
for (cpIndex in 1..30) {
Fmt.write("CP[$2d] = ", cpIndex)
Fmt.pprint("$d", CP.cycloPoly(cpIndex), "", "x")
}
System.print("\nTask 2: Smallest cyclotomic polynomial with n or -n as a coefficient:")
System.print("CP[ 1] has a coefficient with magnitude 1")
var cpIndex = 2
for (coeff in 2..10) {
while (Int.isPrime(cpIndex) || !CP.hasHeight(CP.cycloPoly(cpIndex), coeff)) {
cpIndex = cpIndex + 1
}
Fmt.print("CP[$5d] has a coefficient with magnitude $d", cpIndex, coeff)
}</syntaxhighlight>
{{out}}
<pre>
Task 1: Cyclotomic polynomials for n <= 30:
CP[ 1] = x - 1
CP[ 2] = x + 1
CP[ 3] = x² + x + 1
CP[ 4] = x² + 1
CP[ 5] = x⁴ + x³ + x² + x + 1
CP[ 6] = x² - x + 1
CP[ 7] = x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[ 8] = x⁴ + 1
CP[ 9] = x⁶ + x³ + 1
CP[10] = x⁴ - x³ + x² - x + 1
CP[11] = x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[12] = x⁴ - x² + 1
CP[13] = x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[14] = x⁶ - x⁵ + x⁴ - x³ + x² - x + 1
CP[15] = x⁸ - x⁷ + x⁵ - x⁴ + x³ - x + 1
CP[16] = x⁸ + 1
CP[17] = x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[18] = x⁶ - x³ + 1
CP[19] = x¹⁸ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[20] = x⁸ - x⁶ + x⁴ - x² + 1
CP[21] = x¹² - x¹¹ + x⁹ - x⁸ + x⁶ - x⁴ + x³ - x + 1
CP[22] = x¹⁰ - x⁹ + x⁸ - x⁷ + x⁶ - x⁵ + x⁴ - x³ + x² - x + 1
CP[23] = x²² + x²¹ + x²⁰ + x¹⁹ + x¹⁸ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[24] = x⁸ - x⁴ + 1
CP[25] = x²⁰ + x¹⁵ + x¹⁰ + x⁵ + 1
CP[26] = x¹² - x¹¹ + x¹⁰ - x⁹ + x⁸ - x⁷ + x⁶ - x⁵ + x⁴ - x³ + x² - x + 1
CP[27] = x¹⁸ + x⁹ + 1
CP[28] = x¹² - x¹⁰ + x⁸ - x⁶ + x⁴ - x² + 1
CP[29] = x²⁸ + x²⁷ + x²⁶ + x²⁵ + x²⁴ + x²³ + x²² + x²¹ + x²⁰ + x¹⁹ + x¹⁸ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[30] = x⁸ + x⁷ - x⁵ - x⁴ - x³ + x + 1
Task 2: Smallest cyclotomic polynomial with n or -n as a coefficient:
CP[ 1] has a coefficient with magnitude 1
CP[ 105] has a coefficient with magnitude 2
CP[ 385] has a coefficient with magnitude 3
CP[ 1365] has a coefficient with magnitude 4
CP[ 1785] has a coefficient with magnitude 5
CP[ 2805] has a coefficient with magnitude 6
CP[ 3135] has a coefficient with magnitude 7
CP[ 6545] has a coefficient with magnitude 8
CP[ 6545] has a coefficient with magnitude 9
CP[10465] has a coefficient with magnitude 10
</pre>
| |||