Cyclotomic polynomial: Difference between revisions

=={{header|C++}}==

{{trans|Java}}

#include <iostream>

#include <initializer_list>

return 0;

{{out}}

<pre>Task 1: cyclotomic polynomials for n <= 30:

{{trans|Java}}

{{works with|C sharp|8}}

using System.Collections;

using System.Collections.Generic;

};

}

{{out}}

<pre>

=={{header|D}}==

{{trans|Kotlin}}

import std.exception;

import std.format;

}

}

{{out}}

<pre>Task 1: cyclotomic polynomials for n <= 30:

=={{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}

od;

!!(m,' : ',i);

=={{header|Go}}==

{{trans|Java}}

import (

}

}

{{out}}

Uses synthetic polynomial division and simple memoization.

import Data.Numbers.Primes (primeFactors)

-- general case

(p, m):ps -> let cm = cyclotomics !! (n `div` (p ^ m))

Simple examples

The task solution

showPoly p = foldl1 (\r -> (r ++) . term) $

dropWhile null $

skipBy n [] = []

Result

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₀(x)= 1</tt>

Routine to find the nth cyclotomic polynomial:

cyclotomic=: {{

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²+x+1, x²+1, x²-x+1, and x⁴-x²+1) you get xⁿ-1 (for 12, that would of course be x¹²-1).

Task examples:

c=. ":each j=.cyclotomic y

raw=. rplc&'_-' ;:inv}.,'+';"0|.(*|j)#c('(',[,],')'"_)each '*x^',&":L:0 <"0 i.#c

8 6545

9 6545

=== Another approach ===

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'

}}

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]]

=={{header|Java}}==

import java.util.ArrayList;

import java.util.Collections;

}

{{out}}

<pre>

=={{header|Julia}}==

# memoize cache for recursive calls

println("The cyclotomic polynomial Φ(", abs(n), ") has a coefficient that is ", n < 0 ? -i : i)

end

<pre>

First 30 cyclotomic polynomials:

=={{header|Kotlin}}==

{{trans|Java}}

import kotlin.math.abs

import kotlin.math.pow

} else coefficient.toString() + "x^" + exponent

}

{{out}}

<pre>Task 1: cyclotomic polynomials for n <= 30:

=={{header|Maple}}==

for n to 30 do lprint(Phi(n,x)) od:

[seq(ListTools:-SelectFirst(s->member(n,s),PhiSet,output=indices),n=1..20)];

#[1, 105, 385, 1365, 1785, 2805, 3135, 6545, 6545, 10465, 10465,

=={{header|Mathematica}} / {{header|Wolfram Language}}==

i = 1;

n = 10;

];

i++;

{{out}}

<pre>-1+x

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

echo &"Φ{'(' & $n & ')':7} has coefficient with magnitude = {i}"

dec n

{{out}}

=={{header|PARI/GP}}==

Cyclotomic polynomials are a built-in function.

for(n=1,30,print(n," : ",polcyclo(n)))

for(d=1,10,i=1; while(contains_coeff(i,d)==0,i=i+1);print(d," : ",i))

{{out}}<pre>

=={{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);

$n++;

}

{{out}}

<pre>First 30 cyclotomic polynomials:

{{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>

<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>

=={{header|Python}}==

from collections import deque

while want in c or -want in c:

print(f'C[{want}]: {n}')

{{out}}

Only showing first 10 polynomials to avoid clutter.

Uses the same library as Perl, so comes with the same caveats.

say 'First 30 cyclotomic polynomials:';

sub super ($str) {

$str.subst( / '^' (\d+) /, { $0.trans([<0123456789>.comb] => [<⁰¹²³⁴⁵⁶⁷⁸⁹>.comb]) }, :g)

<pre>First 30 cyclotomic polynomials:

Φ(1) = (x - 1)

=={{header|Sidef}}==

Solution based on polynomial interpolation (slow).

Poly.string_config(Hash(fold_sign => true, prefix => "", suffix => ""))

})

say "Φ(#{k}) has coefficient with magnitude #{n}"

Slightly faster solution, using the '''Math::Polynomial::Cyclotomic''' Perl module.

require('Math::Polynomial::Cyclotomic')

})

say "Φ(#{k}) has coefficient with magnitude = #{n}"

{{out}}

=={{header|Visual Basic .NET}}==

{{trans|C++}}

Module Module1

End Sub

{{out}}

<pre>Task 1: cyclotomic polynomials for n <= 30:

{{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

}

}

{{out}}