/ 
Math-ModInt-0.001
River stage one • 1 direct dependent • 1 total dependent
/ Math::ModInt

NAME

Math::ModInt - modular integer arithmetic

VERSION

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

SYNOPSIS

use Math::ModInt qw(mod);

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

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

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($residue, $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($residue) creates a new object sharing both its type and modulus with the invocant object $x.

mod

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

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

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

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 consistently yield the Math::Polynomial->undefined object, which will raise an exception upon modulus/residue inspection, but can be recogized by the boolean result of the is_defined/is_undefined methods.

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

BUGS AND LIMITATIONS

So far, only a limited amount of effort has been put into making this module suite faster. We prefer native integer arithmetic over Math::BigInt only where it seems really save to do so, and we memoize only to little extent.

The event handling stuff, on the other hand, may already be coming close to overkill.

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.

At the time of release, extensive tests on various platforms will not yet have been performed, as it is precisely the purpose of this initial version to get out there in the first place. The suite therefore can be expected to break somewhere for sure. The author is looking forward to receive helpful reports, as well as more tests and examples. You may want to look out for updates for a while before making your enterprise depend on these modules. Even then, note the usual disclaimer.

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.

Please submit your bug reports and suggestions 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.

LICENSE AND COPYRIGHT

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

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.