Math::ModInt - modular integer arithmetic
This documentation refers to version 0.011 of Math::ModInt.
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)
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.
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
.
The constructor method new2
is called exactly like new
but it returns two values: an integer division result and a modular integer object.
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.
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)
.
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
.
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.
+ - * / ** == !=
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.
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.)
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.
The object method $x->modulus
returns the modulus of the residue class the object represents.
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).
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).
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.
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.
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.
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.
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.
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.
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.
This method should return the normalized residue as defined in the application interface.
This method should return the modulus as defined in the application interface.
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.
$x->_NEG
should return a new object representing -$x
.
$x->_INV
should return a new object representing the modular inverse of $x
, if it exists, otherwise Math::ModInt->undefined
.
$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
.
$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
.
$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
.
$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
.
$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.
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.
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.
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.
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.
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 .
Martin Becker, <becker-cpan-mp@cozap.com>
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.
Copyright (c) 2009-2015 by Martin Becker. All rights reserved.
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.6.0 or, at your option, any later version of Perl 5 you may have available.
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.