Cyclotomic polynomial: Difference between revisions
Content added Content deleted
(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: | Line 5,144: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
===Version 1=== |
|||
{{trans|Go}} |
{{trans|Go}} |
||
{{libheader|Wren-iterate}} |
{{libheader|Wren-iterate}} |
||
Line 5,533: | Line 5,534: | ||
CP[2805] has coefficient with magnitude = 6 |
CP[2805] has coefficient with magnitude = 6 |
||
CP[3135] has coefficient with magnitude = 7 |
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> |
</pre> |