The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-ModInt-0.012
River stage one • 1 direct dependent • 1 total dependent
++
/ Math::ModInt

NAME

Math::ModInt - modular integer arithmetic

VERSION

This documentation refers to version 0.012 of Math::ModInt.

SYNOPSIS

  use Math::ModInt qw(mod divmod qmod);

  $a = mod(32, 127);            #  32 (mod 127)
  $b = $a->new(99);             #  99 (mod 127)
  $c = $a + $b;                 #   4 (mod 127)
  $d = $a**2 - $b/$a;           # 120 (mod 127)
  ($i, $e) = divmod(32, 5);     #  6, mod(2, 5)

  $m = $d->modulus;             # 127
  $r = $d->residue;             # 120
  $s = $d->signed_residue;      #  -7
  $t = "$a";                    # 'mod(32, 127)'

  use Math::BigRat;

  $q = Math::BigRat->new('2/3');
  $f = qmod($q, 5);             #   4 (mod 5)

DESCRIPTION

Math::ModInt provides overloaded operators for modular integer arithmetic. Math::ModInt objects represent integer residue classes. These objects can be used in arithmetic expressions just like Perl numbers. Math::ModInt objects are immutable. Mutators like += will replace an object rather than change its state.

In mixed expressions with Math::ModInt objects and ordinary numbers the numbers are interpreted as their residue class modulo the modulus of the rest of the expression. Different moduli must not be mixed, though.

There are different implementations, optimized for moduli of a particular size or using a particular math library. The base module will transparently choose a suitable back-end whenever a constructor is called.

Application Interface

Constructors

new

Called as a class method, Math::ModInt->new($int, $modulus) creates a new object of a subclass appropriate for the given modulus and current platform. The modulus must be a positive integer value.

Called as an object method, $x->new($int) creates a new object sharing both its type and modulus with the invocant object $x.

new2

The constructor method new2 is called exactly like new but it returns two values: an integer division result and a modular integer object.

mod

For convenience, mod can be imported as an abbreviation for the class method constructor; mod($int, $modulus) is equivalent to Math::ModInt->new($int, $modulus). Note that mod has to be called as a plain function, not like a method.

divmod

The divmod function can be imported, too. It takes two integers like mod but it returns two values: an integer division result and a modular integer object. Thus divmod($int, $modulus) is equivalent to Math::ModInt->new2($int, $modulus).

qmod

Another importable constructor function is qmod. It can convert rational numbers to modular integers of a given modulus if the denominator is coprime to that modulus. The expression qmod($rat, $modulus) is equivalent to mod($rat->numerator, $modulus) / mod($rat->denominator, $modulus). Note that $rat must be an object with numerator and denominator methods, like e.g. an instance of Math::BigRat.

Note also that mixed expressions with modular integers and rational numbers are not permitted. Always convert rational numbers explicitly with qmod.

undefined

This method returns the undefined placeholder object representing undefined results in the domain of modular integer arithmetic, such as from division by an operand not coprime to the modulus. See Math::ModInt::Event for how to control whether this object or other ways to report arithmetic faults should be employed.

Operators

+ - * / ** == !=

Addition, negation, subtraction, multiplication, division, exponentiation with integer exponents, and equivalence operators are provided through overloaded perl operators. Division or exponentiation with negative exponents may trigger an UndefinedResult event and yield an undefined result.

Operands must either have the same modulus or be plain integers, except for equality/inequality checks. Operands with different moduli may be compared and are considered unequal.

For other exceptions to the requirement of identical moduli, see Math::ModInt::ChineseRemainder.

Note that neither the modulo operator % nor bit-operations & | ^ << >> nor order relations < <= > >= <=> are defined.

inverse

The object method $x->inverse returns the multiplicative modular inverse of $x, if it exists, otherwise the undefined placeholder. (y is the modular inverse of x modulo m if x * y is equivalent to 1 modulo m.)

Accessors

is_defined
is_undefined

The object methods $x->is_defined and $x->is_undefined return boolean values checking whether $x is a proper residue class object or the undefined placeholder. Besides as_string, these are the only legal accessors for the undefined placeholder.

modulus

The object method $x->modulus returns the modulus of the residue class the object represents.

residue

The object method $x->residue returns the normalized residue of the residue class the object represents. Its value is chosen as if it was a division remainder, i.e. between zero (inclusive) and the modulus (exclusive).

signed_residue

The object method $x->signed_residue returns a representative of the residue class the object represents, chosen as close to zero as possible. In case of a tie, i.e. when the modulus is an even number and the residue is half the modulus, the negative value is given preference (like in many native signed integer formats).

centered_residue

The object method $x->centered_residue is equivalent to $x->signed_residue except that the positive value is given preference when the residue is precisely half the modulus.

is_zero
is_not_zero

The object methods $x->is_zero and $x->is_not_zero return boolean values checking whether $x is the zero element of its ring, i.e. 0 == $x->residue). Either one of these methods can be called implicitly when a Math::ModInt object is being used in boolean context.

as_string

The object method $x->as_string returns a string representation of $x. It will be in the form mod(residue, modulus) (similar to the constructor) in case of proper residue classes, or mod(?, ?) in case of the undefined placeholder.

Miscellaneous methods

optimize_time

Some implementations can employ different optimization strategies for either time or space efficiency. Time efficiency aims to speed up repetitive calculations at the expense of memory space. Space efficiency aims to minimize the memory footprint at the expense of cpu cycles. Where such a distinction is available, separate choices can be made for each modulus.

The object method $x->optimize_time gives a hint to the implementation of $x to prefer time over space efficiency for the modulus of $x. It returns the object it was called with.

optimize_space

The object method $x->optimize_space gives a hint to the implementation of $x to prefer space over time efficiency for the modulus of $x. It returns the object it was called with.

optimize_default

The object method $x->optimize_default restores the default behaviour of the implementation of $x with respect to its optimization strategy for the modulus of $x. It returns the object it was called with. Defaults may depend on the modulus and may or may not be equivalent to one of the other strategy choices. They should, however, be reasonably secure to use on small systems, and thus lean more to space than time efficency.

Implementation Interface

Math::ModInt offers a special interface for implementations, intended to simplify operator overloading. Implementations are subclasses overriding only a couple of methods, as listed below. The overload pragma should not explicitly be used in implementations adhering to this interface.

Implementations handle a restricted set of moduli, sometimes only one. Currently, these restrictions are known in the base module and hard-coded there. Future revisions of Math::ModInt may offer a registration mechanism with precedences to make platform-specific choices possible.

Mandatory Methods

residue

This method should return the normalized residue as defined in the application interface.

modulus

This method should return the modulus as defined in the application interface.

_NEW

This constructor will be called either as a class method with two parameters residue and modulus, or as an object method with just one parameter residue. It should return a new object with the given residue and modulus in the former case, or the given residue and the modulus of the invocant object in the latter case.

Note that the constructors mod and new of the application interface should not be overriden, as they need to switch implementations, depending on parameters rather than the package they are called from.

_NEG

$x->_NEG should return a new object representing -$x.

_INV

$x->_INV should return a new object representing the modular inverse of $x, if it exists, otherwise Math::ModInt->undefined.

_ADD

$x->_ADD($y) should return a new object representing $x+$y. The parameter $y will always be an object of the same class and have the same modulus as $x.

_SUB

$x->_SUB($y) should return a new object representing $x-$y. The parameter $y will always be an object of the same class and have the same modulus as $x.

_MUL

$x->_MUL($y) should return a new object representing $x*$y. The parameter $y will always be an object of the same class and have the same modulus as $x.

_DIV

$x->_DIV($y) should return a new object representing $x/$y if it exists, otherwise Math::ModInt->undefined. The parameter $y will always be an object of the same class and have the same modulus as $x.

_POW

$x->_POW($y) should return a new object representing $x ** $y if it exists, otherwise Math::ModInt->undefined. The exponent $y will always be an integer number. An undefined result means that the exponent was negative while $x had no modular inverse.

Optional Methods

_NEW2

This constructor method will be called like _NEW but it must return two values: an integer division result and the newly created modular integer object. It should be implemented if the underlying library offers an efficient way to calculate a quotient and remainder simultaneously.

optimize_time
optimize_space
optimize_default

These methods give hints for the optimization strategy for a particular modulus, as described in the application interface above. They do not need to be implemented.

DIAGNOSTICS

Some operations are not defined for all operands. For instance, division only makes sense if the denominator residue is coprime to the modulus. Operands with different moduli generally can not be combined in binary operations.

By default, operations with incompatible operands or undefined results consistently yield the Math::ModInt->undefined object, which will raise an exception upon modulus/residue inspection, but can be recognized by the boolean result of the is_defined/is_undefined methods. See Math::ModInt::Event for ways to alter this behaviour.

DEPENDENCIES

This module uses Math::BigInt for arbitrary-precision calculations. If you want control over which Math::BigInt backend is to be used, import Math::BigInt before Math::ModInt, like this:

  use Math::BigInt try => 'GMP,Pari';
  use Math::ModInt qw(mod);

The minimal required perl version is 5.6.

BUGS AND LIMITATIONS

Math::BigInt version 1.99 can not be used together with this module, as the former has a severe bug with modular integer arithmetic which is detected in our test suite. Math::BigInt version 1.991 has this issue resolved.

A little bit of effort has been put into making this module suite reasonably efficient even in the absence of convenient big integer libraries. For best performance, though, we recommend installing a fast integer library such as Math::BigInt::GMP together with Math::ModInt.

Currently, the choice of Math::ModInt backend is hard-wired into the main module, for the sake of simplicity. Please contact the maintainer if you intend to use a backend not from this distribution, so that something clever can be done about it.

Math::ModInt is still undergoing beta testing on a growing number of platforms. Bug reports and suggestions are always welcome -- please submit them through the CPAN RT, http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math-ModInt .

SEE ALSO

AUTHOR

Martin Becker, <becker-cpan-mp@cozap.com>

ACKNOWLEDGEMENTS

Thanks go to Ilya Zakharevich for the overload package, and for mentioning this package ages before it was actually written, in perlnumber.pod. I also appreciate the role of cpantesters.org in quality assurance for CPAN.

If you find something cool you can do with Math::ModInt you like to share with others, you are welcome to submit your code for the examples section, as well as your name or chosen identity for the hall of fame.

LICENSE AND COPYRIGHT

Copyright (c) 2009-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 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.