summaryrefslogtreecommitdiff
path: root/Master/tlpkg/tlperl/lib/Math
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2012-05-21 00:15:27 +0000
committerKarl Berry <karl@freefriends.org>2012-05-21 00:15:27 +0000
commita4c42bfb2337d37da89d789cb8cc226367994e32 (patch)
treec3eabdef5d565a4e515d2be0d9d4d0540bde0250 /Master/tlpkg/tlperl/lib/Math
parent8274475057f024d35332ac47c2e2f23ea156e6ed (diff)
perl 5.14.2 from siep
git-svn-id: svn://tug.org/texlive/trunk@26525 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/tlpkg/tlperl/lib/Math')
-rw-r--r--Master/tlpkg/tlperl/lib/Math/BigFloat.pm255
-rw-r--r--Master/tlpkg/tlperl/lib/Math/BigInt.pm599
-rw-r--r--Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm822
-rw-r--r--Master/tlpkg/tlperl/lib/Math/BigInt/CalcEmu.pm6
-rw-r--r--Master/tlpkg/tlperl/lib/Math/BigInt/FastCalc.pm51
-rw-r--r--Master/tlpkg/tlperl/lib/Math/BigRat.pm106
6 files changed, 1227 insertions, 612 deletions
diff --git a/Master/tlpkg/tlperl/lib/Math/BigFloat.pm b/Master/tlpkg/tlperl/lib/Math/BigFloat.pm
index 27d60b3143c..06a6e48417c 100644
--- a/Master/tlpkg/tlperl/lib/Math/BigFloat.pm
+++ b/Master/tlpkg/tlperl/lib/Math/BigFloat.pm
@@ -12,8 +12,8 @@ package Math::BigFloat;
# _a : accuracy
# _p : precision
-$VERSION = '1.60';
-require 5.006;
+$VERSION = '1.993';
+require 5.006002;
require Exporter;
@ISA = qw/Math::BigInt/;
@@ -60,7 +60,7 @@ $upgrade = undef;
$downgrade = undef;
# the package we are using for our private parts, defaults to:
# Math::BigInt->config()->{lib}
-my $MBI = 'Math::BigInt::FastCalc';
+my $MBI = 'Math::BigInt::Calc';
# are NaNs ok? (otherwise it dies when encountering an NaN) set w/ config()
$_trap_nan = 0;
@@ -149,7 +149,7 @@ sub new
$self->{sign} = $wanted->sign();
return $self->bnorm();
}
- # else: got a string or something maskerading as number (with overload)
+ # else: got a string or something masquerading as number (with overload)
# handle '+inf', '-inf' first
if ($wanted =~ /^[+-]?inf\z/)
@@ -353,7 +353,7 @@ sub config
}
##############################################################################
-# string conversation
+# string conversion
sub bstr
{
@@ -473,6 +473,7 @@ sub bcmp
# set up parameters
my ($self,$x,$y) = (ref($_[0]),@_);
+
# objectify is costly, so avoid it
if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
{
@@ -482,58 +483,150 @@ sub bcmp
return $upgrade->bcmp($x,$y) if defined $upgrade &&
((!$x->isa($self)) || (!$y->isa($self)));
- if (($x->{sign} !~ /^[+-]$/) || ($y->{sign} !~ /^[+-]$/))
- {
- # handle +-inf and NaN
- return undef if (($x->{sign} eq $nan) || ($y->{sign} eq $nan));
- return 0 if ($x->{sign} eq $y->{sign}) && ($x->{sign} =~ /^[+-]inf$/);
- return +1 if $x->{sign} eq '+inf';
- return -1 if $x->{sign} eq '-inf';
- return -1 if $y->{sign} eq '+inf';
- return +1;
- }
+ # Handle all 'nan' cases.
- # check sign for speed first
- return 1 if $x->{sign} eq '+' && $y->{sign} eq '-'; # does also 0 <=> -y
- return -1 if $x->{sign} eq '-' && $y->{sign} eq '+'; # does also -x <=> 0
+ return undef if ($x->{sign} eq $nan) || ($y->{sign} eq $nan);
+
+ # Handle all '+inf' and '-inf' cases.
+
+ return 0 if ($x->{sign} eq '+inf' && $y->{sign} eq '+inf' ||
+ $x->{sign} eq '-inf' && $y->{sign} eq '-inf');
+ return +1 if $x->{sign} eq '+inf'; # x = +inf and y < +inf
+ return -1 if $x->{sign} eq '-inf'; # x = -inf and y > -inf
+ return -1 if $y->{sign} eq '+inf'; # x < +inf and y = +inf
+ return +1 if $y->{sign} eq '-inf'; # x > -inf and y = -inf
+
+ # Handle all cases with opposite signs.
+
+ return +1 if $x->{sign} eq '+' && $y->{sign} eq '-'; # also does 0 <=> -y
+ return -1 if $x->{sign} eq '-' && $y->{sign} eq '+'; # also does -x <=> 0
+
+ # Handle all remaining zero cases.
- # shortcut
my $xz = $x->is_zero();
my $yz = $y->is_zero();
- return 0 if $xz && $yz; # 0 <=> 0
- return -1 if $xz && $y->{sign} eq '+'; # 0 <=> +y
- return 1 if $yz && $x->{sign} eq '+'; # +x <=> 0
+ return 0 if $xz && $yz; # 0 <=> 0
+ return -1 if $xz && $y->{sign} eq '+'; # 0 <=> +y
+ return +1 if $yz && $x->{sign} eq '+'; # +x <=> 0
+
+ # Both arguments are now finite, non-zero numbers with the same sign.
+
+ my $cmp;
+
+ # The next step is to compare the exponents, but since each mantissa is an
+ # integer of arbitrary value, the exponents must be normalized by the length
+ # of the mantissas before we can compare them.
+
+ my $mxl = $MBI->_len($x->{_m});
+ my $myl = $MBI->_len($y->{_m});
+
+ # If the mantissas have the same length, there is no point in normalizing the
+ # exponents by the length of the mantissas, so treat that as a special case.
+
+ if ($mxl == $myl) {
+
+ # First handle the two cases where the exponents have different signs.
+
+ if ($x->{_es} eq '+' && $y->{_es} eq '-') {
+ $cmp = +1;
+ }
+
+ elsif ($x->{_es} eq '-' && $y->{_es} eq '+') {
+ $cmp = -1;
+ }
+
+ # Then handle the case where the exponents have the same sign.
+
+ else {
+ $cmp = $MBI->_acmp($x->{_e}, $y->{_e});
+ $cmp = -$cmp if $x->{_es} eq '-';
+ }
+
+ # Adjust for the sign, which is the same for x and y, and bail out if
+ # we're done.
+
+ $cmp = -$cmp if $x->{sign} eq '-'; # 124 > 123, but -124 < -123
+ return $cmp if $cmp;
+
+ }
+
+ # We must normalize each exponent by the length of the corresponding
+ # mantissa. Life is a lot easier if we first make both exponents
+ # non-negative. We do this by adding the same positive value to both
+ # exponent. This is safe, because when comparing the exponents, only the
+ # relative difference is important.
+
+ my $ex;
+ my $ey;
+
+ if ($x->{_es} eq '+') {
+
+ # If the exponent of x is >= 0 and the exponent of y is >= 0, there is no
+ # need to do anything special.
+
+ if ($y->{_es} eq '+') {
+ $ex = $MBI->_copy($x->{_e});
+ $ey = $MBI->_copy($y->{_e});
+ }
+
+ # If the exponent of x is >= 0 and the exponent of y is < 0, add the
+ # absolute value of the exponent of y to both.
+
+ else {
+ $ex = $MBI->_copy($x->{_e});
+ $ex = $MBI->_add($ex, $y->{_e}); # ex + |ey|
+ $ey = $MBI->_zero(); # -ex + |ey| = 0
+ }
+
+ } else {
+
+ # If the exponent of x is < 0 and the exponent of y is >= 0, add the
+ # absolute value of the exponent of x to both.
+
+ if ($y->{_es} eq '+') {
+ $ex = $MBI->_zero(); # -ex + |ex| = 0
+ $ey = $MBI->_copy($y->{_e});
+ $ey = $MBI->_add($ey, $x->{_e}); # ey + |ex|
+ }
+
+ # If the exponent of x is < 0 and the exponent of y is < 0, add the
+ # absolute values of both exponents to both exponents.
+
+ else {
+ $ex = $MBI->_copy($y->{_e}); # -ex + |ey| + |ex| = |ey|
+ $ey = $MBI->_copy($x->{_e}); # -ey + |ex| + |ey| = |ex|
+ }
+
+ }
+
+ # Now we can normalize the exponents by adding lengths of the mantissas.
+
+ $MBI->_add($ex, $MBI->_new($mxl));
+ $MBI->_add($ey, $MBI->_new($myl));
+
+ # We're done if the exponents are different.
+
+ $cmp = $MBI->_acmp($ex, $ey);
+ $cmp = -$cmp if $x->{sign} eq '-'; # 124 > 123, but -124 < -123
+ return $cmp if $cmp;
+
+ # Compare the mantissas, but first normalize them by padding the shorter
+ # mantissa with zeros (shift left) until it has the same length as the longer
+ # mantissa.
+
+ my $mx = $x->{_m};
+ my $my = $y->{_m};
+
+ if ($mxl > $myl) {
+ $my = $MBI->_lsft($MBI->_copy($my), $MBI->_new($mxl - $myl), 10);
+ } elsif ($mxl < $myl) {
+ $mx = $MBI->_lsft($MBI->_copy($mx), $MBI->_new($myl - $mxl), 10);
+ }
+
+ $cmp = $MBI->_acmp($mx, $my);
+ $cmp = -$cmp if $x->{sign} eq '-'; # 124 > 123, but -124 < -123
+ return $cmp;
- # adjust so that exponents are equal
- my $lxm = $MBI->_len($x->{_m});
- my $lym = $MBI->_len($y->{_m});
- # the numify somewhat limits our length, but makes it much faster
- my ($xes,$yes) = (1,1);
- $xes = -1 if $x->{_es} ne '+';
- $yes = -1 if $y->{_es} ne '+';
- my $lx = $lxm + $xes * $MBI->_num($x->{_e});
- my $ly = $lym + $yes * $MBI->_num($y->{_e});
- my $l = $lx - $ly; $l = -$l if $x->{sign} eq '-';
- return $l <=> 0 if $l != 0;
-
- # lengths (corrected by exponent) are equal
- # so make mantissa equal length by padding with zero (shift left)
- my $diff = $lxm - $lym;
- my $xm = $x->{_m}; # not yet copy it
- my $ym = $y->{_m};
- if ($diff > 0)
- {
- $ym = $MBI->_copy($y->{_m});
- $ym = $MBI->_lsft($ym, $MBI->_new($diff), 10);
- }
- elsif ($diff < 0)
- {
- $xm = $MBI->_copy($x->{_m});
- $xm = $MBI->_lsft($xm, $MBI->_new(-$diff), 10);
- }
- my $rc = $MBI->_acmp($xm,$ym);
- $rc = -$rc if $x->{sign} eq '-'; # -124 < -123
- $rc <=> 0;
}
sub bacmp
@@ -1141,7 +1234,7 @@ sub _log
# in case of $x == 1, result is 0
return $x->bzero() if $x->is_one();
- # XXX TODO: rewrite this in a similiar manner to bexp()
+ # XXX TODO: rewrite this in a similar manner to bexp()
# http://www.efunda.com/math/taylor_series/logarithmic.cfm?search_string=log
@@ -1604,12 +1697,7 @@ sub bmuladd
# multiply two numbers and add the third to the result
# set up parameters
- my ($self,$x,$y,$z,@r) = (ref($_[0]),@_);
- # objectify is costly, so avoid it
- if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
- {
- ($self,$x,$y,$z,@r) = objectify(3,@_);
- }
+ my ($self,$x,$y,$z,@r) = objectify(3,@_);
return $x if $x->modify('bmuladd');
@@ -1759,7 +1847,7 @@ sub bdiv
$y->{sign} =~ tr/+-/-+/;
# continue with normal div code:
- # make copy of $x in case of list context for later reminder calculation
+ # make copy of $x in case of list context for later remainder calculation
if (wantarray && $y_not_one)
{
$rem = $x->copy();
@@ -1821,7 +1909,7 @@ sub bdiv
sub bmod
{
- # (dividend: BFLOAT or num_str, divisor: BFLOAT or num_str) return reminder
+ # (dividend: BFLOAT or num_str, divisor: BFLOAT or num_str) return remainder
# set up parameters
my ($self,$x,$y,$a,$p,$r) = (ref($_[0]),@_);
@@ -2128,7 +2216,7 @@ sub bsqrt
}
# sqrt(2) = 1.4 because sqrt(2*100) = 1.4*10; so we can increase the accuracy
- # of the result by multipyling the input by 100 and then divide the integer
+ # of the result by multiplying the input by 100 and then divide the integer
# result of sqrt(input) by 10. Rounding afterwards returns the real result.
# The following steps will transform 123.456 (in $x) into 123456 (in $y1)
@@ -2408,7 +2496,7 @@ sub bpow
sub bmodpow
{
# takes a very large number to a very large exponent in a given very
- # large modulus, quickly, thanks to binary exponentation. Supports
+ # large modulus, quickly, thanks to binary exponentiation. Supports
# negative exponents.
my ($self,$num,$exp,$mod,@r) = objectify(3,@_);
@@ -3372,7 +3460,7 @@ sub brsft
# negative amount?
return $x->blsft($y->copy()->babs(),$n) if $y->{sign} =~ /^-/;
- # the following call to bdiv() will return either quo or (quo,reminder):
+ # the following call to bdiv() will return either quo or (quo,remainder):
$x->bdiv($n->bpow($y),$a,$p,$r,$y);
}
@@ -3684,6 +3772,9 @@ sub as_number
$x = $x->can('as_float') ? $x->as_float() : $self->new(0+"$x");
}
+ return Math::BigInt->binf($x->sign()) if $x->is_inf();
+ return Math::BigInt->bnan() if $x->is_nan();
+
my $z = $MBI->_copy($x->{_m});
if ($x->{_es} eq '-') # < 0
{
@@ -3693,7 +3784,7 @@ sub as_number
{
$MBI->_lsft( $z, $x->{_e},10);
}
- $z = Math::BigInt->new( $x->{sign} . $MBI->_num($z));
+ $z = Math::BigInt->new( $x->{sign} . $MBI->_str($z));
$z;
}
@@ -3768,7 +3859,7 @@ Math::BigFloat - Arbitrary size floating point math package
# The following all modify their first argument. If you want to preserve
# $x, use $z = $x->copy()->bXXX($y); See under L<CAVEATS> for why this is
# necessary when mixing $a = $b assignments with non-overloaded math.
-
+
# set
$x->bzero(); # set $i to 0
$x->bnan(); # set $i to NaN
@@ -3783,7 +3874,7 @@ Math::BigFloat - Arbitrary size floating point math package
$x->bnot(); # two's complement (bit wise not)
$x->binc(); # increment x by 1
$x->bdec(); # decrement x by 1
-
+
$x->badd($y); # addition (add $y to $x)
$x->bsub($y); # subtraction (subtract $y from $x)
$x->bmul($y); # multiplication (multiply $x by $y)
@@ -3792,24 +3883,24 @@ Math::BigFloat - Arbitrary size floating point math package
$x->bmod($y); # modulus ($x % $y)
$x->bpow($y); # power of arguments ($x ** $y)
- $x->bmodpow($exp,$mod); # modular exponentation (($num**$exp) % $mod))
+ $x->bmodpow($exp,$mod); # modular exponentiation (($num**$exp) % $mod))
$x->blsft($y, $n); # left shift by $y places in base $n
$x->brsft($y, $n); # right shift by $y places in base $n
# returns (quo,rem) or quo if in scalar context
-
+
$x->blog(); # logarithm of $x to base e (Euler's number)
$x->blog($base); # logarithm of $x to base $base (f.i. 2)
$x->bexp(); # calculate e ** $x where e is Euler's number
-
+
$x->band($y); # bit-wise and
$x->bior($y); # bit-wise inclusive or
$x->bxor($y); # bit-wise exclusive or
$x->bnot(); # bit-wise not (two's complement)
-
+
$x->bsqrt(); # calculate square-root
$x->broot($y); # $y'th root of $x (e.g. $y == 3 => cubic root)
$x->bfac(); # factorial of $x (1*2*3*4*..$x)
-
+
$x->bround($N); # accuracy: preserve $N digits
$x->bfround($N); # precision: round to the $Nth digit
@@ -3820,7 +3911,7 @@ Math::BigFloat - Arbitrary size floating point math package
bgcd(@values); # greatest common divisor
blcm(@values); # lowest common multiplicator
-
+
$x->bstr(); # return string
$x->bsstr(); # return string in scientific notation
@@ -3830,7 +3921,7 @@ Math::BigFloat - Arbitrary size floating point math package
$x->parts(); # return (mantissa,exponent) as BigInt
$x->length(); # number of digits (w/o sign and '.')
- ($l,$f) = $x->length(); # number of digits, and length of fraction
+ ($l,$f) = $x->length(); # number of digits, and length of fraction
$x->precision(); # return P of $x (or global, if P of $x undef)
$x->precision($n); # set P of $x to $n
@@ -3905,7 +3996,7 @@ Some routines (C<is_odd()>, C<is_even()>, C<is_zero()>, C<is_one()>,
C<is_nan()>) return true or false, while others (C<bcmp()>, C<bacmp()>)
return either undef, <0, 0 or >0 and are suited for sort.
-Actual math is done by using the class defined with C<with => Class;> (which
+Actual math is done by using the class defined with C<< with => Class; >> (which
defaults to BigInts) to represent the mantissa and exponent.
The sign C</^[+-]$/> is stored separately. The string 'NaN' is used to
@@ -3943,7 +4034,7 @@ Since things like C<sqrt(2)> or C<1 / 3> must presented with a limited
accuracy lest a operation consumes all resources, each operation produces
no more than the requested number of digits.
-If there is no gloabl precision or accuracy set, B<and> the operation in
+If there is no global precision or accuracy set, B<and> the operation in
question was not called with a requested precision or accuracy, B<and> the
input $x has no accuracy or precision set, then a fallback parameter will
be used. For historical reasons, it is called C<div_scale> and can be accessed
@@ -3975,14 +4066,14 @@ It is less confusing to either calculate the result fully, and afterwards
round it explicitly, or use the additional parameters to the math
functions like so:
- use Math::BigFloat;
+ use Math::BigFloat;
$x = Math::BigFloat->new(2);
$y = $x->copy()->bdiv(3);
print $y->bround(5),"\n"; # will give 0.66667
or
- use Math::BigFloat;
+ use Math::BigFloat;
$x = Math::BigFloat->new(2);
$y = $x->copy()->bdiv(3,5); # will give 0.66667
print "$y\n";
@@ -4156,7 +4247,7 @@ This method was added in v1.87 of Math::BigInt (June 2007).
=head2 bmuladd()
- $x->bmuladd($y,$z);
+ $x->bmuladd($y,$z);
Multiply $x by $y, and then add $z to the result.
@@ -4241,7 +4332,7 @@ request a different storage class for use with Math::BigFloat:
use Math::BigFloat with => 'Math::BigInt::Lite';
However, this request is ignored, as the current code now uses the low-level
-math libary for directly storing the number parts.
+math library for directly storing the number parts.
=head1 EXPORTS
@@ -4284,9 +4375,9 @@ The following will probably not print what you expect:
print $c->bdiv(123.456),"\n";
-It prints both quotient and reminder since print works in list context. Also,
+It prints both quotient and remainder since print works in list context. Also,
bdiv() will modify $c, so be careful. You probably want to use
-
+
print $c / 123.456,"\n";
print scalar $c->bdiv(123.456),"\n"; # or if you want to modify $c
diff --git a/Master/tlpkg/tlperl/lib/Math/BigInt.pm b/Master/tlpkg/tlperl/lib/Math/BigInt.pm
index f97e4380798..62c021ecf71 100644
--- a/Master/tlpkg/tlperl/lib/Math/BigInt.pm
+++ b/Master/tlpkg/tlperl/lib/Math/BigInt.pm
@@ -6,7 +6,7 @@ package Math::BigInt;
#
# The following hash values are used:
-# value: unsigned int with actual value (as a Math::BigInt::Calc or similiar)
+# value: unsigned int with actual value (as a Math::BigInt::Calc or similar)
# sign : +,-,NaN,+inf,-inf
# _a : accuracy
# _p : precision
@@ -16,9 +16,9 @@ package Math::BigInt;
# underlying lib might change the reference!
my $class = "Math::BigInt";
-use 5.006;
+use 5.006002;
-$VERSION = '1.89_01';
+$VERSION = '1.994';
@ISA = qw(Exporter);
@EXPORT_OK = qw(objectify bgcd blcm);
@@ -30,7 +30,7 @@ use vars qw/$round_mode $accuracy $precision $div_scale $rnd_mode
use strict;
# Inside overload, the first arg is always an object. If the original code had
-# it reversed (like $x = 2 * $y), then the third paramater is true.
+# it reversed (like $x = 2 * $y), then the third parameter is true.
# In some cases (like add, $x = $x + 2 is the same as $x = 2 + $x) this makes
# no difference, but in some cases it does.
@@ -172,8 +172,8 @@ $_trap_nan = 0; # are NaNs ok? set w/ config()
$_trap_inf = 0; # are infs ok? set w/ config()
my $nan = 'NaN'; # constants for easier life
-my $CALC = 'Math::BigInt::FastCalc'; # module to do the low level math
- # default is FastCalc.pm
+my $CALC = 'Math::BigInt::Calc'; # module to do the low level math
+ # default is Calc.pm
my $IMPORT = 0; # was import() called yet?
# used to make require work
my %WARN; # warn only once for low-level libs
@@ -799,7 +799,7 @@ sub bone
}
##############################################################################
-# string conversation
+# string conversion
sub bsstr
{
@@ -931,7 +931,7 @@ sub round
# Round $self according to given parameters, or given second argument's
# parameters or global defaults
- # for speed reasons, _find_round_parameters is embeded here:
+ # for speed reasons, _find_round_parameters is embedded here:
my ($self,$a,$p,$r,@args) = @_;
# $a accuracy, if given by caller
@@ -989,7 +989,7 @@ sub round
{
$self->bfround(int($p),$r) if !defined $self->{_p} || $self->{_p} <= $p;
}
- # bround() or bfround() already callled bnorm() if nec.
+ # bround() or bfround() already called bnorm() if nec.
$self;
}
@@ -1260,7 +1260,7 @@ sub blog
# objectify is costly, so avoid it
if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
{
- ($self,$x,$base,@r) = objectify(1,ref($x),@_);
+ ($self,$x,$base,@r) = objectify(2,@_);
}
return $x if $x->modify('blog');
@@ -1320,18 +1320,17 @@ sub bnok
}
else
{
- # ( 7 ) 7! 7*6*5 * 4*3*2*1 7 * 6 * 5
- # ( - ) = --------- = --------------- = ---------
- # ( 3 ) 3! (7-3)! 3*2*1 * 4*3*2*1 3 * 2 * 1
+ # ( 7 ) 7! 1*2*3*4 * 5*6*7 5 * 6 * 7 6 7
+ # ( - ) = --------- = --------------- = --------- = 5 * - * -
+ # ( 3 ) (7-3)! 3! 1*2*3*4 * 1*2*3 1 * 2 * 3 2 3
- # compute n - k + 2 (so we start with 5 in the example above)
- my $z = $x - $y;
- if (!$z->is_one())
+ if (!$y->is_zero())
{
+ my $z = $x - $y;
$z->binc();
my $r = $z->copy(); $z->binc();
my $d = $self->new(2);
- while ($z->bacmp($x) <= 0) # f < x ?
+ while ($z->bacmp($x) <= 0) # f <= x ?
{
$r->bmul($z); $r->bdiv($d);
$z->binc(); $d->binc();
@@ -1375,11 +1374,11 @@ sub bexp
else { $x = $u; }
}
-sub blcm
- {
+sub blcm
+ {
# (BINT or num_str, BINT or num_str) return BINT
# does not modify arguments, but returns new object
- # Lowest Common Multiplicator
+ # Lowest Common Multiple
my $y = shift; my ($x);
if (ref($y))
@@ -1403,7 +1402,7 @@ sub bgcd
{
# (BINT or num_str, BINT or num_str) return BINT
# does not modify arguments, but returns new object
- # GCD -- Euclids algorithm, variant C (Knuth Vol 3, pg 341 ff)
+ # GCD -- Euclid's algorithm, variant C (Knuth Vol 3, pg 341 ff)
my $y = shift;
$y = $class->new($y) if !ref($y);
@@ -1498,13 +1497,13 @@ sub is_even
sub is_positive
{
- # return true when arg (BINT or num_str) is positive (>= 0)
+ # return true when arg (BINT or num_str) is positive (> 0)
my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
return 1 if $x->{sign} eq '+inf'; # +inf is positive
-
+
# 0+ is neither positive nor negative
- ($x->{sign} eq '+' && !$x->is_zero()) ? 1 : 0;
+ ($x->{sign} eq '+' && !$x->is_zero()) ? 1 : 0;
}
sub is_negative
@@ -1574,12 +1573,7 @@ sub bmuladd
# (BINT or num_str, BINT or num_str, BINT or num_str) return BINT
# set up parameters
- my ($self,$x,$y,$z,@r) = (ref($_[0]),@_);
- # objectify is costly, so avoid it
- if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
- {
- ($self,$x,$y,$z,@r) = objectify(3,@_);
- }
+ my ($self,$x,$y,$z,@r) = objectify(3,@_);
return $x if $x->modify('bmuladd');
@@ -1654,7 +1648,7 @@ sub _div_inf
if (($x->is_nan() || $y->is_nan()) ||
($x->is_zero() && $y->is_zero()));
- # +-inf / +-inf == NaN, reminder also NaN
+ # +-inf / +-inf == NaN, remainder also NaN
if (($x->{sign} =~ /^[+-]inf$/) && ($y->{sign} =~ /^[+-]inf$/))
{
return wantarray ? ($x->bnan(),$self->bnan()) : $x->bnan();
@@ -1786,10 +1780,12 @@ sub bmod
sub bmodinv
{
- # Modular inverse. given a number which is (hopefully) relatively
- # prime to the modulus, calculate its inverse using Euclid's
- # alogrithm. If the number is not relatively prime to the modulus
- # (i.e. their gcd is not one) then NaN is returned.
+ # Return modular multiplicative inverse: z is the modular inverse of x (mod
+ # y) if and only if x*z (mod y) = 1 (mod y). If the modulus y is larger than
+ # one, x and z are relative primes (i.e., their greatest common divisor is
+ # one).
+ #
+ # If no modular multiplicative inverse exists, NaN is returned.
# set up parameters
my ($self,$x,$y,@r) = (undef,@_);
@@ -1801,52 +1797,153 @@ sub bmodinv
return $x if $x->modify('bmodinv');
- return $x->bnan()
- if ($y->{sign} ne '+' # -, NaN, +inf, -inf
- || $x->is_zero() # or num == 0
- || $x->{sign} !~ /^[+-]$/ # or num NaN, inf, -inf
- );
-
- # put least residue into $x if $x was negative, and thus make it positive
- $x->bmod($y) if $x->{sign} eq '-';
-
- my $sign;
- ($x->{value},$sign) = $CALC->_modinv($x->{value},$y->{value});
- return $x->bnan() if !defined $x->{value}; # in case no GCD found
- return $x if !defined $sign; # already real result
- $x->{sign} = $sign; # flip/flop see below
- $x->bmod($y); # calc real result
- $x;
+ # Return NaN if one or both arguments is +inf, -inf, or nan.
+
+ return $x->bnan() if ($y->{sign} !~ /^[+-]$/ ||
+ $x->{sign} !~ /^[+-]$/);
+
+ # Return NaN if $y is zero; 1 % 0 makes no sense.
+
+ return $x->bnan() if $y->is_zero();
+
+ # Return 0 in the trivial case. $x % 1 or $x % -1 is zero for all finite
+ # integers $x.
+
+ return $x->bzero() if ($y->is_one() ||
+ $y->is_one('-'));
+
+ # Return NaN if $x = 0, or $x modulo $y is zero. The only valid case when
+ # $x = 0 is when $y = 1 or $y = -1, but that was covered above.
+ #
+ # Note that computing $x modulo $y here affects the value we'll feed to
+ # $CALC->_modinv() below when $x and $y have opposite signs. E.g., if $x =
+ # 5 and $y = 7, those two values are fed to _modinv(), but if $x = -5 and
+ # $y = 7, the values fed to _modinv() are $x = 2 (= -5 % 7) and $y = 7.
+ # The value if $x is affected only when $x and $y have opposite signs.
+
+ $x->bmod($y);
+ return $x->bnan() if $x->is_zero();
+
+ # Compute the modular multiplicative inverse of the absolute values. We'll
+ # correct for the signs of $x and $y later. Return NaN if no GCD is found.
+
+ ($x->{value}, $x->{sign}) = $CALC->_modinv($x->{value}, $y->{value});
+ return $x->bnan() if !defined $x->{value};
+
+ # Library inconsistency workaround: _modinv() in Math::BigInt::GMP versions
+ # <= 1.32 return undef rather than a "+" for the sign.
+
+ $x->{sign} = '+' unless defined $x->{sign};
+
+ # When one or both arguments are negative, we have the following
+ # relations. If x and y are positive:
+ #
+ # modinv(-x, -y) = -modinv(x, y)
+ # modinv(-x, y) = y - modinv(x, y) = -modinv(x, y) (mod y)
+ # modinv( x, -y) = modinv(x, y) - y = modinv(x, y) (mod -y)
+
+ # We must swap the sign of the result if the original $x is negative.
+ # However, we must compensate for ignoring the signs when computing the
+ # inverse modulo. The net effect is that we must swap the sign of the
+ # result if $y is negative.
+
+ $x -> bneg() if $y->{sign} eq '-';
+
+ # Compute $x modulo $y again after correcting the sign.
+
+ $x -> bmod($y) if $x->{sign} ne $y->{sign};
+
+ return $x;
}
sub bmodpow
{
- # takes a very large number to a very large exponent in a given very
- # large modulus, quickly, thanks to binary exponentation. Supports
- # negative exponents.
+ # Modular exponentiation. Raises a very large number to a very large exponent
+ # in a given very large modulus quickly, thanks to binary exponentiation.
+ # Supports negative exponents.
my ($self,$num,$exp,$mod,@r) = objectify(3,@_);
return $num if $num->modify('bmodpow');
- # check modulus for valid values
- return $num->bnan() if ($mod->{sign} ne '+' # NaN, - , -inf, +inf
- || $mod->is_zero());
+ # When the exponent 'e' is negative, use the following relation, which is
+ # based on finding the multiplicative inverse 'd' of 'b' modulo 'm':
+ #
+ # b^(-e) (mod m) = d^e (mod m) where b*d = 1 (mod m)
- # check exponent for valid values
- if ($exp->{sign} =~ /\w/)
- {
- # i.e., if it's NaN, +inf, or -inf...
- return $num->bnan();
- }
+ $num->bmodinv($mod) if ($exp->{sign} eq '-');
- $num->bmodinv ($mod) if ($exp->{sign} eq '-');
+ # Check for valid input. All operands must be finite, and the modulus must be
+ # non-zero.
- # check num for valid values (also NaN if there was no inverse but $exp < 0)
- return $num->bnan() if $num->{sign} !~ /^[+-]$/;
+ return $num->bnan() if ($num->{sign} =~ /NaN|inf/ || # NaN, -inf, +inf
+ $exp->{sign} =~ /NaN|inf/ || # NaN, -inf, +inf
+ $mod->{sign} =~ /NaN|inf/ || # NaN, -inf, +inf
+ $mod->is_zero());
+
+ # Compute 'a (mod m)', ignoring the signs on 'a' and 'm'. If the resulting
+ # value is zero, the output is also zero, regardless of the signs on 'a' and
+ # 'm'.
+
+ my $value = $CALC->_modpow($num->{value}, $exp->{value}, $mod->{value});
+ my $sign = '+';
+
+ # If the resulting value is non-zero, we have four special cases, depending
+ # on the signs on 'a' and 'm'.
+
+ unless ($CALC->_is_zero($value)) {
+
+ # There is a negative sign on 'a' (= $num**$exp) only if the number we
+ # are exponentiating ($num) is negative and the exponent ($exp) is odd.
+
+ if ($num->{sign} eq '-' && $exp->is_odd()) {
+
+ # When both the number 'a' and the modulus 'm' have a negative sign,
+ # use this relation:
+ #
+ # -a (mod -m) = -(a (mod m))
+
+ if ($mod->{sign} eq '-') {
+ $sign = '-';
+ }
+
+ # When only the number 'a' has a negative sign, use this relation:
+ #
+ # -a (mod m) = m - (a (mod m))
+
+ else {
+ # Use copy of $mod since _sub() modifies the first argument.
+ my $mod = $CALC->_copy($mod->{value});
+ $value = $CALC->_sub($mod, $value);
+ $sign = '+';
+ }
+
+ } else {
+
+ # When only the modulus 'm' has a negative sign, use this relation:
+ #
+ # a (mod -m) = (a (mod m)) - m
+ # = -(m - (a (mod m)))
+
+ if ($mod->{sign} eq '-') {
+ # Use copy of $mod since _sub() modifies the first argument.
+ my $mod = $CALC->_copy($mod->{value});
+ $value = $CALC->_sub($mod, $value);
+ $sign = '-';
+ }
+
+ # When neither the number 'a' nor the modulus 'm' have a negative
+ # sign, directly return the already computed value.
+ #
+ # (a (mod m))
+
+ }
- # $mod is positive, sign on $exp is ignored, result also positive
- $num->{value} = $CALC->_modpow($num->{value},$exp->{value},$mod->{value});
- $num;
+ }
+
+ $num->{value} = $value;
+ $num->{sign} = $sign;
+
+ return $num;
}
###############################################################################
@@ -2560,7 +2657,7 @@ sub objectify
{
$k = $a[0]->new($k);
}
- elsif (!defined $up && ref($k) ne $a[0])
+ elsif (ref($k) ne $a[0] and !defined $up || ref $k ne $up)
{
# foreign object, try to convert to integer
$k->can('as_number') ? $k = $k->as_number() : $k = $a[0]->new($k);
@@ -2640,7 +2737,7 @@ sub import
{
$_ =~ tr/a-zA-Z0-9://cd; # limit to sane characters
}
- push @c, \'FastCalc', \'Calc' # if all fail, try these
+ push @c, \'Calc' # if all fail, try these
if $warn_or_die < 2; # but not for "only"
$CALC = ''; # signal error
foreach my $l (@c)
@@ -2752,93 +2849,145 @@ sub import
# import done
}
-sub from_hex
- {
- # create a bigint from a hexadecimal string
- my ($self, $hs) = @_;
+sub from_hex {
+ # Create a bigint from a hexadecimal string.
+
+ my ($self, $str) = @_;
- my $rc = __from_hex($hs);
+ if ($str =~ s/
+ ^
+ ( [+-]? )
+ (0?x)?
+ (
+ [0-9a-fA-F]*
+ ( _ [0-9a-fA-F]+ )*
+ )
+ $
+ //x)
+ {
+ # Get a "clean" version of the string, i.e., non-emtpy and with no
+ # underscores or invalid characters.
- return $self->bnan() unless defined $rc;
+ my $sign = $1;
+ my $chrs = $3;
+ $chrs =~ tr/_//d;
+ $chrs = '0' unless CORE::length $chrs;
- $rc;
- }
+ # Initialize output.
-sub from_bin
- {
- # create a bigint from a hexadecimal string
- my ($self, $bs) = @_;
+ my $x = Math::BigInt->bzero();
- my $rc = __from_bin($bs);
+ # The library method requires a prefix.
- return $self->bnan() unless defined $rc;
+ $x->{value} = $CALC->_from_hex('0x' . $chrs);
- $rc;
- }
+ # Place the sign.
-sub from_oct
- {
- # create a bigint from a hexadecimal string
- my ($self, $os) = @_;
+ if ($sign eq '-' && ! $CALC->_is_zero($x->{value})) {
+ $x->{sign} = '-';
+ }
- my $x = $self->bzero();
-
- # strip underscores
- $os =~ s/([0-7])_([0-7])/$1$2/g;
- $os =~ s/([0-7])_([0-7])/$1$2/g;
-
- return $x->bnan() if $os !~ /^[\-\+]?0[0-7]+\z/;
+ return $x;
+ }
- my $sign = '+'; $sign = '-' if $os =~ /^-/;
+ # CORE::hex() parses as much as it can, and ignores any trailing garbage.
+ # For backwards compatibility, we return NaN.
- $os =~ s/^[+-]//; # strip sign
- $x->{value} = $CALC->_from_oct($os);
- $x->{sign} = $sign unless $CALC->_is_zero($x->{value}); # no '-0'
- $x;
- }
+ return $self->bnan();
+}
-sub __from_hex
- {
- # internal
- # convert a (ref to) big hex string to BigInt, return undef for error
- my $hs = shift;
+sub from_oct {
+ # Create a bigint from an octal string.
- my $x = Math::BigInt->bzero();
-
- # strip underscores
- $hs =~ s/([0-9a-fA-F])_([0-9a-fA-F])/$1$2/g;
- $hs =~ s/([0-9a-fA-F])_([0-9a-fA-F])/$1$2/g;
-
- return $x->bnan() if $hs !~ /^[\-\+]?0x[0-9A-Fa-f]+$/;
+ my ($self, $str) = @_;
- my $sign = '+'; $sign = '-' if $hs =~ /^-/;
+ if ($str =~ s/
+ ^
+ ( [+-]? )
+ (
+ [0-7]*
+ ( _ [0-7]+ )*
+ )
+ $
+ //x)
+ {
+ # Get a "clean" version of the string, i.e., non-emtpy and with no
+ # underscores or invalid characters.
- $hs =~ s/^[+-]//; # strip sign
- $x->{value} = $CALC->_from_hex($hs);
- $x->{sign} = $sign unless $CALC->_is_zero($x->{value}); # no '-0'
- $x;
- }
+ my $sign = $1;
+ my $chrs = $2;
+ $chrs =~ tr/_//d;
+ $chrs = '0' unless CORE::length $chrs;
-sub __from_bin
- {
- # internal
- # convert a (ref to) big binary string to BigInt, return undef for error
- my $bs = shift;
+ # Initialize output.
- my $x = Math::BigInt->bzero();
+ my $x = Math::BigInt->bzero();
- # strip underscores
- $bs =~ s/([01])_([01])/$1$2/g;
- $bs =~ s/([01])_([01])/$1$2/g;
- return $x->bnan() if $bs !~ /^[+-]?0b[01]+$/;
+ # The library method requires a prefix.
- my $sign = '+'; $sign = '-' if $bs =~ /^\-/;
- $bs =~ s/^[+-]//; # strip sign
+ $x->{value} = $CALC->_from_oct('0' . $chrs);
- $x->{value} = $CALC->_from_bin($bs);
- $x->{sign} = $sign unless $CALC->_is_zero($x->{value}); # no '-0'
- $x;
- }
+ # Place the sign.
+
+ if ($sign eq '-' && ! $CALC->_is_zero($x->{value})) {
+ $x->{sign} = '-';
+ }
+
+ return $x;
+ }
+
+ # CORE::oct() parses as much as it can, and ignores any trailing garbage.
+ # For backwards compatibility, we return NaN.
+
+ return $self->bnan();
+}
+
+sub from_bin {
+ # Create a bigint from a binary string.
+
+ my ($self, $str) = @_;
+
+ if ($str =~ s/
+ ^
+ ( [+-]? )
+ (0?b)?
+ (
+ [01]*
+ ( _ [01]+ )*
+ )
+ $
+ //x)
+ {
+ # Get a "clean" version of the string, i.e., non-emtpy and with no
+ # underscores or invalid characters.
+
+ my $sign = $1;
+ my $chrs = $3;
+ $chrs =~ tr/_//d;
+ $chrs = '0' unless CORE::length $chrs;
+
+ # Initialize output.
+
+ my $x = Math::BigInt->bzero();
+
+ # The library method requires a prefix.
+
+ $x->{value} = $CALC->_from_bin('0b' . $chrs);
+
+ # Place the sign.
+
+ if ($sign eq '-' && ! $CALC->_is_zero($x->{value})) {
+ $x->{sign} = '-';
+ }
+
+ return $x;
+ }
+
+ # For consistency with from_hex() and from_oct(), we return NaN when the
+ # input is invalid.
+
+ return $self->bnan();
+}
sub _split
{
@@ -2849,7 +2998,7 @@ sub _split
# invalid input.
my $x = shift;
- # strip white space at front, also extranous leading zeros
+ # strip white space at front, also extraneous leading zeros
$x =~ s/^\s*([-]?)0*([0-9])/$1$2/g; # will not strip ' .2'
$x =~ s/^\s+//; # but this will
$x =~ s/\s+$//g; # strip white space at end
@@ -2864,9 +3013,9 @@ sub _split
# invalid starting char?
return if $x !~ /^[+-]?(\.?[0-9]|0b[0-1]|0x[0-9a-fA-F])/;
- return __from_hex($x) if $x =~ /^[\-\+]?0x/; # hex string
- return __from_bin($x) if $x =~ /^[\-\+]?0b/; # binary string
-
+ return Math::BigInt->from_hex($x) if $x =~ /^[+-]?0x/; # hex string
+ return Math::BigInt->from_bin($x) if $x =~ /^[+-]?0b/; # binary string
+
# strip underscores between digits
$x =~ s/([0-9])_([0-9])/$1$2/g;
$x =~ s/([0-9])_([0-9])/$1$2/g; # do twice for 1_2_3
@@ -3100,7 +3249,7 @@ Math::BigInt - Arbitrary size integer/float math package
# will warn if Math::BigInt::GMP cannot be found
use Math::BigInt lib => 'GMP';
- # to supress the warning use this:
+ # to suppress the warning use this:
# use Math::BigInt try => 'GMP';
# dies if GMP cannot be loaded:
@@ -3136,8 +3285,8 @@ Math::BigInt - Arbitrary size integer/float math package
$x->is_one('-'); # if $x is -1
$x->is_odd(); # if $x is odd
$x->is_even(); # if $x is even
- $x->is_pos(); # if $x >= 0
- $x->is_neg(); # if $x < 0
+ $x->is_pos(); # if $x > 0
+ $x->is_neg(); # if $x < 0
$x->is_inf($sign); # if $x is +inf, or -inf (sign is default '+')
$x->is_int(); # if $x is an integer (not a float)
@@ -3165,7 +3314,7 @@ Math::BigInt - Arbitrary size integer/float math package
$x->bnot(); # two's complement (bit wise not)
$x->binc(); # increment $x by 1
$x->bdec(); # decrement $x by 1
-
+
$x->badd($y); # addition (add $y to $x)
$x->bsub($y); # subtraction (subtract $y from $x)
$x->bmul($y); # multiplication (multiply $x by $y)
@@ -3175,9 +3324,8 @@ Math::BigInt - Arbitrary size integer/float math package
$x->bmuladd($y,$z); # $x = $x * $y + $z
$x->bmod($y); # modulus (x % y)
- $x->bmodpow($exp,$mod); # modular exponentation (($num**$exp) % $mod))
- $x->bmodinv($mod); # the inverse of $x in the given modulus $mod
-
+ $x->bmodpow($y,$mod); # modular exponentiation (($x ** $y) % $mod)
+ $x->bmodinv($mod); # modular multiplicative inverse
$x->bpow($y); # power of arguments (x ** y)
$x->blsft($y); # left shift in base 2
$x->brsft($y); # right shift in base 2
@@ -3185,7 +3333,7 @@ Math::BigInt - Arbitrary size integer/float math package
$x->blsft($y,$n); # left shift by $y places in base $n
$x->brsft($y,$n); # right shift by $y places in base $n
# returns (quo,rem) or quo if in scalar context
-
+
$x->band($y); # bitwise and
$x->bior($y); # bitwise inclusive or
$x->bxor($y); # bitwise exclusive or
@@ -3200,7 +3348,7 @@ Math::BigInt - Arbitrary size integer/float math package
$x->blog(); # logarithm of $x to base e (Euler's number)
$x->blog($base); # logarithm of $x to base $base (f.i. 2)
$x->bexp(); # calculate e ** $x where e is Euler's number
-
+
$x->round($A,$P,$mode); # round to accuracy or precision using mode $mode
$x->bround($n); # accuracy: preserve $n digits
$x->bfround($n); # $n > 0: round $nth digits,
@@ -3212,14 +3360,14 @@ Math::BigInt - Arbitrary size integer/float math package
$x->bfloor(); # return integer less or equal than $x
$x->bceil(); # return integer greater or equal than $x
-
+
# The following do not modify their arguments:
# greatest common divisor (no OO style)
my $gcd = Math::BigInt::bgcd(@values);
- # lowest common multiplicator (no OO style)
- my $lcm = Math::BigInt::blcm(@values);
-
+ # lowest common multiple (no OO style)
+ my $lcm = Math::BigInt::blcm(@values);
+
$x->length(); # return number of digits in number
($xl,$f) = $x->length(); # length of number and length of fraction part,
# latter is always 0 digits long for BigInts
@@ -3230,8 +3378,8 @@ Math::BigInt - Arbitrary size integer/float math package
$x->copy(); # make a true copy of $x (unlike $y = $x;)
$x->as_int(); # return as BigInt (in BigInt: same as copy())
$x->numify(); # return as scalar (might overflow!)
-
- # conversation to string (do not modify their argument)
+
+ # conversion to string (do not modify their argument)
$x->bstr(); # normalized string (e.g. '3')
$x->bsstr(); # norm. string in scientific notation (e.g. '3E0')
$x->as_hex(); # as signed hexadecimal string with prefixed 0x
@@ -3270,7 +3418,7 @@ Input values to these routines may be any string, that looks like a number
and results in an integer, including hexadecimal and binary numbers.
Scalars holding numbers may also be passed, but note that non-integer numbers
-may already have lost precision due to the conversation to float. Quote
+may already have lost precision due to the conversion to float. Quote
your input if you want BigInt to see all the digits:
$x = Math::BigInt->new(12345678890123456789); # bad
@@ -3286,7 +3434,7 @@ are accepted, too. Please note that octal numbers are not recognized
by new(), so the following will print "123":
perl -MMath::BigInt -le 'print Math::BigInt->new("0123")'
-
+
To convert an octal number, use from_oct();
perl -MMath::BigInt -le 'print Math::BigInt->from_oct("0123")'
@@ -3295,8 +3443,8 @@ Currently, Math::BigInt::new() defaults to 0, while Math::BigInt::new('')
results in 'NaN'. This might change in the future, so use always the following
explicit forms to get a zero or NaN:
- $zero = Math::BigInt->bzero();
- $nan = Math::BigInt->bnan();
+ $zero = Math::BigInt->bzero();
+ $nan = Math::BigInt->bnan();
C<bnorm()> on a BigInt object is now effectively a no-op, since the numbers
are always stored in normalized form. If passed a string, creates a BigInt
@@ -3365,7 +3513,7 @@ The following values can be set by passing C<config()> a reference to a hash:
upgrade downgrade precision accuracy round_mode div_scale
Example:
-
+
$new_cfg = Math::BigInt->config( { trap_inf => 1, precision => 5 } );
=head2 accuracy()
@@ -3382,7 +3530,7 @@ results have. If you set a global accuracy, then this also applies to new()!
Warning! The accuracy I<sticks>, e.g. once you created a number under the
influence of C<< CLASS->accuracy($A) >>, all results from math operations with
-that number will also be rounded.
+that number will also be rounded.
In most cases, you should probably round the results explicitly using one of
L<round()>, L<bround()> or L<bfround()> or by passing the desired accuracy
@@ -3393,15 +3541,15 @@ to the math operation as additional parameter:
print scalar $x->copy()->bdiv($y, 2); # print 4300
print scalar $x->copy()->bdiv($y)->bround(2); # print 4300
-Please see the section about L<ACCURACY AND PRECISION> for further details.
+Please see the section about L<ACCURACY and PRECISION> for further details.
Value must be greater than zero. Pass an undef value to disable it:
$x->accuracy(undef);
Math::BigInt->accuracy(undef);
-Returns the current accuracy. For C<$x->accuracy()> it will return either the
-local accuracy, or if not defined, the global. This means the return value
+Returns the current accuracy. For C<< $x->accuracy() >> it will return either
+the local accuracy, or if not defined, the global. This means the return value
represents the accuracy that will be in effect for $x:
$y = Math::BigInt->new(1234567); # unrounded
@@ -3428,7 +3576,7 @@ Math::BigInt.
# This also applies to new()!
CLASS->precision(-5); # ditto
- $P = CLASS->precision(); # read out global precision
+ $P = CLASS->precision(); # read out global precision
$P = $x->precision(); # read out precision that affects $x
Note: You probably want to use L<accuracy()> instead. With L<accuracy> you
@@ -3443,15 +3591,15 @@ In Math::BigInt, passing a negative number precision has no effect since no
numbers have digits after the dot. In L<Math::BigFloat>, it will round all
results to P digits after the dot.
-Please see the section about L<ACCURACY AND PRECISION> for further details.
+Please see the section about L<ACCURACY and PRECISION> for further details.
Pass an undef value to disable it:
$x->precision(undef);
Math::BigInt->precision(undef);
-Returns the current precision. For C<$x->precision()> it will return either the
-local precision of $x, or if not defined, the global. This means the return
+Returns the current precision. For C<< $x->precision() >> it will return either
+the local precision of $x, or if not defined, the global. This means the return
value represents the prevision that will be in effect for $x:
$y = Math::BigInt->new(1234567); # unrounded
@@ -3466,7 +3614,7 @@ Math::BigInt.
=head2 brsft()
- $x->brsft($y,$n);
+ $x->brsft($y,$n);
Shifts $x right by $y in base $n. Default is base 2, used are usually 10 and
2, but others work, too.
@@ -3503,13 +3651,26 @@ See L<Input> for more info on accepted input formats.
$x = Math::BigInt->from_oct("0775"); # input is octal
+Interpret the input as an octal string and return the corresponding value. A
+"0" (zero) prefix is optional. A single underscore character may be placed
+right after the prefix, if present, or between any two digits. If the input is
+invalid, a NaN is returned.
+
=head2 from_hex()
$x = Math::BigInt->from_hex("0xcafe"); # input is hexadecimal
+Interpret input as a hexadecimal string. A "0x" or "x" prefix is optional. A
+single underscore character may be placed right after the prefix, if present,
+or between any two digits. If the input is invalid, a NaN is returned.
+
=head2 from_bin()
- $x = Math::BigInt->from_oct("0x10011"); # input is binary
+ $x = Math::BigInt->from_bin("0b10011"); # input is binary
+
+Interpret the input as a binary string. A "0b" or "b" prefix is optional. A
+single underscore character may be placed right after the prefix, if present,
+or between any two digits. If the input is invalid, a NaN is returned.
=head2 bnan()
@@ -3553,7 +3714,6 @@ If used on an object, it will set it to one:
=head2 is_one()/is_zero()/is_nan()/is_inf()
-
$x->is_zero(); # true if arg is +0
$x->is_nan(); # true if arg is NaN
$x->is_one(); # true if arg is +1
@@ -3568,7 +3728,7 @@ like:
if ($x == 0)
=head2 is_pos()/is_neg()/is_positive()/is_negative()
-
+
$x->is_pos(); # true if > 0
$x->is_neg(); # true if < 0
@@ -3605,7 +3765,7 @@ Returns -1, 0, 1 or undef.
$x->bacmp($y);
-Compares $x with $y while ignoring their. Returns -1, 0, 1 or undef.
+Compares $x with $y while ignoring their sign. Returns -1, 0, 1 or undef.
=head2 sign()
@@ -3648,7 +3808,7 @@ numbers.
=head2 bnot()
- $x->bnot();
+ $x->bnot();
Two's complement (bitwise not). This is equivalent to
@@ -3695,19 +3855,28 @@ This method was added in v1.87 of Math::BigInt (June 2007).
=head2 bmodinv()
- num->bmodinv($mod); # modular inverse
+ $x->bmodinv($mod); # modular multiplicative inverse
+
+Returns the multiplicative inverse of C<$x> modulo C<$mod>. If
+
+ $y = $x -> copy() -> bmodinv($mod)
+
+then C<$y> is the number closest to zero, and with the same sign as C<$mod>,
+satisfying
+
+ ($x * $y) % $mod = 1 % $mod
-Returns the inverse of C<$num> in the given modulus C<$mod>. 'C<NaN>' is
-returned unless C<$num> is relatively prime to C<$mod>, i.e. unless
-C<bgcd($num, $mod)==1>.
+If C<$x> and C<$y> are non-zero, they must be relative primes, i.e.,
+C<bgcd($y, $mod)==1>. 'C<NaN>' is returned when no modular multiplicative
+inverse exists.
=head2 bmodpow()
- $num->bmodpow($exp,$mod); # modular exponentation
+ $num->bmodpow($exp,$mod); # modular exponentiation
# ($num**$exp % $mod)
Returns the value of C<$num> taken to the power C<$exp> in the modulus
-C<$mod> using binary exponentation. C<bmodpow> is far superior to
+C<$mod> using binary exponentiation. C<bmodpow> is far superior to
writing
$num ** $exp % $mod
@@ -3867,7 +4036,7 @@ Calculates the N'th root of C<$x>.
=head2 round()
$x->round($A,$P,$round_mode);
-
+
Round $x to accuracy C<$A> or precision C<$P> using the round mode
C<$round_mode>.
@@ -3894,7 +4063,7 @@ Examples:
=head2 bfloor()
- $x->bfloor();
+ $x->bfloor();
Set $x to the integer less or equal than $x. This is a no-op in BigInt, but
does change $x in BigFloat.
@@ -3912,8 +4081,8 @@ does change $x in BigFloat.
=head2 blcm()
- blcm(@values); # lowest common multiplicator (no OO style)
-
+ blcm(@values); # lowest common multiple (no OO style)
+
head2 length()
$x->length();
@@ -3945,14 +4114,14 @@ Return the signed mantissa of $x as BigInt.
=head2 as_int()/as_number()
- $x->as_int();
+ $x->as_int();
Returns $x as a BigInt (truncated towards zero). In BigInt this is the same as
-C<copy()>.
+C<copy()>.
C<as_number()> is an alias to this method. C<as_number> was introduced in
v1.22, while C<as_int()> was only introduced in v1.68.
-
+
=head2 bstr()
$x->bstr();
@@ -3989,7 +4158,7 @@ This loses precision, to avoid this use L<as_int()> instead.
$x->modify('bpowd');
This method returns 0 if the object can be modified with the given
-peration, or 1 if not.
+operation, or 1 if not.
This is used for instance by L<Math::BigInt::Constant>.
@@ -4039,12 +4208,12 @@ the decimal point. For example, 123.45 has a precision of -2. 0 means an
integer like 123 (or 120). A precision of 2 means two digits to the left
of the decimal point are zero, so 123 with P = 1 becomes 120. Note that
numbers with zeros before the decimal point may have different precisions,
-because 1200 can have p = 0, 1 or 2 (depending on what the inital value
+because 1200 can have p = 0, 1 or 2 (depending on what the initial value
was). It could also have p < 0, when the digits after the decimal point
are zero.
The string output (of floating point numbers) will be padded with zeros:
-
+
Initial value P A Result String
------------------------------------------------------------
1234.01 -3 1000 1000
@@ -4161,7 +4330,7 @@ versions <= 5.7.2) is like this:
=item Accuracy (significant digits)
* fround($a) rounds to $a significant digits
- * only fdiv() and fsqrt() take A as (optional) paramater
+ * only fdiv() and fsqrt() take A as (optional) parameter
+ other operations simply create the same number (fneg etc), or more (fmul)
of digits
+ rounding/truncating is only done when explicitly calling one of fround
@@ -4186,7 +4355,7 @@ versions <= 5.7.2) is like this:
assumption that 124 has 3 significant digits, while 120/7 will get you
'17', not '17.1' since 120 is thought to have 2 significant digits.
The rounding after the division then uses the remainder and $y to determine
- wether it must round up or down.
+ whether it must round up or down.
? I have no idea which is the right way. That's why I used a slightly more
? simple scheme and tweaked the few failing testcases to match it.
@@ -4239,7 +4408,7 @@ This is how it works now:
Math::BigInt->accuracy(2);
Math::BigInt::SomeSubClass->accuracy(3);
- $x = Math::BigInt::SomeSubClass->new(1234);
+ $x = Math::BigInt::SomeSubClass->new(1234);
$x is now 1230, and not 1200. A subclass might choose to implement
this otherwise, e.g. falling back to the parent's A and P.
@@ -4301,7 +4470,7 @@ This is how it works now:
and P to -2, globally.
?Maybe an extra option that forbids local A & P settings would be in order,
- ?so that intermediate rounding does not 'poison' further math?
+ ?so that intermediate rounding does not 'poison' further math?
=item Overriding globals
@@ -4414,12 +4583,12 @@ have real numbers as results, the result is NaN.
=item exp(), cos(), sin(), atan2()
These all might have problems handling infinity right.
-
+
=back
=head1 INTERNALS
-The actual numbers are stored as unsigned big integers (with seperate sign).
+The actual numbers are stored as unsigned big integers (with separate sign).
You should neither care about nor depend on the internal representation; it
might change without notice. Use B<ONLY> method calls like C<< $x->sign(); >>
@@ -4466,7 +4635,7 @@ small numbers (less than about 20 digits) and when converting very large
numbers to decimal (for instance for printing, rounding, calculating their
length in decimal etc).
-So please select carefully what libary you want to use.
+So please select carefully what library you want to use.
Different low-level libraries use different formats to store the numbers.
However, you should B<NOT> depend on the number having a specific format
@@ -4506,7 +4675,7 @@ C<$e> and C<$m> will stay always the same, though their real values might
change.
=head1 EXAMPLES
-
+
use Math::BigInt;
sub bint { Math::BigInt->new(shift); }
@@ -4654,8 +4823,8 @@ directly.
=item *
-The private object hash keys like C<$x->{sign}> may not be changed, but
-additional keys can be added, like C<$x->{_custom}>.
+The private object hash keys like C<< $x->{sign} >> may not be changed, but
+additional keys can be added, like C<< $x->{_custom} >>.
=item *
@@ -4716,7 +4885,7 @@ As a shortcut, you can use the module C<bignum>:
use bignum;
-Also good for oneliners:
+Also good for one-liners:
perl -Mbignum -le 'print 2 ** 255'
@@ -4793,7 +4962,7 @@ So, the following examples will now work all as expected:
print "$x eq 9" if $x eq 3*3;
Additionally, the following still works:
-
+
print "$x == 9" if $x == $y;
print "$x == 9" if $x == 9;
print "$x == 9" if $x == 3*3;
@@ -4858,8 +5027,8 @@ The following will probably not do what you expect:
It prints both the number of digits in the number and in the fraction part
since print calls C<length()> in list context. Use something like:
-
- print scalar $c->length(),"\n"; # prints 3
+
+ print scalar $c->length(),"\n"; # prints 3
=item bdiv
@@ -4870,7 +5039,7 @@ The following will probably not do what you expect:
It prints both quotient and remainder since print calls C<bdiv()> in list
context. Also, C<bdiv()> will modify $c, so be careful. You probably want
to use
-
+
print $c / 10000,"\n";
print scalar $c->bdiv(10000),"\n"; # or if you want to modify $c
@@ -4878,7 +5047,7 @@ instead.
The quotient is always the greatest integer less than or equal to the
real-valued quotient of the two operands, and the remainder (when it is
-nonzero) always has the same sign as the second operand; so, for
+non-zero) always has the same sign as the second operand; so, for
example,
1 / 4 => ( 0, 1)
@@ -4934,8 +5103,8 @@ clearly the reasoning:
-inf/-inf = 1, 0 1 * -inf + 0 = -inf
inf/-inf = -1, 0 -1 * -inf + 0 = inf
-inf/ inf = -1, 0 1 * -inf + 0 = -inf
- 8/ 0 = inf, 8 inf * 0 + 8 = 8
- inf/ 0 = inf, inf inf * 0 + inf = inf
+ 8/ 0 = inf, 8 inf * 0 + 8 = 8
+ inf/ 0 = inf, inf inf * 0 + inf = inf
0/ 0 = NaN
These cases below violate the "remainder has the sign of the second of the two
@@ -4943,8 +5112,8 @@ arguments", since they wouldn't match up otherwise.
A / B = C, R so that C * B + R = A
========================================================
- -inf/ 0 = -inf, -inf -inf * 0 + inf = -inf
- -8/ 0 = -inf, -8 -inf * 0 + 8 = -8
+ -inf/ 0 = -inf, -inf -inf * 0 + inf = -inf
+ -8/ 0 = -inf, -8 -inf * 0 + 8 = -8
=item Modifying and =
@@ -4983,7 +5152,7 @@ modify $x, the last one won't:
print bpow($x,$i),"\n"; # modify $x
print $x->bpow($i),"\n"; # ditto
print $x **= $i,"\n"; # the same
- print $x ** $i,"\n"; # leave $x alone
+ print $x ** $i,"\n"; # leave $x alone
The form C<$x **= $y> is faster than C<$x = $x ** $y;>, though.
@@ -5033,7 +5202,7 @@ the result should be a Math::BigFloat or the second operant is one.
To get a Math::BigFloat you either need to call the operation manually,
make sure the operands are already of the proper type or casted to that type
via Math::BigFloat->new():
-
+
$float = Math::BigFloat->new($mbi2) / $mbi; # = 2.5
Beware of simple "casting" the entire expression, this would only convert
@@ -5050,7 +5219,7 @@ If in doubt, break the expression into simpler terms, or cast all operands
to the desired resulting type.
Scalar values are a bit different, since:
-
+
$float = 2 + $mbf;
$float = $mbf + 2;
diff --git a/Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm b/Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm
index 52e33d232ae..25f9a3b99d9 100644
--- a/Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm
+++ b/Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm
@@ -1,10 +1,10 @@
package Math::BigInt::Calc;
-use 5.006;
+use 5.006002;
use strict;
# use warnings; # dont use warnings for older Perls
-our $VERSION = '0.52';
+our $VERSION = '1.993';
# Package to store unsigned big integers in decimal and do math with them
@@ -60,7 +60,7 @@ sub _base_len
$BASE = int("1e".$BASE_LEN);
$MAX_VAL = $BASE-1;
return $BASE_LEN unless wantarray;
- return ($BASE_LEN, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN, $MAX_VAL, $BASE);
+ return ($BASE_LEN, $BASE, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN, $MAX_VAL,);
}
# find whether we can use mul or div in mul()/div()
@@ -95,7 +95,7 @@ sub _base_len
}
}
return $BASE_LEN unless wantarray;
- return ($BASE_LEN, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN, $MAX_VAL, $BASE);
+ return ($BASE_LEN, $BASE, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN, $MAX_VAL);
}
sub _new
@@ -189,7 +189,7 @@ BEGIN
$XOR_MASK = __PACKAGE__->_new( ( 2 ** $XOR_BITS ));
$OR_MASK = __PACKAGE__->_new( ( 2 ** $OR_BITS ));
- # We can compute the approximate lenght no faster than the real length:
+ # We can compute the approximate length no faster than the real length:
*_alen = \&_len;
}
@@ -272,17 +272,22 @@ sub _str
sub _num
{
- # Make a number (scalar int/float) from a BigInt object
- my $x = $_[1];
+ # Make a Perl scalar number (int/float) from a BigInt object.
+ my $x = $_[1];
- return 0+$x->[0] if scalar @$x == 1; # below $BASE
- my $fac = 1;
- my $num = 0;
- foreach (@$x)
- {
- $num += $fac*$_; $fac *= $BASE;
+ return 0 + $x->[0] if scalar @$x == 1; # below $BASE
+
+ # Start with the most significant element and work towards the least
+ # significant element. Avoid multiplying "inf" (which happens if the number
+ # overflows) with "0" (if there are zero elements in $x) since this gives
+ # "nan" which propagates to the output.
+
+ my $num = 0;
+ for (my $i = $#$x ; $i >= 0 ; --$i) {
+ $num *= $BASE;
+ $num += $x -> [$i];
}
- $num;
+ return $num;
}
##############################################################################
@@ -294,7 +299,7 @@ sub _add
# routine to add two base 1eX numbers
# stolen from Knuth Vol 2 Algorithm A pg 231
# there are separate routines to add and sub as per Knuth pg 233
- # This routine clobbers up array x, but not y.
+ # This routine modifies array x, but not y.
my ($c,$x,$y) = @_;
@@ -595,7 +600,7 @@ sub _div_use_mul
my ($c,$x,$yorg) = @_;
- # the general div algorithmn here is about O(N*N) and thus quite slow, so
+ # the general div algorithm here is about O(N*N) and thus quite slow, so
# we first check for some special cases and use shortcuts to handle them.
# This works, because we store the numbers in a chunked format where each
@@ -785,7 +790,7 @@ sub _div_use_div_64
my ($c,$x,$yorg) = @_;
use integer;
- # the general div algorithmn here is about O(N*N) and thus quite slow, so
+ # the general div algorithm here is about O(N*N) and thus quite slow, so
# we first check for some special cases and use shortcuts to handle them.
# This works, because we store the numbers in a chunked format where each
@@ -976,7 +981,7 @@ sub _div_use_div
# in list context
my ($c,$x,$yorg) = @_;
- # the general div algorithmn here is about O(N*N) and thus quite slow, so
+ # the general div algorithm here is about O(N*N) and thus quite slow, so
# we first check for some special cases and use shortcuts to handle them.
# This works, because we store the numbers in a chunked format where each
@@ -1206,20 +1211,18 @@ sub _len
sub _digit
{
- # return the nth digit, negative values count backward
- # zero is rightmost, so _digit(123,0) will give 3
+ # Return the nth digit. Zero is rightmost, so _digit(123,0) gives 3.
+ # Negative values count from the left, so _digit(123, -1) gives 1.
my ($c,$x,$n) = @_;
my $len = _len('',$x);
- $n = $len+$n if $n < 0; # -1 last, -2 second-to-last
- $n = abs($n); # if negative was too big
- $len--; $n = $len if $n > $len; # n to big?
-
- my $elem = int($n / $BASE_LEN); # which array element
- my $digit = $n % $BASE_LEN; # which digit in this element
- $elem = '0' x $BASE_LEN . @$x[$elem]; # get element padded with 0's
- substr($elem,-$digit-1,1);
+ $n += $len if $n < 0; # -1 last, -2 second-to-last
+ return "0" if $n < 0 || $n >= $len; # return 0 for digits out of range
+
+ my $elem = int($n / $BASE_LEN); # which array element
+ my $digit = $n % $BASE_LEN; # which digit in this element
+ substr("$x->[$elem]", -$digit-1, 1);
}
sub _zeros
@@ -1264,8 +1267,8 @@ sub _is_even
sub _is_odd
{
- # return true if arg is even
- (($_[1]->[0] & 1)) <=> 0;
+ # return true if arg is odd
+ (($_[1]->[0] & 1)) <=> 0;
}
sub _is_one
@@ -1352,22 +1355,24 @@ sub _mod
# if possible, use mod shortcut
my ($c,$x,$yo) = @_;
- # slow way since $y to big
+ # slow way since $y too big
if (scalar @$yo > 1)
{
my ($xo,$rem) = _div($c,$x,$yo);
- return $rem;
+ @$x = @$rem;
+ return $x;
}
my $y = $yo->[0];
- # both are single element arrays
+
+ # if both are single element arrays
if (scalar @$x == 1)
{
$x->[0] %= $y;
return $x;
}
- # @y is a single element, but @x has more than one element
+ # if @$x has more than one element, but @$y is a single element
my $b = $BASE % $y;
if ($b == 0)
{
@@ -1378,7 +1383,8 @@ sub _mod
}
elsif ($b == 1)
{
- # else need to go through all elements: O(N), but loop is a bit simplified
+ # else need to go through all elements in @$x: O(N), but loop is a bit
+ # simplified
my $r = 0;
foreach (@$x)
{
@@ -1390,8 +1396,9 @@ sub _mod
}
else
{
- # else need to go through all elements: O(N)
- my $r = 0; my $bm = 1;
+ # else need to go through all elements in @$x: O(N)
+ my $r = 0;
+ my $bm = 1;
foreach (@$x)
{
$r = ($_ * $bm + $r) % $y;
@@ -1405,8 +1412,8 @@ sub _mod
$r = 0 if $r == $y;
$x->[0] = $r;
}
- splice (@$x,1); # keep one element of $x
- $x;
+ @$x = $x->[0]; # keep one element of @$x
+ return $x;
}
##############################################################################
@@ -1489,7 +1496,7 @@ sub _lsft
}
# set lowest parts to 0
while ($dst >= 0) { $x->[$dst--] = 0; }
- # fix spurios last zero element
+ # fix spurious last zero element
splice @$x,-1 if $x->[-1] == 0;
$x;
}
@@ -1530,40 +1537,68 @@ sub _pow
$cx;
}
-sub _nok
- {
- # n over k
- # ref to array, return ref to array
- my ($c,$n,$k) = @_;
+sub _nok {
+ # Return binomial coefficient (n over k).
+ # Given refs to arrays, return ref to array.
+ # First input argument is modified.
- # ( 7 ) 7! 7*6*5 * 4*3*2*1 7 * 6 * 5
- # ( - ) = --------- = --------------- = ---------
- # ( 3 ) 3! (7-3)! 3*2*1 * 4*3*2*1 3 * 2 * 1
+ my ($c, $n, $k) = @_;
- # compute n - k + 2 (so we start with 5 in the example above)
- my $x = _copy($c,$n);
+ # If k > n/2, or, equivalently, 2*k > n, compute nok(n, k) as
+ # nok(n, n-k), to minimize the number if iterations in the loop.
- _sub($c,$n,$k);
- if (!_is_one($c,$n))
{
- _inc($c,$n);
- my $f = _copy($c,$n); _inc($c,$f); # n = 5, f = 6, d = 2
- my $d = _two($c);
- while (_acmp($c,$f,$x) <= 0) # f < n ?
- {
- # n = (n * f / d) == 5 * 6 / 2 => n == 3
- $n = _mul($c,$n,$f); $n = _div($c,$n,$d);
- # f = 7, d = 3
- _inc($c,$f); _inc($c,$d);
- }
+ my $twok = _mul($c, _two($c), _copy($c, $k)); # 2 * k
+ if (_acmp($c, $twok, $n) > 0) { # if 2*k > n
+ $k = _sub($c, _copy($c, $n), $k); # k = n - k
+ }
}
- else
- {
- # keep ref to $n and set it to 1
- splice (@$n,1); $n->[0] = 1;
+
+ # Example:
+ #
+ # / 7 \ 7! 1*2*3*4 * 5*6*7 5 * 6 * 7 6 7
+ # | | = --------- = --------------- = --------- = 5 * - * -
+ # \ 3 / (7-3)! 3! 1*2*3*4 * 1*2*3 1 * 2 * 3 2 3
+
+ if (_is_zero($c, $k)) {
+ @$n = 1;
}
- $n;
- }
+
+ else {
+
+ # Make a copy of the original n, since we'll be modifing n in-place.
+
+ my $n_orig = _copy($c, $n);
+
+ # n = 5, f = 6, d = 2 (cf. example above)
+
+ _sub($c, $n, $k);
+ _inc($c, $n);
+
+ my $f = _copy($c, $n);
+ _inc($c, $f);
+
+ my $d = _two($c);
+
+ # while f <= n (the original n, that is) ...
+
+ while (_acmp($c, $f, $n_orig) <= 0) {
+
+ # n = (n * f / d) == 5 * 6 / 2 (cf. example above)
+
+ _mul($c, $n, $f);
+ _div($c, $n, $d);
+
+ # f = 7, d = 3 (cf. example above)
+
+ _inc($c, $f);
+ _inc($c, $d);
+ }
+
+ }
+
+ return $n;
+}
my @factorials = (
1,
@@ -2030,7 +2065,7 @@ sub _root
# reset step to 2
$step = _two();
# add two, because $trial cannot be exactly the result (otherwise we would
- # alrady have found it)
+ # already have found it)
_add($c, $trial, $step);
# and now add more and more (2,4,6,8,10 etc)
@@ -2348,32 +2383,45 @@ sub _from_bin
sub _modinv
{
- # modular inverse
+ # modular multiplicative inverse
my ($c,$x,$y) = @_;
- my $u = _zero($c); my $u1 = _one($c);
- my $a = _copy($c,$y); my $b = _copy($c,$x);
+ # modulo zero
+ if (_is_zero($c, $y)) {
+ return (undef, undef);
+ }
+
+ # modulo one
+ if (_is_one($c, $y)) {
+ return (_zero($c), '+');
+ }
+
+ my $u = _zero($c);
+ my $v = _one($c);
+ my $a = _copy($c,$y);
+ my $b = _copy($c,$x);
- # Euclid's Algorithm for bgcd(), only that we calc bgcd() ($a) and the
- # result ($u) at the same time. See comments in BigInt for why this works.
+ # Euclid's Algorithm for bgcd(), only that we calc bgcd() ($a) and the result
+ # ($u) at the same time. See comments in BigInt for why this works.
my $q;
- ($a, $q, $b) = ($b, _div($c,$a,$b)); # step 1
my $sign = 1;
- while (!_is_zero($c,$b))
- {
- my $t = _add($c, # step 2:
- _mul($c,_copy($c,$u1), $q) , # t = u1 * q
- $u ); # + u
- $u = $u1; # u = u1, u1 = t
- $u1 = $t;
- $sign = -$sign;
- ($a, $q, $b) = ($b, _div($c,$a,$b)); # step 1
- }
+ {
+ ($a, $q, $b) = ($b, _div($c, $a, $b)); # step 1
+ last if _is_zero($c, $b);
+
+ my $t = _add($c, # step 2:
+ _mul($c, _copy($c, $v), $q) , # t = v * q
+ $u ); # + u
+ $u = $v; # u = v
+ $v = $t; # v = t
+ $sign = -$sign;
+ redo;
+ }
# if the gcd is not 1, then return NaN
- return (undef,undef) unless _is_one($c,$a);
-
- ($u1, $sign == 1 ? '+' : '-');
+ return (undef, undef) unless _is_one($c, $a);
+
+ ($v, $sign == 1 ? '+' : '-');
}
sub _modpow
@@ -2381,18 +2429,24 @@ sub _modpow
# modulus of power ($x ** $y) % $z
my ($c,$num,$exp,$mod) = @_;
- # in the trivial case,
+ # a^b (mod 1) = 0 for all a and b
if (_is_one($c,$mod))
{
- splice @$num,0,1; $num->[0] = 0;
- return $num;
- }
- if ((scalar @$num == 1) && (($num->[0] == 0) || ($num->[0] == 1)))
- {
- $num->[0] = 1;
- return $num;
+ @$num = 0;
+ return $num;
}
+ # 0^a (mod m) = 0 if m != 0, a != 0
+ # 0^0 (mod m) = 1 if m != 0
+ if (_is_zero($c, $num)) {
+ if (_is_zero($c, $exp)) {
+ @$num = 1;
+ } else {
+ @$num = 0;
+ }
+ return $num;
+ }
+
# $num = _mod($c,$num,$mod); # this does not make it faster
my $acc = _copy($c,$num); my $t = _one();
@@ -2413,19 +2467,40 @@ sub _modpow
$num;
}
-sub _gcd
- {
- # greatest common divisor
- my ($c,$x,$y) = @_;
+sub _gcd {
+ # Greatest common divisor.
- while ( (scalar @$y != 1) || ($y->[0] != 0) ) # while ($y != 0)
- {
- my $t = _copy($c,$y);
- $y = _mod($c, $x, $y);
- $x = $t;
+ my ($c, $x, $y) = @_;
+
+ # gcd(0,0) = 0
+ # gcd(0,a) = a, if a != 0
+
+ if (@$x == 1 && $x->[0] == 0) {
+ if (@$y == 1 && $y->[0] == 0) {
+ @$x = 0;
+ } else {
+ @$x = @$y;
+ }
+ return $x;
}
- $x;
- }
+
+ # Until $y is zero ...
+
+ until (@$y == 1 && $y->[0] == 0) {
+
+ # Compute remainder.
+
+ _mod($c, $x, $y);
+
+ # Swap $x and $y.
+
+ my $tmp = [ @$x ];
+ @$x = @$y;
+ $y = $tmp; # no deref here; that would modify input $y
+ }
+
+ return $x;
+}
##############################################################################
##############################################################################
@@ -2433,148 +2508,415 @@ sub _gcd
1;
__END__
+=pod
+
=head1 NAME
Math::BigInt::Calc - Pure Perl module to support Math::BigInt
=head1 SYNOPSIS
-Provides support for big integer calculations. Not intended to be used by other
-modules. Other modules which sport the same functions can also be used to support
-Math::BigInt, like Math::BigInt::GMP or Math::BigInt::Pari.
+This library provides support for big integer calculations. It is not
+intended to be used by other modules. Other modules which support the same
+API (see below) can also be used to support Math::BigInt, like
+Math::BigInt::GMP and Math::BigInt::Pari.
=head1 DESCRIPTION
+In this library, the numbers are represented in base B = 10**N, where N is
+the largest possible value that does not cause overflow in the intermediate
+computations. The base B elements are stored in an array, with the least
+significant element stored in array element zero. There are no leading zero
+elements, except a single zero element when the number is zero.
+
+For instance, if B = 10000, the number 1234567890 is represented internally
+as [3456, 7890, 12].
+
+=head1 THE Math::BigInt API
+
In order to allow for multiple big integer libraries, Math::BigInt was
-rewritten to use library modules for core math routines. Any module which
-follows the same API as this can be used instead by using the following:
+rewritten to use a plug-in library for core math routines. Any module which
+conforms to the API can be used by Math::BigInt by using this in your program:
use Math::BigInt lib => 'libname';
-'libname' is either the long name ('Math::BigInt::Pari'), or only the short
-version like 'Pari'.
-
-=head1 STORAGE
-
-=head1 METHODS
-
-The following functions MUST be defined in order to support the use by
-Math::BigInt v1.70 or later:
-
- api_version() return API version, 1 for v1.70, 2 for v1.83
- _new(string) return ref to new object from ref to decimal string
- _zero() return a new object with value 0
- _one() return a new object with value 1
- _two() return a new object with value 2
- _ten() return a new object with value 10
-
- _str(obj) return ref to a string representing the object
- _num(obj) returns a Perl integer/floating point number
- NOTE: because of Perl numeric notation defaults,
- the _num'ified obj may lose accuracy due to
- machine-dependent floating point size limitations
-
- _add(obj,obj) Simple addition of two objects
- _mul(obj,obj) Multiplication of two objects
- _div(obj,obj) Division of the 1st object by the 2nd
- In list context, returns (result,remainder).
- NOTE: this is integer math, so no
- fractional part will be returned.
- The second operand will be not be 0, so no need to
- check for that.
- _sub(obj,obj) Simple subtraction of 1 object from another
- a third, optional parameter indicates that the params
- are swapped. In this case, the first param needs to
- be preserved, while you can destroy the second.
- sub (x,y,1) => return x - y and keep x intact!
- _dec(obj) decrement object by one (input is guaranteed to be > 0)
- _inc(obj) increment object by one
-
-
- _acmp(obj,obj) <=> operator for objects (return -1, 0 or 1)
-
- _len(obj) returns count of the decimal digits of the object
- _digit(obj,n) returns the n'th decimal digit of object
-
- _is_one(obj) return true if argument is 1
- _is_two(obj) return true if argument is 2
- _is_ten(obj) return true if argument is 10
- _is_zero(obj) return true if argument is 0
- _is_even(obj) return true if argument is even (0,2,4,6..)
- _is_odd(obj) return true if argument is odd (1,3,5,7..)
-
- _copy return a ref to a true copy of the object
-
- _check(obj) check whether internal representation is still intact
- return 0 for ok, otherwise error message as string
-
- _from_hex(str) return new object from a hexadecimal string
- _from_bin(str) return new object from a binary string
- _from_oct(str) return new object from an octal string
-
- _as_hex(str) return string containing the value as
- unsigned hex string, with the '0x' prepended.
- Leading zeros must be stripped.
- _as_bin(str) Like as_hex, only as binary string containing only
- zeros and ones. Leading zeros must be stripped and a
- '0b' must be prepended.
-
- _rsft(obj,N,B) shift object in base B by N 'digits' right
- _lsft(obj,N,B) shift object in base B by N 'digits' left
-
- _xor(obj1,obj2) XOR (bit-wise) object 1 with object 2
- Note: XOR, AND and OR pad with zeros if size mismatches
- _and(obj1,obj2) AND (bit-wise) object 1 with object 2
- _or(obj1,obj2) OR (bit-wise) object 1 with object 2
-
- _mod(obj1,obj2) Return remainder of div of the 1st by the 2nd object
- _sqrt(obj) return the square root of object (truncated to int)
- _root(obj) return the n'th (n >= 3) root of obj (truncated to int)
- _fac(obj) return factorial of object 1 (1*2*3*4..)
- _pow(obj1,obj2) return object 1 to the power of object 2
- return undef for NaN
- _zeros(obj) return number of trailing decimal zeros
- _modinv return inverse modulus
- _modpow return modulus of power ($x ** $y) % $z
- _log_int(X,N) calculate integer log() of X in base N
- X >= 0, N >= 0 (return undef for NaN)
- returns (RESULT, EXACT) where EXACT is:
- 1 : result is exactly RESULT
- 0 : result was truncated to RESULT
- undef : unknown whether result is exactly RESULT
- _gcd(obj,obj) return Greatest Common Divisor of two objects
-
-The following functions are REQUIRED for an api_version of 2 or greater:
-
- _1ex($x) create the number 1Ex where x >= 0
- _alen(obj) returns approximate count of the decimal digits of the
- object. This estimate MUST always be greater or equal
- to what _len() returns.
- _nok(n,k) calculate n over k (binomial coefficient)
-
-The following functions are optional, and can be defined if the underlying lib
+'libname' is either the long name, like 'Math::BigInt::Pari', or only the short
+version, like 'Pari'.
+
+=head2 General Notes
+
+A library only needs to deal with unsigned big integers. Testing of input
+parameter validity is done by the caller, so there is no need to worry about
+underflow (e.g., in C<_sub()> and C<_dec()>) nor about division by zero (e.g.,
+in C<_div()>) or similar cases.
+
+For some methods, the first parameter can be modified. That includes the
+possibility that you return a reference to a completely different object
+instead. Although keeping the reference and just changing its contents is
+preferred over creating and returning a different reference.
+
+Return values are always objects, strings, Perl scalars, or true/false for
+comparison routines.
+
+=head2 API version 1
+
+The following methods must be defined in order to support the use by
+Math::BigInt v1.70 or later.
+
+=head3 API version
+
+=over 4
+
+=item I<api_version()>
+
+Return API version as a Perl scalar, 1 for Math::BigInt v1.70, 2 for
+Math::BigInt v1.83.
+
+=back
+
+=head3 Constructors
+
+=over 4
+
+=item I<_new(STR)>
+
+Convert a string representing an unsigned decimal number to an object
+representing the same number. The input is normalize, i.e., it matches
+C<^(0|[1-9]\d*)$>.
+
+=item I<_zero()>
+
+Return an object representing the number zero.
+
+=item I<_one()>
+
+Return an object representing the number one.
+
+=item I<_two()>
+
+Return an object representing the number two.
+
+=item I<_ten()>
+
+Return an object representing the number ten.
+
+=item I<_from_bin(STR)>
+
+Return an object given a string representing a binary number. The input has a
+'0b' prefix and matches the regular expression C<^0[bB](0|1[01]*)$>.
+
+=item I<_from_oct(STR)>
+
+Return an object given a string representing an octal number. The input has a
+'0' prefix and matches the regular expression C<^0[1-7]*$>.
+
+=item I<_from_hex(STR)>
+
+Return an object given a string representing a hexadecimal number. The input
+has a '0x' prefix and matches the regular expression
+C<^0x(0|[1-9a-fA-F][\da-fA-F]*)$>.
+
+=back
+
+=head3 Mathematical functions
+
+Each of these methods may modify the first input argument, except I<_bgcd()>,
+which shall not modify any input argument, and I<_sub()> which may modify the
+second input argument.
+
+=over 4
+
+=item I<_add(OBJ1, OBJ2)>
+
+Returns the result of adding OBJ2 to OBJ1.
+
+=item I<_mul(OBJ1, OBJ2)>
+
+Returns the result of multiplying OBJ2 and OBJ1.
+
+=item I<_div(OBJ1, OBJ2)>
+
+Returns the result of dividing OBJ1 by OBJ2 and truncating the result to an
+integer.
+
+=item I<_sub(OBJ1, OBJ2, FLAG)>
+
+=item I<_sub(OBJ1, OBJ2)>
+
+Returns the result of subtracting OBJ2 by OBJ1. If C<flag> is false or omitted,
+OBJ1 might be modified. If C<flag> is true, OBJ2 might be modified.
+
+=item I<_dec(OBJ)>
+
+Decrement OBJ by one.
+
+=item I<_inc(OBJ)>
+
+Increment OBJ by one.
+
+=item I<_mod(OBJ1, OBJ2)>
+
+Return OBJ1 modulo OBJ2, i.e., the remainder after dividing OBJ1 by OBJ2.
+
+=item I<_sqrt(OBJ)>
+
+Return the square root of the object, truncated to integer.
+
+=item I<_root(OBJ, N)>
+
+Return Nth root of the object, truncated to int. N is E<gt>= 3.
+
+=item I<_fac(OBJ)>
+
+Return factorial of object (1*2*3*4*...).
+
+=item I<_pow(OBJ1, OBJ2)>
+
+Return OBJ1 to the power of OBJ2. By convention, 0**0 = 1.
+
+=item I<_modinv(OBJ1, OBJ2)>
+
+Return modular multiplicative inverse, i.e., return OBJ3 so that
+
+ (OBJ3 * OBJ1) % OBJ2 = 1 % OBJ2
+
+The result is returned as two arguments. If the modular multiplicative
+inverse does not exist, both arguments are undefined. Otherwise, the
+arguments are a number (object) and its sign ("+" or "-").
+
+The output value, with its sign, must either be a positive value in the
+range 1,2,...,OBJ2-1 or the same value subtracted OBJ2. For instance, if the
+input arguments are objects representing the numbers 7 and 5, the method
+must either return an object representing the number 3 and a "+" sign, since
+(3*7) % 5 = 1 % 5, or an object representing the number 2 and "-" sign,
+since (-2*7) % 5 = 1 % 5.
+
+=item I<_modpow(OBJ1, OBJ2, OBJ3)>
+
+Return modular exponentiation, (OBJ1 ** OBJ2) % OBJ3.
+
+=item I<_rsft(OBJ, N, B)>
+
+Shift object N digits right in base B and return the resulting object. This is
+equivalent to performing integer division by B**N and discarding the remainder,
+except that it might be much faster, depending on how the number is represented
+internally.
+
+For instance, if the object $obj represents the hexadecimal number 0xabcde,
+then C<_rsft($obj, 2, 16)> returns an object representing the number 0xabc. The
+"remainer", 0xde, is discarded and not returned.
+
+=item I<_lsft(OBJ, N, B)>
+
+Shift the object N digits left in base B. This is equivalent to multiplying by
+B**N, except that it might be much faster, depending on how the number is
+represented internally.
+
+=item I<_log_int(OBJ, B)>
+
+Return integer log of OBJ to base BASE. This method has two output arguments,
+the OBJECT and a STATUS. The STATUS is Perl scalar; it is 1 if OBJ is the exact
+result, 0 if the result was truncted to give OBJ, and undef if it is unknown
+whether OBJ is the exact result.
+
+=item I<_gcd(OBJ1, OBJ2)>
+
+Return the greatest common divisor of OBJ1 and OBJ2.
+
+=back
+
+=head3 Bitwise operators
+
+Each of these methods may modify the first input argument.
+
+=over 4
+
+=item I<_and(OBJ1, OBJ2)>
+
+Return bitwise and. If necessary, the smallest number is padded with leading
+zeros.
+
+=item I<_or(OBJ1, OBJ2)>
+
+Return bitwise or. If necessary, the smallest number is padded with leading
+zeros.
+
+=item I<_xor(OBJ1, OBJ2)>
+
+Return bitwise exclusive or. If necessary, the smallest number is padded
+with leading zeros.
+
+=back
+
+=head3 Boolean operators
+
+=over 4
+
+=item I<_is_zero(OBJ)>
+
+Returns a true value if OBJ is zero, and false value otherwise.
+
+=item I<_is_one(OBJ)>
+
+Returns a true value if OBJ is one, and false value otherwise.
+
+=item I<_is_two(OBJ)>
+
+Returns a true value if OBJ is two, and false value otherwise.
+
+=item I<_is_ten(OBJ)>
+
+Returns a true value if OBJ is ten, and false value otherwise.
+
+=item I<_is_even(OBJ)>
+
+Return a true value if OBJ is an even integer, and a false value otherwise.
+
+=item I<_is_odd(OBJ)>
+
+Return a true value if OBJ is an even integer, and a false value otherwise.
+
+=item I<_acmp(OBJ1, OBJ2)>
+
+Compare OBJ1 and OBJ2 and return -1, 0, or 1, if OBJ1 is less than, equal
+to, or larger than OBJ2, respectively.
+
+=back
+
+=head3 String conversion
+
+=over 4
+
+=item I<_str(OBJ)>
+
+Return a string representing the object. The returned string should have no
+leading zeros, i.e., it should match C<^(0|[1-9]\d*)$>.
+
+=item I<_as_bin(OBJ)>
+
+Return the binary string representation of the number. The string must have a
+'0b' prefix.
+
+=item I<_as_oct(OBJ)>
+
+Return the octal string representation of the number. The string must have
+a '0x' prefix.
+
+Note: This method was required from Math::BigInt version 1.78, but the required
+API version number was not incremented, so there are older libraries that
+support API version 1, but do not support C<_as_oct()>.
+
+=item I<_as_hex(OBJ)>
+
+Return the hexadecimal string representation of the number. The string must
+have a '0x' prefix.
+
+=back
+
+=head3 Numeric conversion
+
+=over 4
+
+=item I<_num(OBJ)>
+
+Given an object, return a Perl scalar number (int/float) representing this
+number.
+
+=back
+
+=head3 Miscellaneous
+
+=over 4
+
+=item I<_copy(OBJ)>
+
+Return a true copy of the object.
+
+=item I<_len(OBJ)>
+
+Returns the number of the decimal digits in the number. The output is a
+Perl scalar.
+
+=item I<_zeros(OBJ)>
+
+Return the number of trailing decimal zeros. The output is a Perl scalar.
+
+=item I<_digit(OBJ, N)>
+
+Return the Nth digit as a Perl scalar. N is a Perl scalar, where zero refers to
+the rightmost (least significant) digit, and negative values count from the
+left (most significant digit). If $obj represents the number 123, then
+I<_digit($obj, 0)> is 3 and I<_digit(123, -1)> is 1.
+
+=item I<_check(OBJ)>
+
+Return a true value if the object is OK, and a false value otherwise. This is a
+check routine to test the internal state of the object for corruption.
+
+=back
+
+=head2 API version 2
+
+The following methods are required for an API version of 2 or greater.
+
+=head3 Constructors
+
+=over 4
+
+=item I<_1ex(N)>
+
+Return an object representing the number 10**N where N E<gt>= 0 is a Perl
+scalar.
+
+=back
+
+=head3 Mathematical functions
+
+=over 4
+
+=item I<_nok(OBJ1, OBJ2)>
+
+Return the binomial coefficient OBJ1 over OBJ1.
+
+=back
+
+=head3 Miscellaneous
+
+=over 4
+
+=item I<_alen(OBJ)>
+
+Return the approximate number of decimal digits of the object. The
+output is one Perl scalar. This estimate must be greater than or equal
+to what C<_len()> returns.
+
+=back
+
+=head2 API optional methods
+
+The following methods are optional, and can be defined if the underlying lib
has a fast way to do them. If undefined, Math::BigInt will use pure Perl (hence
slow) fallback routines to emulate these:
-
- _signed_or
- _signed_and
- _signed_xor
-Input strings come in as unsigned but with prefix (i.e. as '123', '0xabc'
-or '0b1101').
+=head3 Signed bitwise operators.
-So the library needs only to deal with unsigned big integers. Testing of input
-parameter validity is done by the caller, so you need not worry about
-underflow (f.i. in C<_sub()>, C<_dec()>) nor about division by zero or similar
-cases.
+Each of these methods may modify the first input argument.
-The first parameter can be modified, that includes the possibility that you
-return a reference to a completely different object instead. Although keeping
-the reference and just changing its contents is preferred over creating and
-returning a different reference.
+=over 4
-Return values are always references to objects, strings, or true/false for
-comparison routines.
+=item I<_signed_or(OBJ1, OBJ2, SIGN1, SIGN2)>
+
+Return the signed bitwise or.
+
+=item I<_signed_and(OBJ1, OBJ2, SIGN1, SIGN2)>
+
+Return the signed bitwise and.
+
+=item I<_signed_xor(OBJ1, OBJ2, SIGN1, SIGN2)>
+
+Return the signed bitwise exclusive or.
+
+=back
=head1 WRAP YOUR OWN
@@ -2592,18 +2934,34 @@ by this:
This way you ensure that your library really works 100% within Math::BigInt.
=head1 LICENSE
-
+
This program is free software; you may redistribute it and/or modify it under
the same terms as Perl itself.
=head1 AUTHORS
+=over 4
+
+=item *
+
Original math code by Mark Biggar, rewritten by Tels L<http://bloodgate.com/>
in late 2000.
-Seperated from BigInt and shaped API with the help of John Peacock.
+
+=item *
+
+Separated from BigInt and shaped API with the help of John Peacock.
+
+=item *
Fixed, speed-up, streamlined and enhanced by Tels 2001 - 2007.
+=item *
+
+API documentation corrected and extended by Peter John Acklam,
+E<lt>pjacklam@online.noE<gt>
+
+=back
+
=head1 SEE ALSO
L<Math::BigInt>, L<Math::BigFloat>,
diff --git a/Master/tlpkg/tlperl/lib/Math/BigInt/CalcEmu.pm b/Master/tlpkg/tlperl/lib/Math/BigInt/CalcEmu.pm
index 5810f5db9f7..ee0b677c53f 100644
--- a/Master/tlpkg/tlperl/lib/Math/BigInt/CalcEmu.pm
+++ b/Master/tlpkg/tlperl/lib/Math/BigInt/CalcEmu.pm
@@ -5,7 +5,7 @@ use strict;
# use warnings; # dont use warnings for older Perls
use vars qw/$VERSION/;
-$VERSION = '0.05';
+$VERSION = '1.993';
package Math::BigInt;
@@ -300,7 +300,7 @@ optional routines the low-level math package does not provide on its own.
Will be loaded on demand and called automatically by BigInt.
Stuff here is really low-priority to optimize, since it is far better to
-implement the operation in the low-level math libary directly, possible even
+implement the operation in the low-level math library directly, possible even
using a call to the native lib.
=head1 METHODS
@@ -312,7 +312,7 @@ using a call to the native lib.
=head2 __emu_bior
=head1 LICENSE
-
+
This program is free software; you may redistribute it and/or modify it under
the same terms as Perl itself.
diff --git a/Master/tlpkg/tlperl/lib/Math/BigInt/FastCalc.pm b/Master/tlpkg/tlperl/lib/Math/BigInt/FastCalc.pm
index 2b4aea58dc2..9abb12091f1 100644
--- a/Master/tlpkg/tlperl/lib/Math/BigInt/FastCalc.pm
+++ b/Master/tlpkg/tlperl/lib/Math/BigInt/FastCalc.pm
@@ -2,31 +2,24 @@ package Math::BigInt::FastCalc;
use 5.006;
use strict;
-# use warnings; # dont use warnings for older Perls
+use warnings;
-use DynaLoader;
-use Math::BigInt::Calc;
+use Math::BigInt::Calc 1.993;
-use vars qw/@ISA $VERSION $BASE $BASE_LEN/;
+use vars '$VERSION';
-@ISA = qw(DynaLoader);
-
-$VERSION = '0.19';
-
-bootstrap Math::BigInt::FastCalc $VERSION;
+$VERSION = '0.28';
##############################################################################
# global constants, flags and accessory
-# announce that we are compatible with MBI v1.70 and up
-sub api_version () { 1; }
-
-BEGIN
- {
- # use Calc to override the methods that we do not provide in XS
+# announce that we are compatible with MBI v1.83 and up
+sub api_version () { 2; }
- for my $method (qw/
- str
+# use Calc to override the methods that we do not provide in XS
+
+for my $method (qw/
+ str num
add sub mul div
rsft lsft
mod modpow modinv
@@ -42,18 +35,9 @@ BEGIN
no strict 'refs';
*{'Math::BigInt::FastCalc::_' . $method} = \&{'Math::BigInt::Calc::_' . $method};
}
- my ($AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN_SMALL, $MAX_VAL);
-
- # store BASE_LEN and BASE to later pass it to XS code
- ($BASE_LEN, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN_SMALL, $MAX_VAL, $BASE) =
- Math::BigInt::Calc::_base_len();
-
- }
-sub import
- {
- _set_XS_BASE($BASE, $BASE_LEN);
- }
+require XSLoader;
+XSLoader::load(__PACKAGE__, $VERSION, Math::BigInt::Calc::_base_len());
##############################################################################
##############################################################################
@@ -100,23 +84,26 @@ The following functions are now implemented in FastCalc.xs:
_is_odd _is_even _is_one _is_zero
_is_two _is_ten
_zero _one _two _ten
- _acmp _len _num
+ _acmp _len
_inc _dec
__strip_zeros _copy
=head1 LICENSE
-
+
This program is free software; you may redistribute it and/or modify it under
-the same terms as Perl itself.
+the same terms as Perl itself.
=head1 AUTHORS
Original math code by Mark Biggar, rewritten by Tels L<http://bloodgate.com/>
in late 2000.
-Seperated from BigInt and shaped API with the help of John Peacock.
+Separated from BigInt and shaped API with the help of John Peacock.
+
Fixed, sped-up and enhanced by Tels http://bloodgate.com 2001-2003.
Further streamlining (api_version 1 etc.) by Tels 2004-2007.
+Bug-fixing by Peter John Acklam E<lt>pjacklam@online.noE<gt> 2010-2011.
+
=head1 SEE ALSO
L<Math::BigInt>, L<Math::BigFloat>,
diff --git a/Master/tlpkg/tlperl/lib/Math/BigRat.pm b/Master/tlpkg/tlperl/lib/Math/BigRat.pm
index 2460d1c7d4e..135645fc43a 100644
--- a/Master/tlpkg/tlperl/lib/Math/BigRat.pm
+++ b/Master/tlpkg/tlperl/lib/Math/BigRat.pm
@@ -6,16 +6,17 @@
# The following hash values are used:
# sign : +,-,NaN,+inf,-inf
# _d : denominator
-# _n : numeraotr (value = _n/_d)
+# _n : numerator (value = _n/_d)
# _a : accuracy
# _p : precision
# You should not look at the innards of a BigRat - use the methods for this.
package Math::BigRat;
-# anythig older is untested, and unlikely to work
+# anything older is untested, and unlikely to work
use 5.006;
use strict;
+use Carp ();
use Math::BigFloat;
use vars qw($VERSION @ISA $upgrade $downgrade
@@ -23,13 +24,22 @@ use vars qw($VERSION @ISA $upgrade $downgrade
@ISA = qw(Math::BigFloat);
-$VERSION = '0.24';
+$VERSION = '0.26_02';
$VERSION = eval $VERSION;
-use overload; # inherit overload from Math::BigFloat
+# inherit overload from Math::BigFloat, but disable the bitwise ops that don't
+# make much sense for rationals unless they're truncated or something first
+
+use overload
+ map {
+ my $op = $_;
+ ($op => sub {
+ Carp::croak("bitwise operation $op not supported in Math::BigRat");
+ });
+ } qw(& | ^ ~ << >> &= |= ^= <<= >>=);
BEGIN
- {
+ {
*objectify = \&Math::BigInt::objectify; # inherit this from BigInt
*AUTOLOAD = \&Math::BigFloat::AUTOLOAD; # can't inherit AUTOLOAD
# we inherit these from BigFloat because currently it is not possible
@@ -86,14 +96,14 @@ sub _new_from_float
{
# something like Math::BigRat->new('0.1');
# 1 / 1 => 1/10
- $MBI->_lsft ( $self->{_d}, $f->{_e} ,10);
+ $MBI->_lsft ( $self->{_d}, $f->{_e} ,10);
}
else
{
# something like Math::BigRat->new('10');
# 1 / 1 => 10/1
- $MBI->_lsft ( $self->{_n}, $f->{_e} ,10) unless
- $MBI->_is_zero($f->{_e});
+ $MBI->_lsft ( $self->{_n}, $f->{_e} ,10) unless
+ $MBI->_is_zero($f->{_e});
}
$self;
}
@@ -106,7 +116,7 @@ sub new
my ($n,$d) = @_;
my $self = { }; bless $self,$class;
-
+
# input like (BigInt) or (BigFloat):
if ((!defined $d) && (ref $n) && (!$n->isa('Math::BigRat')))
{
@@ -197,7 +207,7 @@ sub new
local $Math::BigFloat::accuracy = undef;
local $Math::BigFloat::precision = undef;
- # one of them looks like a float
+ # one of them looks like a float
my $nf = Math::BigFloat->new($n,undef,undef);
$self->{sign} = '+';
return $self->bnan() if $nf->is_nan();
@@ -247,7 +257,7 @@ sub new
$n = Math::BigInt->new($n,undef,undef) unless ref $n;
if ($n->{sign} =~ /^[+-]$/ && $d->{sign} =~ /^[+-]$/)
- {
+ {
# both parts are ok as integers (wierd things like ' 1e0'
$self->{_n} = $MBI->_copy($n->{value});
$self->{_d} = $MBI->_copy($d->{value});
@@ -380,7 +390,7 @@ sub bsstr
my $s = $x->{sign}; $s =~ s/^\+//; # +inf => inf
return $s;
}
-
+
my $s = ''; $s = $x->{sign} if $x->{sign} ne '+'; # +3 vs 3
$s . $MBI->_str($x->{_n}) . '/' . $MBI->_str($x->{_d});
}
@@ -416,7 +426,7 @@ sub bnorm
# reduce other numbers
my $gcd = $MBI->_copy($x->{_n});
$gcd = $MBI->_gcd($gcd,$x->{_d});
-
+
if (!$MBI->_is_one($gcd))
{
$x->{_n} = $MBI->_div($x->{_n},$gcd);
@@ -521,14 +531,14 @@ sub badd
return $x->bnan() if ($x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/);
# 1 1 gcd(3,4) = 1 1*3 + 1*4 7
- # - + - = --------- = --
+ # - + - = --------- = --
# 4 3 4*3 12
# we do not compute the gcd() here, but simple do:
# 5 7 5*3 + 7*4 43
- # - + - = --------- = --
+ # - + - = --------- = --
# 4 3 4*3 12
-
+
# and bnorm() will then take care of the rest
# 5 * 3
@@ -563,7 +573,7 @@ sub bsub
$x->{sign} =~ tr/+-/-+/
unless $x->{sign} eq '+' && $MBI->_is_zero($x->{_n}); # not -0
$x->badd($y,@r); # does norm and round
- $x->{sign} =~ tr/+-/-+/
+ $x->{sign} =~ tr/+-/-+/
unless $x->{sign} eq '+' && $MBI->_is_zero($x->{_n}); # not -0
$x;
}
@@ -571,7 +581,7 @@ sub bsub
sub bmul
{
# multiply two rational numbers
-
+
# set up parameters
my ($self,$x,$y,@r) = (ref($_[0]),@_);
# objectify is costly, so avoid it
@@ -604,7 +614,7 @@ sub bmul
# 1 2 1 * 2 2 1
# - * - = ----- = - = -
# 4 3 4 * 3 12 6
-
+
$x->{_n} = $MBI->_mul( $x->{_n}, $y->{_n});
$x->{_d} = $MBI->_mul( $x->{_d}, $y->{_d});
@@ -640,11 +650,11 @@ sub bdiv
# 1 1 1 3
# - / - == - * -
# 4 3 4 1
-
+
$x->{_n} = $MBI->_mul( $x->{_n}, $y->{_d});
$x->{_d} = $MBI->_mul( $x->{_d}, $y->{_n});
- # compute new sign
+ # compute new sign
$x->{sign} = $x->{sign} eq $y->{sign} ? '+' : '-';
$x->bnorm()->round(@r);
@@ -674,14 +684,14 @@ sub bmod
my $u = bless { sign => '+' }, $self;
$u->{_n} = $MBI->_mul( $MBI->_copy($x->{_n}), $y->{_d} );
$u->{_d} = $MBI->_mul( $MBI->_copy($x->{_d}), $y->{_n} );
-
+
# compute floor(u)
if (! $MBI->_is_one($u->{_d}))
{
$u->{_n} = $MBI->_div($u->{_n},$u->{_d}); # 22/7 => 3/1 w/ truncate
# no need to set $u->{_d} to 1, since below we set it to $y->{_d} anyway
}
-
+
# now compute $y * $u
$u->{_d} = $MBI->_copy($y->{_d}); # 1 * $y->{_d}, see floor above
$u->{_n} = $MBI->_mul($u->{_n},$y->{_n});
@@ -728,7 +738,7 @@ sub binc
{
# increment value (add 1)
my ($self,$x,@r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
-
+
return $x if $x->{sign} !~ /^[+-]$/; # NaN, inf, -inf
if ($x->{sign} eq '-')
@@ -827,7 +837,7 @@ sub denominator
return Math::BigInt->new($x->{sign}) if $x->{sign} eq 'NaN';
# inf, -inf
return Math::BigInt->bone() if $x->{sign} !~ /^[+-]$/;
-
+
Math::BigInt->new($MBI->_str($x->{_d}));
}
@@ -961,7 +971,7 @@ sub bpow
if ($x->{sign} eq '-')
{
# - * - => +, - * - * - => -
- $x->{sign} = '+' if $MBI->_is_even($y->{_n});
+ $x->{sign} = '+' if $MBI->_is_even($y->{_n});
}
return $x->round(@r);
}
@@ -977,7 +987,7 @@ sub bpow
if ($x->{sign} eq '-')
{
# - * - => +, - * - * - => -
- $x->{sign} = '+' if $MBI->_is_even($y->{_n});
+ $x->{sign} = '+' if $MBI->_is_even($y->{_n});
}
return $x->round(@r);
}
@@ -1230,7 +1240,7 @@ sub bmodinv
}
# $x or $y are NaN or +-inf => NaN
- return $x->bnan()
+ return $x->bnan()
if $x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/;
if ($x->is_int() && $y->is_int())
@@ -1276,7 +1286,7 @@ sub bsqrt
$x->{_n} = $MBI->_copy( $x->{_n}->{_m} ); # 710/45.1 => 710/451
}
- # convert parts to $MBI again
+ # convert parts to $MBI again
$x->{_n} = $MBI->_lsft( $MBI->_copy( $x->{_n}->{_m} ), $x->{_n}->{_e}, 10)
if ref($x->{_n}) ne $MBI && ref($x->{_n}) ne 'ARRAY';
$x->{_d} = $MBI->_lsft( $MBI->_copy( $x->{_d}->{_m} ), $x->{_d}->{_e}, 10)
@@ -1288,7 +1298,7 @@ sub bsqrt
sub blsft
{
my ($self,$x,$y,$b,@r) = objectify(3,@_);
-
+
$b = 2 unless defined $b;
$b = $self->new($b) unless ref ($b);
$x->bmul( $b->copy()->bpow($y), @r);
@@ -1328,8 +1338,8 @@ sub bfround
sub bcmp
{
- # compare two signed numbers
-
+ # compare two signed numbers
+
# set up parameters
my ($self,$x,$y) = (ref($_[0]),@_);
# objectify is costly, so avoid it
@@ -1358,7 +1368,7 @@ sub bcmp
return 0 if $xz && $yz; # 0 <=> 0
return -1 if $xz && $y->{sign} eq '+'; # 0 <=> +y
return 1 if $yz && $x->{sign} eq '+'; # +x <=> 0
-
+
my $t = $MBI->_mul( $MBI->_copy($x->{_n}), $y->{_d});
my $u = $MBI->_mul( $MBI->_copy($y->{_n}), $x->{_d});
@@ -1370,7 +1380,7 @@ sub bcmp
sub bacmp
{
# compare two numbers (as unsigned)
-
+
# set up parameters
my ($self,$x,$y) = (ref($_[0]),@_);
# objectify is costly, so avoid it
@@ -1400,7 +1410,7 @@ sub numify
{
# convert 17/8 => float (aka 2.125)
my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
-
+
return $x->bstr() if $x->{sign} !~ /^[+-]$/; # inf, NaN, etc
# N/1 => N
@@ -1416,7 +1426,7 @@ sub as_number
# NaN, inf etc
return Math::BigInt->new($x->{sign}) if $x->{sign} !~ /^[+-]$/;
-
+
my $u = Math::BigInt->bzero();
$u->{sign} = $x->{sign};
$u->{value} = $MBI->_div( $MBI->_copy($x->{_n}), $x->{_d}); # 22/7 => 3
@@ -1434,7 +1444,7 @@ sub as_float
# NaN, inf etc
return Math::BigFloat->new($x->{sign}) if $x->{sign} !~ /^[+-]$/;
-
+
my $u = Math::BigFloat->bzero();
$u->{sign} = $x->{sign};
# n
@@ -1571,7 +1581,7 @@ sub import
# register us with MBI to get notified of future lib changes
Math::BigInt::_register_callback( $self, sub { $MBI = $_[0]; } );
-
+
# any non :constant stuff is handled by our parent, Exporter (loaded
# by Math::BigFloat, even if @_ is empty, to give it a chance
$self->SUPER::import(@a); # for subclasses
@@ -1593,7 +1603,7 @@ Math::BigRat - Arbitrary big rational numbers
my $x = Math::BigRat->new('3/7'); $x += '5/9';
print $x->bstr(),"\n";
- print $x ** 2,"\n";
+ print $x ** 2,"\n";
my $y = Math::BigRat->new('inf');
print "$y ", ($y->is_inf ? 'is' : 'is not') , " infinity\n";
@@ -1664,7 +1674,7 @@ Create a new Math::BigRat object. Input can come in various forms:
Returns a copy of the numerator (the part above the line) as signed BigInt.
=head2 denominator()
-
+
$d = $x->denominator();
Returns a copy of the denominator (the part under the line) as positive BigInt.
@@ -1717,21 +1727,21 @@ This method was added in v0.22 of Math::BigRat (April 2008).
$x = Math::BigRat->new('13');
print $x->as_hex(),"\n"; # '0xd'
-Returns the BigRat as hexadecimal string. Works only for integers.
+Returns the BigRat as hexadecimal string. Works only for integers.
=head2 as_bin()
$x = Math::BigRat->new('13');
print $x->as_bin(),"\n"; # '0x1101'
-Returns the BigRat as binary string. Works only for integers.
+Returns the BigRat as binary string. Works only for integers.
=head2 as_oct()
$x = Math::BigRat->new('13');
print $x->as_oct(),"\n"; # '015'
-Returns the BigRat as octal string. Works only for integers.
+Returns the BigRat as octal string. Works only for integers.
=head2 from_hex()/from_bin()/from_oct()
@@ -1746,7 +1756,7 @@ in string form.
$len = $x->length();
-Return the length of $x in digitis for integer values.
+Return the length of $x in digits for integer values.
=head2 digit()
@@ -1849,19 +1859,19 @@ Set $x to the next bigger integer value (e.g. truncate the number to integer
and then increment it by one).
=head2 bfloor()
-
+
$x->bfloor();
Truncate $x to an integer value.
=head2 bsqrt()
-
+
$x->bsqrt();
Calculate the square root of $x.
=head2 broot()
-
+
$x->broot($n);
Calculate the N'th root of $x.
@@ -1884,7 +1894,7 @@ Please see the documentation in L<Math::BigInt> for further details.
print $x->bstr(),"\n"; # prints 1/2
print $x->bsstr(),"\n"; # prints 1/2
-Return a string representating this object.
+Return a string representing this object.
=head2 bacmp()/bcmp()