demos/perl/GMP.pm

# GMP perl module

# Copyright 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
#
# This file is part of the GNU MP Library.
#
# The GNU MP Library is free software; you can redistribute it and/or modify
# it under the terms of the GNU Lesser General Public License as published
# by the Free Software Foundation; either version 3 of the License, or (at
# your option) any later version.
#
# The GNU MP 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.  See the GNU Lesser General Public
# License for more details.
#
# You should have received a copy of the GNU Lesser General Public License
# along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.

# [Note: The above copyright notice is repeated in the documentation section
# below, in order to get it into man pages etc generated by the various pod
# conversions.  When changing, be sure to update below too.]


# This code is designed to work with perl 5.005, so it and the sub-packages
# aren't as modern as they could be.

package GMP;

require Symbol;
require Exporter;
require DynaLoader;
@ISA = qw(Exporter DynaLoader);

@EXPORT = qw();
@EXPORT_OK = qw(version);
%EXPORT_TAGS = ('all' => [qw(
                             get_d get_d_2exp get_si get_str integer_p
                             printf sgn sprintf)],
		'constants' => [()]);
Exporter::export_ok_tags('all');

$VERSION = '2.00';
bootstrap GMP $VERSION;


# The format string is cut up into "%" specifiers so GMP types can be
# passed to GMP::sprintf_internal.  Any "*"s are interpolated before
# calling sprintf_internal, which saves worrying about variable
# argument lists there.
#
# Because sprintf_internal is only called after the conversion and
# operand have been checked there won't be any crashes from a bad
# format string.
#
sub sprintf {
  my $fmt = shift;
  my $out = '';
  my ($pre, $dummy, $pat, $rest);

  while (($pre, $dummy, $pat, $rest) = ($fmt =~ /^((%%|[^%])*)(%[- +#.*hlLqv\d]*[bcdfeEgGinopsuxX])(.*)$/s)) {

    $out .= $pre;

    my $pat2 = $pat;    # $pat with "*"s expanded
    my @params = ();    # arguments per "*"s
    while ($pat2 =~ /[*]/) {
      my $arg = shift;
      $pat2 =~ s/[*]/$arg/;
      push @params, $arg;
    }

    if (UNIVERSAL::isa($_[0],"GMP::Mpz")) {
      if ($pat2 !~ /[dioxX]$/) {
	die "GMP::sprintf: unsupported output format for mpz: $pat2\n";
      }
      $pat2 =~ s/(.)$/Z$1/;
      $out .= sprintf_internal ($pat2, shift);

    } elsif (UNIVERSAL::isa($_[0],"GMP::Mpq")) {
      if ($pat2 !~ /[dioxX]$/) {
	die "GMP::sprintf: unsupported output format for mpq: $pat2\n";
      }
      $pat2 =~ s/(.)$/Q$1/;
      $out .= sprintf_internal ($pat2, shift);

    } elsif (UNIVERSAL::isa($_[0],"GMP::Mpf")) {
      if ($pat2 !~ /[eEfgG]$/) {
	die "GMP::sprintf: unsupported output format for mpf: $pat2\n";
      }
      $pat2 =~ s/(.)$/F$1/;
      $out .= sprintf_internal ($pat2, shift);

    } elsif ($pat =~ /n$/) {
      # do it this way so h, l or V type modifiers are respected, and use a
      # dummy variable to avoid a warning about discarding the value
      my $dummy = sprintf "%s$pat", $out, $_[0];
      shift;

    } else {
      $out .= sprintf $pat, @params, shift;
    }

    $fmt = $rest;
  }
  $out .= $fmt;
  return $out;
}

sub printf {
  if (ref($_[0]) eq 'GLOB') {
    my $h = Symbol::qualify_to_ref(shift, caller);
    print $h GMP::sprintf(@_);
  } else {
    print STDOUT GMP::sprintf(@_);
  }
}

1;
__END__


=head1 NAME

GMP - Perl interface to the GNU Multiple Precision Arithmetic Library

=head1 SYNOPSIS

    use GMP;
    use GMP::Mpz;
    use GMP::Mpq;
    use GMP::Mpf;
    use GMP::Rand;

=head1 DESCRIPTION

This module provides access to GNU MP arbitrary precision integers,
rationals and floating point.

No functions are exported from these packages by default, but can be
selected in the usual way, or the tag :all for everything.

    use GMP::Mpz qw(gcd, lcm);   # just these functions
    use GMP::Mpq qw(:all);       # everything in mpq

=head2 GMP::Mpz

This class provides arbitrary precision integers.  A new mpz can be
constructed with C<mpz>.  The initial value can be an integer, float,
string, mpz, mpq or mpf.  Floats, mpq and mpf will be automatically
truncated to an integer.

    use GMP::Mpz qw(:all);
    my $a = mpz(123);
    my $b = mpz("0xFFFF");
    my $c = mpz(1.5);       # truncated

The following overloaded operators are available, and corresponding
assignment forms like C<+=>,

=over 4

=item

+ - * / % E<lt>E<lt> E<gt>E<gt> ** & | ^ ! E<lt> E<lt>= == != E<gt> E<gt>=
E<lt>=E<gt> abs not sqrt

=back

C</> and C<%> round towards zero (as per the C<tdiv> functions in GMP).

The following functions are available, behaving the same as the
corresponding GMP mpz functions,

=over 4

=item

bin, cdiv, cdiv_2exp, clrbit, combit, congruent_p, congruent_2exp_p,
divexact, divisible_p, divisible_2exp_p, even_p, fac, fdiv, fdiv_2exp, fib,
fib2, gcd, gcdext, hamdist, invert, jacobi, kronecker, lcm, lucnum, lucnum2,
mod, mpz_export, mpz_import, nextprime, odd_p, perfect_power_p,
perfect_square_p, popcount, powm, probab_prime_p, realloc, remove, root,
roote, scan0, scan1, setbit, sizeinbase, sqrtrem, tdiv, tdiv_2exp, tstbit

=back

C<cdiv>, C<fdiv> and C<tdiv> and their C<2exp> variants return a
quotient/remainder pair.  C<fib2> returns a pair F[n] and F[n-1], similarly
C<lucnum2>.  C<gcd> and C<lcm> accept a variable number of arguments (one or
more).  C<gcdext> returns a triplet of gcd and two cofactors, for example

    use GMP::Mpz qw(:all);
    $a = 7257;
    $b = 10701;
    ($g, $x, $y) = gcdext ($a, $b);
    print "gcd($a,$b) is $g, and $g == $a*$x + $b*$y\n";

C<mpz_import> and C<mpz_export> are so named to avoid the C<import> keyword.
Their parameters are as follows,

    $z = mpz_import ($order, $size, $endian, $nails, $string);
    $string = mpz_export ($order, $size, $endian, $nails, $z);

The order, size, endian and nails parameters are as per the corresponding C
functions.  The string input for C<mpz_import> is interpreted as byte data
and must be a multiple of $size bytes.  C<mpz_export> conversely returns a
string of byte data, which will be a multiple of $size bytes.

C<invert> returns the inverse, or undef if it doesn't exist.  C<remove>
returns a remainder/multiplicity pair.  C<root> returns the nth root, and
C<roote> returns a root/bool pair, the bool indicating whether the root is
exact.  C<sqrtrem> and C<rootrem> return a root/remainder pair.

C<clrbit>, C<combit> and C<setbit> expect a variable which they can modify,
it doesn't make sense to pass a literal constant.  Only the given variable
is modified, if other variables are referencing the same mpz object then a
new copy is made of it.  If the variable isn't an mpz it will be coerced to
one.  For instance,

    use GMP::Mpz qw(setbit);
    setbit (123, 0);  # wrong, don't pass a constant
    $a = mpz(6);
    $b = $a;
    setbit ($a, 0);   # $a becomes 7, $b stays at 6

C<scan0> and C<scan1> return ~0 if no 0 or 1 bit respectively is found.

=head2 GMP::Mpq

This class provides rationals with arbitrary precision numerators and
denominators.  A new mpq can be constructed with C<mpq>.  The initial value
can be an integer, float, string, mpz, mpq or mpf, or a pair of integers or
mpz's.  No precision is lost when converting a float or mpf, the exact value
is retained.

    use GMP::Mpq qw(:all);
    $a = mpq();              # zero
    $b = mpq(0.5);           # gives 1/2
    $b = mpq(14);            # integer 14
    $b = mpq(3,4);           # fraction 3/4
    $b = mpq("7/12");        # fraction 7/12
    $b = mpq("0xFF/0x100");  # fraction 255/256

When a fraction is given, it should be in the canonical form specified in
the GMP manual, which is denominator positive, no common factors, and zero
always represented as 0/1.  If not then C<canonicalize> can be called to put
it in that form.  For example,

    use GMP::Mpq qw(:all);
    $q = mpq(21,15);   # eek! common factor 3
    canonicalize($q);  # get rid of it

The following overloaded operators are available, and corresponding
assignment forms like C<+=>,

=over 4

=item

+ - * / E<lt>E<lt> E<gt>E<gt> ** ! E<lt> E<lt>= == != E<gt> E<gt>=
E<lt>=E<gt> abs not

=back

The following functions are available,

=over 4

=item

den, inv, num

=back

C<inv> calculates 1/q, as per the corresponding GMP function.  C<num> and
C<den> return an mpz copy of the numerator or denominator respectively.  In
the future C<num> and C<den> might give lvalues so the original mpq can be
modified through them, but this is not done currently.

=head2 GMP::Mpf

This class provides arbitrary precision floating point numbers.  The
mantissa is an arbitrary user-selected precision and the exponent is a fixed
size (one machine word).

A new mpf can be constructed with C<mpf>.  The initial value can be an
integer, float, string, mpz, mpq or mpf.  The second argument specifies the
desired precision in bits, or if omitted then the default precision is used.

    use GMP::Mpf qw(:all);
    $a = mpf();         # zero
    $b = mpf(-7.5);     # default precision
    $c = mpf(1.5, 500); # 500 bits precision
    $d = mpf("1.0000000000000001");

The following overloaded operators are available, with the corresponding
assignment forms like C<+=>,

=over 4

=item

+ - * / E<lt>E<lt> E<gt>E<gt> ** ! E<lt> E<lt>= == != E<gt> E<gt>=
E<lt>=E<gt> abs not sqrt

=back

The following functions are available, behaving the same as the
corresponding GMP mpf functions,

=over 4

=item

ceil, floor, get_default_prec, get_prec, mpf_eq, set_default_prec, set_prec,
trunc

=back

C<mpf_eq> is so named to avoid clashing with the perl C<eq> operator.

C<set_prec> expects a variable which it can modify, it doesn't make sense to
pass a literal constant.  Only the given variable is modified, if other
variables are referencing the same mpf object then a new copy is made of it.
If the variable isn't an mpf it will be coerced to one.

Results are the same precision as inputs, or if two mpf's are given to a
binary operator then the precision of the first is used.  For example,

    use GMP::Mpf qw(mpf);
    $a = mpf(2.0, 100);
    $b = mpf(2.0, 500);
    $c = $a + $b;         # gives 100 bits precision

Mpf to string conversion via "" or the usual string contexts uses C<$#> the
same as normal float to string conversions, or defaults to C<%.g> if C<$#>
is not defined.  C<%.g> means all significant digits in the selected
precision.

=head2 GMP class

The following functions are available in the GMP class,

=over 4

=item

fits_slong_p, get_d, get_d_2exp, get_si, get_str, integer_p, printf, sgn,
sprintf, version

=back

C<get_d_2exp> accepts any integer, string, float, mpz, mpq or mpf operands
and returns a float and an integer exponent,

    ($dbl, $exp) = get_d_2exp (mpf ("3.0"));
    # dbl is 0.75, exp is 2

C<get_str> takes an optional second argument which is the base, defaulting
to decimal.  A negative base means upper case, as per the C functions.  For
integer, integer string, mpz or mpq operands a string is returned.

    use GMP qw(:all);
    use GMP::Mpq qw(:all);
    print get_str(mpq(-5,8)),"\n";      # -5/8
    print get_str(255,16),"\n";         # ff

For float, float strings or mpf operands, C<get_str> accepts an optional
third parameter being how many digits to produce, defaulting to 0 which
means all digits.  (Only as many digits as can be accurately represented by
the float precision are ever produced though.)  A string/exponent pair is
returned, as per the C mpf_get_str function.  For example,

    use GMP qw(:all);
    use GMP::Mpf qw(:all);
    ($s, $e) = get_str(111.111111111, 10, 4);
    printf ".$se$e\n";                  # .1111e3
    ($s, $e) = get_str(1.625, 10);
    print "0.$s*10^$e\n";               # 0.1625*10^1
    ($s, $e) = get_str(mpf(2)**20, 16);
    printf ".%s@%x\n", $s, $e;          # .1@14

C<printf> and C<sprintf> allow formatted output of GMP types.  mpz and mpq
values can be used with integer conversions (d, o, x, X) and mpf with float
conversions (f, e, E, g, G).  All the standard perl printf features are
available too.  For example,

    use GMP::Mpz qw(mpz);
    use GMP::Mpf qw(mpf);
    GMP::printf ("%d %d %s", 123, mpz(2)**128, 'foo');
    GMP::printf STDERR "%.40f", mpf(1.234);

In perl 5.6.1 it doesn't seem to work to export C<printf>, the plain builtin
C<printf> is reached unless calls are C<&printf()> style.  Explicit use of
C<GMP::printf> is suggested.  C<sprintf> doesn't suffer this problem.

    use GMP qw(sprintf);
    use GMP::Mpq qw(mpq);
    $s = sprintf "%x", mpq(15,16);

C<version> is not exported by default or by tag :all, calling it as
C<GMP::version()> is recommended.  It returns the GMP library version
string, which is not to be confused with the module version number.

The other GMP module functions behave as per the corresponding GMP routines,
and accept any integer, string, float, mpz, mpq or mpf.  For example,

    use GMP qw(:all);
    use GMP::Mpz qw(mpz);
    $z = mpz(123);
    print sgn($z);    # gives 1

Because each of GMP::Mpz, GMP::Mpq and GMP::Mpf is a sub-class of GMP,
C<-E<gt>> style calls work too.

    use GMP qw(:all);
    use GMP::Mpq qw(mpf);
    $q = mpq(-5,7);
    if ($q->integer_p())   # false
      ...

=head2 GMP::Rand

This class provides objects holding an algorithm and state for random number
generation.  C<randstate> creates a new object, for example,

    use GMP::Rand qw(randstate);
    $r = randstate();
    $r = randstate('lc_2exp_size', 64);
    $r = randstate('lc_2exp', 43840821, 1, 32);
    $r = randstate('mt');
    $r = randstate($another_r);

With no parameters this corresponds to the C function
C<gmp_randinit_default>, and is a compromise between speed and randomness.
'lc_2exp_size' corresponds to C<gmp_randinit_lc_2exp_size>, 'lc_2exp'
corresponds to C<gmp_randinit_lc_2exp>, and 'mt' corresponds to
C<gmp_randinit_mt>.  Or when passed another randstate object, a copy of that
object is made.

'lc_2exp_size' can fail if the requested size is bigger than the internal
table provides for, in which case undef is returned.  The maximum size
currently supported is 128.  The other forms always succeed.

A randstate can be seeded with an integer or mpz, using the C<seed> method.
/dev/random might be a good source of randomness, or time() or
Time::HiRes::time() might be adequate, depending on the application.

    $r->seed(time()));

Random numbers can be generated with the following functions,

=over 4

=item

mpf_urandomb, mpz_rrandomb, mpz_urandomb, mpz_urandomm,
gmp_urandomb_ui, gmp_urandomm_ui

=back

Each constructs a new mpz or mpf and with a distribution per the
corresponding GMP function.  For example,

    use GMP::Rand (:all);
    $r = randstate();
    $a = mpz_urandomb($r,256);         # uniform mpz, 256 bits
    $b = mpz_urandomm($r,mpz(3)**100); # uniform mpz, 0 to 3**100-1
    $c = mpz_rrandomb($r,1024);        # special mpz, 1024 bits
    $f = mpf_urandomb($r,128);         # uniform mpf, 128 bits, 0<=$f<1
    $f = gmp_urandomm_ui($r,56);       # uniform int, 0 to 55

=head2 Coercion

Arguments to operators and functions are converted as necessary to the
appropriate type.  For instance C<**> requires an unsigned integer exponent,
and an mpq argument will be converted, so long as it's an integer in the
appropriate range.

    use GMP::Mpz (mpz);
    use GMP::Mpq (mpq);
    $p = mpz(3) ** mpq(45);   # allowed, 45 is an integer

It's an error if a conversion to an integer or mpz would cause any
truncation.  For example,

    use GMP::Mpz (mpz);
    $p = mpz(3) + 1.25;       # not allowed
    $p = mpz(3) + mpz(1.25);  # allowed, explicit truncation

Comparisons, however, accept any combination of operands and are always done
exactly.  For example,

    use GMP::Mpz (mpz);
    print mpz(3) < 3.1;       # true

Variables used on the left of an assignment operator like C<+=> are subject
to coercion too.  An integer, float or string will change type when an mpz,
mpq or mpf is applied to it.  For example,

    use GMP::Mpz (mpz);
    $a = 1;
    $a += mpz(1234);   # $a becomes an mpz

=head2 Overloading

The rule for binary operators in the C<overload> mechanism is that if both
operands are class objects then the method from the first is used.  This
determines the result type when mixing GMP classes.  For example,

    use GMP::Mpz (mpz);
    use GMP::Mpq (mpq);
    use GMP::Mpf (mpf);
    $z = mpz(123);
    $q = mpq(3,2);
    $f = mpf(1.375)
    print $q+$f;     # gives an mpq
    print $f+$z;     # gives an mpf
    print $z+$f;     # not allowed, would lose precision

=head2 Constants

A special tag C<:constants> is recognised in the module exports list.  It
doesn't select any functions, but indicates that perl constants should be
GMP objects.  This can only be used on one of GMP::Mpz, GMP::Mpq or GMP::Mpf
at any one time, since they apply different rules.

GMP::Mpz will treat constants as mpz's if they're integers, or ordinary
floats if not.  For example,

    use GMP::Mpz qw(:constants);
    print 764861287634126387126378128,"\n";   # an mpz
    print 1.25,"\n";                          # a float

GMP::Mpq is similar, treating integers as mpq's and leaving floats to the
normal perl handling.  Something like 3/4 is read as two integer mpq's and a
division, but that's fine since it gives the intended fraction.

    use GMP::Mpq qw(:constants);
    print 3/4,"\n";    # an mpq
    print 1.25,"\n";   # a float

GMP::Mpf will treat all constants as mpf's using the default precision.
BEGIN blocks can be used to set that precision while the code is parsed.
For example,

    use GMP::Mpf qw(:constants);
    BEGIN { GMP::Mpf::set_default_prec(256); }
    print 1/3;
    BEGIN { GMP::Mpf::set_default_prec(64); }
    print 5/7;

A similar special tag :noconstants is recognised to turn off the constants
feature.  For example,

    use GMP::Mpz qw(:constants);
    print 438249738748174928193,"\n";   # an mpz
    use GMP::Mpz qw(:noconstants);
    print 438249738748174928193,"\n";   # now a float

All three 'integer', 'binary' and 'float' constant methods are captured.
'float' is captured even for GMP::Mpz and GMP::Mpq since perl by default
treats integer strings as floats if they don't fit a plain integer.

=head1 SEE ALSO

GMP manual, L<perl>, L<overload>.

=head1 BUGS

In perl 5.005_03 on i386 FreeBSD, the overloaded constants sometimes provoke
seg faults.  Don't know if that's a perl bug or a GMP module bug, though it
does seem to go bad before reaching anything in GMP.xs.

There's no way to specify an arbitrary base when converting a string to an
mpz (or mpq or mpf), only hex or octal with 0x or 0 (for mpz and mpq, but
not for mpf).

These modules are not reentrant or thread safe, due to the implementation of
the XSUBs.

Returning a new object from the various functions is convenient, but
assignment versions could avoid creating new objects.  Perhaps they could be
named after the C language functions, eg. mpq_inv($q,$q);

It'd be good if C<num> and C<den> gave lvalues so the underlying mpq could
be manipulated.

C<printf> could usefully accept %b for mpz, mpq and mpf, and perhaps %x for
mpf too.

C<get_str> returning different style values for integer versus float is a
bit unfortunate.  With mpz, mpq and mpf objects there's no doubt what it
will do, but on a plain scalar its action depends on whether the scalar was
promoted to a float at any stage, and then on the GMP module rules about
using the integer or float part.

=head1 INTERNALS

In usual perl object style, an mpz is a reference to an object blessed into
class C<GMP::Mpz>.  The object holds a pointer to the C language C<mpz_t>
structure.  Similarly for mpq, mpf and randstate.

A free list of mpz and mpq values is kept to avoid repeated initializing and
clearing when objects are created and destroyed.  This aims to help speed,
but it's not clear whether it's really needed.

mpf doesn't use a free list because the precision of new objects can be
different each time.

No interface to C<mpf_set_prec_raw> is provided.  It wouldn't be very useful
since there's no way to make an operation store its result in a particular
object.  The plain C<set_prec> is useful though, for truncating to a lower
precision, or as a sort of directive that subsequent calculations involving
that variable should use a higher precision.

The overheads of perl dynamic typing (operator dispatch, operand type
checking or coercion) will mean this interface is slower than using C
directly.

Some assertion checking is available as a compile-time option.

=head1 COPYRIGHT

Copyright 2001, 2002, 2003, 2004 Free Software Foundation, Inc.

This file is part of the GNU MP Library.

The GNU MP Library is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published
by the Free Software Foundation; either version 3 of the License, or (at
your option) any later version.

The GNU MP 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.  See the GNU Lesser General Public
License for more details.

You should have received a copy of the GNU Lesser General Public License
along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.

=cut

# Local variables:
# perl-indent-level: 2
# fill-column: 76
# End: