File Coverage

blib/lib/Math/Polynomial/Cyclotomic.pm

Criterion	Covered	Total	%
statement	57	57	100.0
branch	12	12	100.0
condition	14	16	87.5
subroutine	17	17	100.0
pod	4	8	50.0
total	104	110	94.5

# Copyright (c) 2013-2019 by Martin Becker.  This package is free software,
# licensed under The Artistic License 2.0 (GPL compatible).

package Math::Polynomial::Cyclotomic;

use 5.006;
use strict;
use warnings;
use Math::Polynomial;
use Math::Prime::Util qw(divisors);
require Exporter;

our @ISA         = qw(Exporter);
our @EXPORT_OK   = qw(
    cyclo_poly cyclo_factors cyclo_poly_iterate cyclo_factors_iterate
);
our %EXPORT_TAGS = (all => \@EXPORT_OK);
our $VERSION     = '0.002';

# some polynomial with default coefficient type
my $poly = Math::Polynomial->new;
$poly->string_config({fold_sign => 1, times => '*'});

# ----- private subroutine -----

sub _cyclo_poly {
    my ($u, $table, $n, $divisors) = @_;
    my @d = $divisors? (grep { not $n % $_ } @{$divisors}): divisors($n);
    my $p = $u->monomial(pop @d)->sub_($u);
    if (@d) {
        my $m = $d[-1];
        $p /= $u->monomial($m)->sub_($u);
        for (my $i = 1; $i < $#d; ++$i) {
            my $r = $d[$i];
            if ($m % $r) {
                $p /= $table->{$r} || _cyclo_poly($u, $table, $r, \@d);
            }
        }
    }
    $table->{$n} = $p;
    return $p;
}

sub _cyclo_factors {
    my ($u, $table, $n) = @_;
    my @d = divisors($n);
    return map { $table->{$_} || _cyclo_poly($u, $table, $_, \@d) } @d;
}

# ----- Math::Polynomial extension -----

sub Math::Polynomial::cyclotomic {
    my ($this, $n, $table) = @_;
    my $u = $this->monomial(0);
    return _cyclo_poly($u, {}, $n) if !$table;
    return $table->{$n} || _cyclo_poly($u, $table, $n);
}

sub Math::Polynomial::cyclo_factors {
    my ($this, $n, $table) = @_;
    my $u = $this->monomial(0);
    return _cyclo_factors($u, $table || {}, $n);
}

sub Math::Polynomial::cyclo_poly_iterate {
    my ($this, $n, $table) = @_;
    my $u = $this->monomial(0);
    $n ||= 1;
    --$n;
    $table ||= {};
    return
        sub {
            ++$n;
            $table->{$n} || _cyclo_poly($u, $table, $n);
        };
}

sub Math::Polynomial::cyclo_factors_iterate {
    my ($this, $n, $table) = @_;
    my $u = $this->monomial(0);
    $n ||= 1;
    $table ||= {};
    return sub { _cyclo_factors($u, $table, $n++) };
}

# ----- public subroutines -----

sub cyclo_poly            { $poly->cyclotomic(@_)            }
sub cyclo_factors         { $poly->cyclo_factors(@_)         }
sub cyclo_poly_iterate    { $poly->cyclo_poly_iterate(@_)    }
sub cyclo_factors_iterate { $poly->cyclo_factors_iterate(@_) }

1;

__END__