Cyclotomic polynomial: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Minor tidy) |
(An alternative version using a compact and efficient algorithm from an academic paper. The existing post was retained.) |
||
Line 2,749: | Line 2,749: | ||
CP[6545] has coefficient with magnitude = 9 |
CP[6545] has coefficient with magnitude = 9 |
||
CP[10465] has coefficient with magnitude = 10 |
CP[10465] has coefficient with magnitude = 10 |
||
</pre> |
|||
===Alternative Version=== |
|||
An alternative example using the algorithm from "Matters Computational" by Jorg Arndt, pages 704 - 705. |
|||
It completes the task in less than 2 seconds. |
|||
<syntaxhighlight lang="java"> |
|||
import java.math.BigInteger; |
|||
import java.util.ArrayList; |
|||
import java.util.Arrays; |
|||
import java.util.List; |
|||
public class CyclotomicPolynomials { |
|||
public static void main(String[] args) { |
|||
System.out.println("Task 1: Cyclotomic polynomials for n <= 30:"); |
|||
for ( int cpIndex = 1; cpIndex <= 30; cpIndex++ ) { |
|||
System.out.println("CP[" + cpIndex + "] = " + toString(cyclotomicPolynomial(cpIndex))); |
|||
} |
|||
System.out.println(); |
|||
System.out.println("Task 2: Smallest cyclotomic polynomial with n or -n as a coefficient:"); |
|||
System.out.println("CP[1] has a coefficient with magnitude 1"); |
|||
int cpIndex = 2; |
|||
for ( int coefficient = 2; coefficient <= 10; coefficient++ ) { |
|||
while ( BigInteger.valueOf(cpIndex).isProbablePrime(PRIME_CERTAINTY) |
|||
|| ! hasHeight(cyclotomicPolynomial(cpIndex), coefficient) ) { |
|||
cpIndex += 1; |
|||
} |
|||
System.out.println("CP[" + cpIndex + "] has a coefficient with magnitude " + coefficient); |
|||
} |
|||
} |
|||
// Return the Cyclotomic Polynomial of order 'cpIndex' as an array of coefficients, |
|||
// where, for example, the polynomial 3x^2 - 1 is represented by the array [3, 0, -1]. |
|||
private static int[] cyclotomicPolynomial(int cpIndex) { |
|||
int[] polynomial = new int[] { 1, -1 }; |
|||
if ( cpIndex == 1 ) { |
|||
return polynomial; |
|||
} |
|||
if ( BigInteger.valueOf(cpIndex).isProbablePrime(PRIME_CERTAINTY) ) { |
|||
int[] result = new int[cpIndex]; |
|||
Arrays.fill(result, 1); |
|||
return result; |
|||
} |
|||
List<Integer> primes = distinctPrimeFactors(cpIndex); |
|||
int product = 1; |
|||
for ( int prime : primes ) { |
|||
int[] numerator = substituteExponent(polynomial, prime); |
|||
polynomial = exactDivision(numerator, polynomial); |
|||
product *= prime; |
|||
} |
|||
polynomial = substituteExponent(polynomial, cpIndex / product); |
|||
return polynomial; |
|||
} |
|||
// Return the Cyclotomic Polynomial obtained from 'polynomial' by replacing x with x^'exponent'. |
|||
private static int[] substituteExponent(int[] polynomial, int exponent) { |
|||
int[] result = new int[exponent * ( polynomial.length - 1 ) + 1]; |
|||
for ( int i = polynomial.length - 1; i >= 0; i-- ) { |
|||
result[i * exponent] = polynomial[i]; |
|||
} |
|||
return result; |
|||
} |
|||
// Return the Cyclotomic Polynomial equal to 'dividend' / 'divisor'. The division is always exact. |
|||
private static int[] exactDivision(int[] dividend, int[] divisor) { |
|||
int[] result = Arrays.copyOf(dividend, dividend.length); |
|||
for ( int i = 0; i < dividend.length - divisor.length + 1; i++ ) { |
|||
if ( result[i] != 0 ) { |
|||
for ( int j = 1; j < divisor.length; j ++ ) { |
|||
result[i + j] += -divisor[j] * result[i]; |
|||
} |
|||
} |
|||
} |
|||
result = Arrays.copyOf(result, result.length - divisor.length + 1); |
|||
return result; |
|||
} |
|||
// Return whether 'polynomial' has a coefficient of equal magnitude to 'coefficient'. |
|||
private static boolean hasHeight(int[] polynomial, int coefficient) { |
|||
for ( int i = 0; i <= ( polynomial.length + 1 ) / 2; i++ ) { |
|||
if ( Math.abs(polynomial[i]) == coefficient ) { |
|||
return true; |
|||
} |
|||
} |
|||
return false; |
|||
} |
|||
// Return a string representation of 'polynomial'. |
|||
private static String toString(int[] polynomial) { |
|||
StringBuilder text = new StringBuilder(); |
|||
for ( int i = 0; i < polynomial.length; i++ ) { |
|||
if ( polynomial[i] == 0 ) { |
|||
continue; |
|||
} |
|||
text.append(( polynomial[i] < 0 ) ? ( ( i == 0 ) ? "-" : " - " ) : ( ( i == 0 ) ? "" : " + " )); |
|||
final int exponent = polynomial.length - 1 - i; |
|||
if ( exponent > 0 && Math.abs(polynomial[i]) > 1 ) { |
|||
text.append(Math.abs(polynomial[i])); |
|||
} |
|||
text.append(( exponent > 1 ) ? |
|||
( "x^" + String.valueOf(exponent) ) : ( ( exponent == 1 ) ? "x" : Math.abs(polynomial[i]) )); |
|||
} |
|||
return text.toString(); |
|||
} |
|||
// Return a list of the distinct prime factors of 'number'. |
|||
private static List<Integer> distinctPrimeFactors(int number) { |
|||
List<Integer> primeFactors = new ArrayList<Integer>(); |
|||
for ( int divisor = 2; divisor * divisor <= number; divisor++ ) { |
|||
if ( number % divisor == 0 ) { |
|||
primeFactors.add(divisor); |
|||
} |
|||
while ( number % divisor == 0 ) { |
|||
number = number / divisor; |
|||
} |
|||
} |
|||
if ( number > 1 ) { |
|||
primeFactors.add(number); |
|||
} |
|||
return primeFactors; |
|||
} |
|||
private static final int PRIME_CERTAINTY = 15; |
|||
} |
|||
</syntaxhighlight> |
|||
<pre> |
|||
Task 1: Cyclotomic polynomials for n <= 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 |
|||
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> |
||