Math::GMPn - Fixed length integer arithmetic.
use Math::GMPn; # 128bits; mpn_set_str($a, "123450000000000", 10, 128); mpn_set_str($b, "100000000000001", 16, 128); # hexadecimal mpn_set_str($c, "0x1f1f1f1f1f1f1f1", 0, 128); # hexadecimal too! mpn_set_num($d, 23 * 234); mpn_mul($r1, $a, $b); mpn_add($r2, $r1, $c); mpn_div($r3, $r4, $r2, $d); say mpn_get_str($r4);
This module provides a set of functions to perform arithmetic on fixed length but arbitrarily large bit strings implemented on top of the GMP library low level functions (see http://gmplib.org/manual/Low_002dlevel-Functions.html).
Numbers are represented as arrays of GMP mp_limb_t integers (usually, the native unsigned int) packed into Perl scalars without any additional wrapping.
The bit length of the strings passed to the module must be a multiple of the mp_limb_t bit size (32 and 64 bits for 32bit and 64bit machines respectively). Most operations do not check that condition and their results are unspecified when arguments with non conforming sizes are used.
Also, the strings passed must by internally aligned on a mp_limb_t boundary. That usually means not using the four argument variant of substr
on any scalar that would be passed to Math::GMPn. For instance:
# don't do that: $a = ...; $b = ...; substr($a, 0, 3, ""); mpn_add($r, $a, $b); # croaks!
When strings of different length are used on the same operation, the result lenght is equal to that of the largest input. For instance, adding a 128bit string and a 256bit string will output a 256bit string. Overflows are silently discarded.
This module is designed to be as fast as possible, trading of user-friendliness by speed when required.
In practice, that translates into the following principles:
In order to minimize Perl internal data structures and memory allocations, most functions do not return the result but use their first argument for output.
For instance:
mpn_add($r, $s1, $s2)
Returns the result value in $r.
Assembler programmers may find this way of doing familiar.
Interface is not object oriented but fully functional.
OO is ruled out because method invocation on objects is very expensive.
Overloading would require wrapping the Math::GMPn strings, using OO and returning the results as new values, and so, drastically reducing the performance of the module.
Some functions have extraneous requirements, as no overlapping arguments, input arguments being overwritten after the call, requiring some value to be odd, etc.
Those are usually artifacts of the underlaying GMP low level functions that can not be hidden without a noticiable impact on the performance of the module.
Besides going against the aim for speed, the module performs all the checks required to ensure that it will not make your program crash when bad inputs are given.
(Otherwise, report it as a bug, please ;-)
Some of the functions of this module accept overlapping of input and output arguments while others doesn't.
For instance:
mpn_add($r, $r, $s); # valid! mpn_mul($r, $r, $s); # invalid!
The rules are as follow:
logical operations (ior, xor, and, etc.), addition and substration, shifts.
multiplication, division, squaring, root squaring, gcd, etc.
when in doubt, just try!
The following functions are exported by the module:
Return the size in bytes of the mp_limb_t type used internally by GMP to represent numbers (usually 4 for 32bit machines and 8 for 64bit ones).
Return the size in bits of the mp_limb_t type (usually 32 or 64 for 32bit or 64bit machines respectively).
Converts an ASCII representation of the number in the given base $base
to Math::GMPn internal representation.
Digits must be in the range '0'-'9' and 'a'-'z' or 'A'-'Z'.
$base
must be between 2 and 36 (inclusive). When base is omitted (or is 0), if the string starts by 0b
, 0o
or 0x
, base 2, 8 or 16 is used respectively; otherwise, it defaults to 10.
If $bitlen
is not given, the minimum plausible bit length able to store the given number is used.
Converts a byte representation of the number in the given base $base
to the internal representation.
For instance, the following calls are equivalent:
mpn_set_str0($a1, "\xf0\xaa\x01", 16, 128); mpn_set_str($a2, "f0aa01", 16, 128); mpn_set_str($a2, "0xf0aa01", 0, 128);
Generate a random number of length <$bitlen>. The most significant limb is always non-zero.
Converts a Perl native number to Math::GMPn internal format.
Performs an inplace inclusive or of the native Perl unsigned integer $ul
displaced $bitix
bits to the right into $r
. Conceptually it is equivalent to:
$r ||= $u1 << ($bitix * GMP_LIMB_BITS)
This function can be used to build a Math::GMPn number from its limbs:
my @limbs = (0x00000123, 0x00000340, 0xffffaaaa, 0x0034000f) my $r = ''; mpn_setior_uint($r, $limbs[$_], 32 * $_) for my (0..$#limbs) # $r = 0x0034000fffffaaaa0000034000000123
Sets $r
to the value $s
but removing high limbs with value 0.
Extends or truncate $r to the given bitlen $bitlen
.
If the optional $sign_extend argument has a true value, the leftmost bit of $r is used to fill the new bits.
Return the size in bits of the given argument
Converts the Math::GMPn number in $s1 to its ASCII representation in base $base
(10 by default).
Converts the Math::GMPn number in $s1 to its byte representation in base $base
(10 by default).
returns the value of the Math::GMPn number shifted to the right $bitix
bits and masked by $mask
. Conceptually it is equivalent to:
$u = ($s1 >> $bitix ) & $mask;
$r = ~$s1
$r = -$s1
$r = $s1 | $s2
$r = $s1 ^ $s2
$r = $s1 & $s2
$r = $s1 & ~$s2
$r = $s1 | ~$s2
$r = ~($s1 & $s2)
$r = ~($s1 | $s2)
$r = ~($s1 ^ $s2)
$r = $s1 + $s2
$r = $s1 - $s2
$r = $s1 * $s2
This function performs the multiplication of $s1
and $s2
but does not truncate the result to the lenght of the largest argument so that bitlen($r) = bitlen($s1) + bitlen($s2)
.
$r = $s1 * $s1
This function squares $s1
and returns the result untruncated.
Calculates the quoting and the remainder of dividing $s1
by $s2
. Mathematically:
$s1 = $q * $s2 + $r
$r = $s1 / 3
$s1 must be a multiple of 3
.
Computes the square root and the remainder of $s1
. Mathematically:
$s1 = $r1 * $r1 + $r2
$r += $s1 * $s2
$r -= $s1 * $s2
$r = $s1 << $ul
$r = $s1 >> ul
Counts the number of bits set on $s1
Computes the hammin distance between $s1
and $s2
.
Returns the position of the first bit with value 0 starting at $start
.
Returns the position of the first bit with value 1 starting at $start
.
$cmp = $s1 <=> $s2
Returns true if $s1
is a perfect square
Computes the greatest common divisor of $sd1
and $sd2
.
The values of $sd1
and $sd2
are destroyed on the operation.
Those operations perform the same operations as the no _uint
counterparts but take as their third argument a native Perl unsigned int.
This is a very early release of this module, so it may contain lots of bugs.
If you find any use the CPAN RT system at http://rt.cpan.org to report them or just send my an email with the details.
For questions related to the usage of this module, post them at PerlMonks: http://perlmonks.org.
Math::GMPz, Math::Int128, Math::GMP, Math::Pari, Math::BigInt.
http://gmplib.org/manual/Low_002dlevel-Functions.html#Low_002dlevel-Functions.
http://perlmonks.org/?node_id=886488
Copyright (C) 2011 by Salvador Fañdino <sfandino@yahoo.com>
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.10.1 or, at your option, any later version of Perl 5 you may have available.