/ 
Math-Polynomial-Cyclotomic-0.002
River stage zero No dependents
/ Math::Polynomial::Cyclotomic

NAME

Math::Polynomial::Cyclotomic - cyclotomic polynomials generator

VERSION

This documentation refers to Version 0.002 of Math::Polynomial::Cyclotomic.

SYNOPSIS

use Math::Polynomial::Cyclotomic qw(
  cyclo_poly cyclo_factors cyclo_poly_iterate cyclo_factors_iterate );
use Math::Polynomial::Cyclotomic qw(:all);

$p6 = cyclo_poly(6);                    # x^2-x+1

# complete factorization of x^6-1
@f6 = cyclo_factors(6);                 # x-1, x+1, x^2+x+1, x^2-x+1

# iterator generating consecutive cyclotomic polynomials
$it = cyclo_poly_iterate(1);
$p1 = $it->();                          # x-1
$p2 = $it->();                          # x+1
$p3 = $it->();                          # x^2+x+1

# iterator generating factors of consecutive binomials x^n-1
$it = cyclo_factors_iterate(3);
@f3 = $it->();                          # x-1, x^2+x+1
@f4 = $it->();                          # x-1, x+1, x^2+1

# constructors for a given coefficient type, such as Math::AnyNum
$poly = Math::Polynomial->new(Math::AnyNum->new(0));
$p6 = $poly->cyclotomic(6);             # x^2-x+1
@fs = $poly->cyclo_factors(6);          # x-1, x+1, x^2+x+1, x^2-x+1
$it = $poly->cyclo_poly_iterate(1);     # as above
$it = $poly->cyclo_factors_iterate(3);  # as above

# optional argument: hashref of read-write polynomial index
%table = ();
@f6    = cyclo_factors(6, \%table);
$p3    = $table{3};                     # already done
$p18   = cyclo_poly(18, \%table);       # faster

DESCRIPTION

This small extension of Math::Polynomial adds a constructor for cyclotomic polynomials and a factoring algorithm for rational polynomials of the form x^n-1. Cyclotomic polynomials are monic irreducible polynomials with integer coefficients that are a divisor of some binomial x^n-1 but not of any other binomial x^k-1 with k < n.

cyclo_poly

If $n is a positive integer number, cyclo_poly($n) calculates the nth cyclotomic polynomial.

If %table is a dictionary mapping indexes to previously computed cyclotomic polynomials, cyclo_poly($n, \%table) will do the same, but use the table to store and look up intermediate results that also happen to be cyclotomic polynomials. The table must not contain other stuff, nor should it be used for more than one coefficient type. To be safe, start with an empty hash but re-use it for similar calculations.

Math::Polynomial::cyclotomic

If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclotomic($n) is essentially equivalent to cyclo_poly($n), but returns a polynomial sharing the coefficient type of $poly.

With an optional hashref argument for memoization, $poly->cyclotomic($n, \%table) will work similar to cyclo_poly($n, \%table).

cyclo_factors

If $n is a positive integer number, cyclo_factors($n) calculates a complete factorization of x^n-1 over the field of rational numbers. These are precisely the cyclotomic polynomials with index k, k running through all positive integer divisors of n. The factors are ordered by increasing index, so that the nth cyclotomic polynomial will be the last element of the list returned.

Like "cyclo_poly", cyclo_factors can be called with an optional hashref argument for memoization. It will store individual cyclotomic polynomials, not complete factorizations, and can thus be used with cyclo_poly and cyclo_factors interchangeably.

Math::Polynomial::cyclo_factors

If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_factors($n) is essentially equivalent to cyclo_factors($n), but returns a list of polynomials sharing the coefficient type of $poly.

With an optional hashref argument for memoization, $poly->cyclo_factors($n, \%table) will work similar to cyclo_factors($n, \%table).

cyclo_poly_iterate

If $n is a positive integer number, cyclo_poly_iterate($n) returns a coderef that, repeatedly called, returns consecutive cyclotomic polynomials starting with index n. If $n is omitted it defaults to 1. Iterating this way is more time-efficient than repetitive calls of cyclo_poly, as intermediate results that would otherwise be re-calculated later are memoized in the state of the closure. Re-assigning or undefining the coderef will free the memory used for that.

Alternatively, an external memoization table can be used, if supplied as optional hashref argument, as in cyclo_poly_iterate($n, \%table).

Math::Polynomial::cyclo_poly_iterate

If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_poly_iterate($n) is essentially equivalent to cyclo_poly_iterate($n), but the polynomials returned by the iterator will share the coefficient type of $poly.

With an optional hashref argument for memoization, $poly->cyclo_poly_iterate($n, \%table) will work similar to cyclo_poly_iterate($n, \%table).

cyclo_factors_iterate

If $n is a positive integer number, cyclo_factors_iterate($n) returns a coderef that, repeatedly called, returns factorizations of consecutive binomials x^k-1 starting with k = n. If $n is omitted it defaults to 1. Iterating this way is more time-efficient than repetitive calls of cyclo_factors, as intermediate results that would otherwise be re-calculated later are memoized in the state of the closure. Re-assigning or undefining the coderef will free the memory used for that.

Alternatively, an external memoization table can be used, if supplied as optional hashref argument, as in cyclo_factors_iterate($n, \%table). It will store individual cyclotomic polynomials, not complete factorizations, and can thus be used with cyclo_poly_iterate and cyclo_factors_iterate, as well as cyclo_poly and cyclo_factors, interchangeably.

Math::Polynomial::cyclo_factors_iterate

If $poly is a Math::Polynomial object and Math::Polynomial::Cyclotomic has been loaded, $poly->cyclo_factors_iterate($n) is essentially equivalent to cyclo_factors_iterate($n), but the polynomials returned by the iterator will share the coefficient type of $poly.

With an optional hashref argument for memoization, $poly->cyclo_factors_iterate($n, \%table) will work similar to cyclo_factors_iterate($n, \%table).

DIAGNOSTICS

While this library doesn't have specific diagnostic messages, some exceptions from Math::Polynomial or Math::Prime::Util may indicate inappropriate arguments.

exponent too large

The integer argument n, which necessitates operations on polynomials up to degree n, was too large for current Math::Polynomial limitations.

Parameter '%s' must be a positive integer

The argument n should have been a positive integer number but was not.

DEPENDENCIES

This library uses Math::Polynomial (version 1.001 and up) for polynomial arithmetic and Math::Prime::Util (version 0.36 and up) for factoring integers. The minimal required perl version is 5.6.

ROADMAP

While cyclotomic polynomials are irreducible over the integers in general, they can be further factorized with algebraic methods when restricted to particular integer values. We intend to add aurifeuillean factorization in an upcoming release.

It will be not very hard to extend the interface to factor not just x^n-1 but, more generally, x^n±y^n, too. We might add this feature just for that reason.

Other improvements should address performance with large degrees, eventually. This is, however, not a priority so far.

BUGS AND LIMITATIONS

This implementation is optimized for n ≤ 10000. It assumes that factoring numbers up to n is cheap, and it employs polynomial division via Math::Polynomial, using pure Perl to operate on arrays of coefficients.

For larger n, $Math::Polynomial::max_degree must be raised or undefined. For very large n, a memory-efficient polynomial type and an arbitrary precision coefficient type should be used. Note that although Math::BigInt is not in general a coefficient type suitable for polynomial division, in this case it would be sufficent, as all of our divisions in the coefficient space have integer results.

Currently, our algorithms do not always avoid factoring integer numbers more than once. Doing so more rigorously might speed up calculations for very large n.

Bug reports and suggestions are always welcome — please submit them through the CPAN RT, http://rt.cpan.org/NoAuth/Bugs.html?Dist=Math-Polynomial-Cyclotomic.

SEE ALSO

AUTHOR

Martin Becker, <becker-cpan-mp (at) cozap.com>

CONTRIBUTING

Contributions to this library are welcome (see the CONTRIBUTING file).

LICENSE AND COPYRIGHT

Copyright (c) 2019 by Martin Becker, Blaubeuren.

This library is free software; you can distribute it and/or modify it under the terms of the Artistic License 2.0 (see the LICENSE file).

DISCLAIMER OF WARRANTY

This library is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.