Upgrade to Math::BigRat 0.11

Subject: [PATCH] [ANNOUCNE] Math::BigRat 0.11
Message-Id: <200401071830.07445@bloodgate.com>

p4raw-id: //depot/perl@22110

4 files changed, 308 insertions, 62 deletions

diff --git a/lib/Math/BigRat.pm b/lib/Math/BigRat.pm
index 2b5796f18a..8a5feefdf7 100644
--- a/lib/Math/BigRat.pm
+++ b/lib/Math/BigRat.pm
@@ -10,13 +10,14 @@
 #   _a   : accuracy
 #   _p   : precision
 #   _f   : flags, used by MBR to flag parts of a rational as untouchable
+# You should not look at the innards of a BigRat - use the methods for this.
 
 package Math::BigRat;
 
 require 5.005_03;
 use strict;
 
-use Exporter;
+require Exporter;
 use Math::BigFloat;
 use vars qw($VERSION @ISA $PACKAGE @EXPORT_OK $upgrade $downgrade
             $accuracy $precision $round_mode $div_scale $_trap_nan $_trap_inf);
@@ -24,7 +25,7 @@ use vars qw($VERSION @ISA $PACKAGE @EXPORT_OK $upgrade $downgrade
 @ISA = qw(Exporter Math::BigFloat);
 @EXPORT_OK = qw();
 
-$VERSION = '0.10';
+$VERSION = '0.11';
 
 use overload;			# inherit from Math::BigFloat
 
@@ -56,7 +57,7 @@ sub isa
 
 sub _new_from_float
   {
-  # turn a single float input into a rational (like '0.1')
+  # turn a single float input into a rational number (like '0.1')
   my ($self,$f) = @_;
 
   return $self->bnan() if $f->is_nan();
@@ -95,7 +96,7 @@ sub new
     {
     if ($n->isa('Math::BigFloat'))
       {
-      return $self->_new_from_float($n)->bnorm();
+      $self->_new_from_float($n);
       }
     if ($n->isa('Math::BigInt'))
       {
@@ -103,7 +104,6 @@ sub new
       $self->{_n} = $n->copy();				# "mantissa" = $n
       $self->{_d} = $MBI->bone();
       $self->{sign} = $self->{_n}->{sign}; $self->{_n}->{sign} = '+';
-      return $self->bnorm();
       }
     if ($n->isa('Math::BigInt::Lite'))
       {
@@ -111,8 +111,8 @@ sub new
       $self->{sign} = '+'; $self->{sign} = '-' if $$n < 0;
       $self->{_n} = $MBI->new(abs($$n),undef,undef);	# "mantissa" = $n
       $self->{_d} = $MBI->bone();
-      return $self->bnorm();
       }
+    return $self->bnorm();
     }
   return $n->copy() if ref $n;
 
@@ -174,8 +174,13 @@ sub new
         # inf/inf => NaN
         return $self->bnan() if
 	  ($self->{_n}->is_inf() && $self->{_d}->is_inf());
-        # +-inf/123 => +-inf
-        return $self->binf($self->{sign}) if $self->{_n}->is_inf();
+        if ($self->{_n}->is_inf())
+	  {
+	  my $s = '+'; 		# '+inf/+123' or '-inf/-123'
+	  $s = '-' if substr($self->{_n}->{sign},0,1) ne $self->{_d}->{sign};
+	  # +-inf/123 => +-inf
+          return $self->binf($s);
+	  }
         # 123/inf => 0
         return $self->bzero();
         }
@@ -231,7 +236,7 @@ sub config
 
 sub bstr
   {
-  my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
+  my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
 
   if ($x->{sign} !~ /^[+-]$/)		# inf, NaN etc
     {
@@ -239,10 +244,10 @@ sub bstr
     return $s;
     }
 
-  my $s = ''; $s = $x->{sign} if $x->{sign} ne '+';	# +3 vs 3
+  my $s = ''; $s = $x->{sign} if $x->{sign} ne '+';	# '+3/2' => '3/2'
 
-  return $s.$x->{_n}->bstr() if $x->{_d}->is_one(); 
-  return $s.$x->{_n}->bstr() . '/' . $x->{_d}->bstr(); 
+  return $s . $x->{_n}->bstr() if $x->{_d}->is_one();
+  $s . $x->{_n}->bstr() . '/' . $x->{_d}->bstr();
   }
 
 sub bsstr
@@ -256,7 +261,7 @@ sub bsstr
     }
   
   my $s = ''; $s = $x->{sign} if $x->{sign} ne '+';	# +3 vs 3
-  return $s . $x->{_n}->bstr() . '/' . $x->{_d}->bstr(); 
+  $s . $x->{_n}->bstr() . '/' . $x->{_d}->bstr(); 
   }
 
 sub bnorm
@@ -279,8 +284,8 @@ sub bnorm
   $x->{_d}->{_f} = MB_NEVER_ROUND;
   $x->{_n}->{_f} = MB_NEVER_ROUND;
   # 'forget' that parts were rounded via MBI::bround() in MBF's bfround()
-  $x->{_d}->{_a} = undef; $x->{_n}->{_a} = undef;
-  $x->{_d}->{_p} = undef; $x->{_n}->{_p} = undef; 
+  delete $x->{_d}->{_a}; delete $x->{_n}->{_a};
+  delete $x->{_d}->{_p}; delete $x->{_n}->{_p}; 
 
   # no normalize for NaN, inf etc.
   return $x if $x->{sign} !~ /^[+-]$/;
@@ -365,7 +370,7 @@ sub _bzero
 
 sub badd
   {
-  # add two rationals
+  # add two rational numbers
 
   # set up parameters
   my ($self,$x,$y,@r) = (ref($_[0]),@_);
@@ -402,7 +407,7 @@ sub badd
 
   $x->{_d}->bmul($y->{_d});
 
-  # calculate new sign
+  # calculate sign of result and norm our _n part
   $x->{sign} = $x->{_n}->{sign}; $x->{_n}->{sign} = '+';
 
   $x->bnorm()->round(@r);
@@ -410,7 +415,7 @@ sub badd
 
 sub bsub
   {
-  # subtract two rationals
+  # subtract two rational numbers
 
   # set up parameters
   my ($self,$x,$y,@r) = (ref($_[0]),@_);
@@ -420,41 +425,18 @@ sub bsub
     ($self,$x,$y,@r) = objectify(2,@_);
     }
 
-  # TODO: $self instead or $class??
-  $x = $class->new($x) unless $x->isa($class);
-  $y = $class->new($y) unless $y->isa($class);
-
-  return $x->bnan() if ($x->{sign} eq 'NaN' || $y->{sign} eq 'NaN');
-  # TODO: inf handling
-
-  #  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     13
-  #  - - -  = --------- = - --
-  #  4   3       4*3        12
-
-  local $Math::BigInt::accuracy = undef;
-  local $Math::BigInt::precision = undef;
-
-  $x->{_n}->bmul($y->{_d}); $x->{_n}->{sign} = $x->{sign};
-  my $m = $y->{_n}->copy()->bmul($x->{_d});
-  $m->{sign} = $y->{sign};			# 2/1 - 2/1
-  $x->{_n}->bsub($m);
-
-  $x->{_d}->bmul($y->{_d});
-  
-  # calculate new sign
-  $x->{sign} = $x->{_n}->{sign}; $x->{_n}->{sign} = '+';
-
-  $x->bnorm()->round(@r);
+  # flip sign of $x, call badd(), then flip sign of result
+  $x->{sign} =~ tr/+-/-+/
+    unless $x->{sign} eq '+' && $x->{_n}->is_zero();	# not -0
+  $x->badd($y,@r);			# does norm and round
+  $x->{sign} =~ tr/+-/-+/ 
+    unless $x->{sign} eq '+' && $x->{_n}->is_zero();	# not -0
+  $x;
   }
 
 sub bmul
   {
-  # multiply two rationals
+  # multiply two rational numbers
   
   # set up parameters
   my ($self,$x,$y,@r) = (ref($_[0]),@_);
@@ -800,6 +782,7 @@ sub bfac
   {
   my ($self,$x,@r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
 
+  # if $x is an integer
   if (($x->{sign} eq '+') && ($x->{_d}->is_one()))
     {
     $x->{_n}->bfac();
@@ -890,7 +873,91 @@ sub bpow
 
 sub blog
   {
-  return Math::BigRat->bnan();
+  # set up parameters
+  my ($self,$x,$y,@r) = (ref($_[0]),@_);
+
+  # objectify is costly, so avoid it
+  if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
+    {
+    ($self,$x,$y,@r) = objectify(2,@_);
+    }
+
+  # $x <= 0 => NaN
+  return $x->bnan() if $x->is_zero() || $x->{sign} ne '+' || $y->{sign} ne '+';
+
+  if ($x->is_int() && $y->is_int())
+    {
+    return $self->new($x->as_number()->blog($y->as_number(),@r));
+    }
+
+  warn ("blog() not fully implemented");
+  $x->bnan();
+  }
+
+sub broot
+  {
+  # set up parameters
+  my ($self,$x,$y,@r) = (ref($_[0]),@_);
+  # objectify is costly, so avoid it
+  if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
+    {
+    ($self,$x,$y,@r) = objectify(2,@_);
+    }
+
+  if ($x->is_int() && $y->is_int())
+    {
+    return $self->new($x->as_number()->broot($y->as_number(),@r));
+    }
+ 
+  warn ("broot() not fully implemented"); 
+  $x->bnan();
+  }
+
+sub bmodpow
+  {
+  # set up parameters
+  my ($self,$x,$y,$m,@r) = (ref($_[0]),@_);
+  # objectify is costly, so avoid it
+  if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
+    {
+    ($self,$x,$y,$m,@r) = objectify(3,@_);
+    }
+
+  # $x or $y or $m are NaN or +-inf => NaN
+  return $x->bnan()
+   if $x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/ ||
+   $m->{sign} !~ /^[+-]$/;
+
+  if ($x->is_int() && $y->is_int() && $m->is_int())
+    {
+    return $self->new($x->as_number()->bmodpow($y->as_number(),$m,@r));
+    }
+
+  warn ("bmodpow() not fully implemented");
+  $x->bnan();
+  }
+
+sub bmodinv
+  {
+  # set up parameters
+  my ($self,$x,$y,@r) = (ref($_[0]),@_);
+  # objectify is costly, so avoid it
+  if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
+    {
+    ($self,$x,$y,@r) = objectify(2,@_);
+    }
+
+  # $x or $y are NaN or +-inf => NaN
+  return $x->bnan() 
+   if $x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/;
+
+  if ($x->is_int() && $y->is_int())
+    {
+    return $self->new($x->as_number()->bmodinv($y->as_number(),@r));
+    }
+
+  warn ("bmodinv() not fully implemented");
+  $x->bnan();
   }
 
 sub bsqrt
@@ -969,7 +1036,15 @@ sub bfround
 
 sub bcmp
   {
-  my ($self,$x,$y) = objectify(2,@_);
+  # compare two signed numbers 
+  
+  # set up parameters
+  my ($self,$x,$y) = (ref($_[0]),@_);
+  # objectify is costly, so avoid it
+  if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
+    {
+    ($self,$x,$y) = objectify(2,@_);
+    }
 
   if (($x->{sign} !~ /^[+-]$/) || ($y->{sign} !~ /^[+-]$/))
     {
@@ -999,14 +1074,23 @@ sub bcmp
 
 sub bacmp
   {
-  my ($self,$x,$y) = objectify(2,@_);
+  # compare two numbers (as unsigned)
+  
+  # set up parameters
+  my ($self,$x,$y) = (ref($_[0]),@_);
+  # objectify is costly, so avoid it
+  if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
+    {
+    ($self,$x,$y) = objectify(2,@_);
+    }
 
   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} =~ /^[+-]inf$/ && $y->{sign} =~ /^[+-]inf$/;
-    return +1;  # inf is always bigger
+    return 1 if $x->{sign} =~ /^[+-]inf$/ && $y->{sign} !~ /^[+-]inf$/;
+    return -1;
     }
 
   my $t = $x->{_n} * $y->{_d};
@@ -1132,21 +1216,26 @@ __END__
 
 =head1 NAME
 
-Math::BigRat - arbitrarily big rationals
+Math::BigRat - arbitrarily big rational numbers
 
 =head1 SYNOPSIS
 
 	use Math::BigRat;
 
-	$x = Math::BigRat->new('3/7'); $x += '5/9';
+	my $x = Math::BigRat->new('3/7'); $x += '5/9';
 
 	print $x->bstr(),"\n";
   	print $x ** 2,"\n";
 
+	my $y = Math::BigRat->new('inf');
+	print "$y ", ($y->is_inf ? 'is' : 'is not') , " infinity\n";
+
+	my $z = Math::BigRat->new(144); $z->bsqrt();
+
 =head1 DESCRIPTION
 
 Math::BigRat complements Math::BigInt and Math::BigFloat by providing support
-for arbitrarily big rationals.
+for arbitrarily big rational numbers.
 
 =head2 MATH LIBRARY
 
@@ -1191,6 +1280,7 @@ information.
 Create a new Math::BigRat object. Input can come in various forms:
 
 	$x = Math::BigRat->new(123);				# scalars
+	$x = Math::BigRat->new('inf');				# infinity
 	$x = Math::BigRat->new('123.3');			# float
 	$x = Math::BigRat->new('1/3');				# simple string
 	$x = Math::BigRat->new('1 / 3');			# spaced
@@ -1311,6 +1401,12 @@ and then increment it by one).
 
 Truncate $x to an integer value.
 
+=head2 bsqrt()
+	
+	$x->bsqrt();
+
+Calculate the square root of $x.
+
 =head2 config
 
         use Data::Dumper;
@@ -1368,6 +1464,8 @@ Some things are not yet implemented, or only implemented half-way:
 
 =item $x ** $y where $y is not an integer
 
+=item bmod(), blog(), bmodinv() and bmodpow() (partial)
+
 =back
 
 =head1 LICENSE
@@ -1388,6 +1486,6 @@ may contain more documentation and examples as well as testcases.
 
 =head1 AUTHORS
 
-(C) by Tels L<http://bloodgate.com/> 2001-2002. 
+(C) by Tels L<http://bloodgate.com/> 2001, 2002, 2003, 2004.
 
 =cut
diff --git a/lib/Math/BigRat/t/bigrat.t b/lib/Math/BigRat/t/bigrat.t
index ae385553f0..dd3927565a 100755
--- a/lib/Math/BigRat/t/bigrat.t
+++ b/lib/Math/BigRat/t/bigrat.t
@@ -8,7 +8,7 @@ BEGIN
   $| = 1;
   chdir 't' if -d 't';
   unshift @INC, '../lib'; # for running manually
-  plan tests => 164;
+  plan tests => 170;
   }
 
 # testing of Math::BigRat
@@ -237,6 +237,26 @@ $x = $cr->new('NaN'); ok ($x->numify(), 'NaN');
 $x = $cr->new('4/3'); ok ($x->numify(), 4/3);
 
 ##############################################################################
+# broot(), bmodpow() and bmodinv()
+
+$x = $cr->new(2) ** 32;
+$y = $cr->new(4);
+$z = $cr->new(3);
+
+ok ($x->copy()->broot($y), 2 ** 8);
+ok (ref($x->copy()->broot($y)), $cr);
+
+ok ($x->copy()->bmodpow($y,$z), 1);
+ok (ref($x->copy()->bmodpow($y,$z)), $cr);
+
+$x = $cr->new(8);
+$y = $cr->new(5033);
+$z = $cr->new(4404);
+
+ok ($x->copy()->bmodinv($y), $z);
+ok (ref($x->copy()->bmodinv($y)), $cr);
+
+##############################################################################
 # done
 
 1;
diff --git a/lib/Math/BigRat/t/bigratpm.inc b/lib/Math/BigRat/t/bigratpm.inc
index 4e63220ff7..1f4124fc84 100644
--- a/lib/Math/BigRat/t/bigratpm.inc
+++ b/lib/Math/BigRat/t/bigratpm.inc
@@ -82,9 +82,9 @@ while (<DATA>)
     else
       {
       $try .= "\$y = new $class \"$args[1]\";";
-      if ($f eq "fcmp") {
+      if ($f eq "bcmp") {
         $try .= '$x <=> $y;';
-      } elsif ($f eq "facmp") {
+      } elsif ($f eq "bacmp") {
         $try .= '$x->bacmp($y);';
       } elsif ($f eq "bpow") {
         $try .= '$x ** $y;';
@@ -106,7 +106,18 @@ while (<DATA>)
         $try .= '$x << $y;';
       } elsif ($f eq "bmod") {
         $try .= '$x % $y;';
-      } else { warn "Unknown op '$f'"; }
+      } elsif( $f eq "bmodinv") {
+       $try .= "\$x->bmodinv(\$y);";
+      } elsif( $f eq "blog") {
+       $try .= "\$x->blog(\$y);";
+      } else {
+        $try .= "\$z = $class->new(\"$args[2]\");";
+
+        # Functions with three arguments
+        if( $f eq "bmodpow") {
+          $try .= "\$x->bmodpow(\$y,\$z);";
+        } else { warn "Unknown op '$f'"; }
+      }
     }
     # print "# Trying: '$try'\n";
     $ans1 = eval $try;
@@ -171,11 +182,53 @@ sub ok_undef
   }
 
 __DATA__
+&bmodinv
+# format: number:modulus:result
+# bmodinv Data errors
+abc:abc:NaN
+abc:5:NaN
+5:abc:NaN
+# bmodinv Expected Results from normal use
+1:5:1
+3:5:2
+-2:5:2
+8:5033:4404
+1234567891:13:6
+-1234567891:13:7
+324958749843759385732954874325984357439658735983745:2348249874968739:1741662881064902
+## bmodinv Error cases / useless use of function
+3:-5:NaN
+inf:5:NaN
+5:inf:NaN
+-inf:5:NaN
+5:-inf:NaN
 &as_number
 144/7:20
 NaN:NaN
 +inf:inf
 -inf:-inf
+&bmodpow
+# format: number:exponent:modulus:result
+# bmodpow Data errors
+abc:abc:abc:NaN
+5:abc:abc:NaN
+abc:5:abc:NaN
+abc:abc:5:NaN
+5:5:abc:NaN
+5:abc:5:NaN
+abc:5:5:NaN
+# bmodpow Expected results
+0:0:2:1
+1:0:2:1
+0:0:1:0
+8:7:5032:3840
+8:-1:5033:4404
+98436739867439843769485798542749827593285729587325:43698764986460981048259837659386739857456983759328457:6943857329857295827698367:3104744730915914415259518
+# bmodpow Error cases
+8:8:-5:NaN
+8:-1:16:NaN
+inf:5:13:NaN
+5:inf:13:NaN
 &bmod
 NaN:1:NaN
 1:NaN:NaN
@@ -209,6 +262,16 @@ NaN:NaN
 &flog
 NaN:NaN
 0:NaN
+-2:NaN
+&blog
+NaN:NaN:NaN
+0:NaN:NaN
+NaN:0:NaN
+NaN:1:NaN
+1:NaN:NaN
+0:2:NaN
+0:-2:NaN
+3:-2:NaN
 &finf
 1:+:inf
 2:-:-inf
@@ -251,6 +314,13 @@ abcfsstr:NaN
 bnormNaN:NaN
 +inf:inf
 -inf:-inf
+inf/inf:NaN
+5/inf:0
+5/-inf:0
+inf/5:inf
+-inf/5:-inf
+inf/-5:-inf
+-inf/-5:inf
 123:123
 -123.4567:-1234567/10000
 # invalid inputs
@@ -429,6 +499,8 @@ baddNaN:+inf:NaN
 7/27:3/54:11/54
 -2/3:+2/3:-4/3
 -2/3:-2/3:0
+0:-123:123
+0:123:-123
 &bmul
 abc:abc:NaN
 abc:+0:NaN
@@ -657,6 +729,8 @@ NaNzero:0
 1:0
 0/3:1
 1/3:0
+-0/3:1
+5/inf:1
 &is_one
 NaNone:0
 +inf:0
@@ -669,6 +743,7 @@ NaNone:0
 1/3:0
 100/100:1
 0.1/0.1:1
+5/inf:0
 &ffloor
 0:0
 abc:NaN
@@ -721,6 +796,59 @@ NaN:NaN
 # bpow test for overload of **
 2:2:4
 3:3:27
+&bacmp
++0:-0:0
++0:+1:-1
+-1:+1:0
++1:-1:0
+-1:+2:-1
++2:-1:1
+-123456789:+987654321:-1
++123456789:-987654321:-1
++987654321:+123456789:1
+-987654321:+123456789:1
+-123:+4567889:-1
+# NaNs
+acmpNaN:123:
+123:acmpNaN:
+acmpNaN:acmpNaN:
+# infinity
++inf:+inf:0
+-inf:-inf:0
++inf:-inf:0
+-inf:+inf:0
++inf:123:1
+-inf:123:1
++inf:-123:1
+-inf:-123:1
++inf:1/23:1
+-inf:1/23:1
++inf:-1/23:1
+-inf:-1/23:1
++inf:12/3:1
+-inf:12/3:1
++inf:-12/3:1
+-inf:-12/3:1
+123:inf:-1
+-123:inf:-1
+123:-inf:-1
+-123:-inf:-1
+1/23:inf:-1
+-1/23:inf:-1
+1/23:-inf:-1
+-1/23:-inf:-1
+12/3:inf:-1
+-12/3:inf:-1
+12/3:-inf:-1
+-12/3:-inf:-1
+# return undef
++inf:NaN:
+NaN:inf:
+-inf:NaN:
+NaN:-inf:
+1/3:2/3:-1
+2/3:1/3:1
+2/3:2/3:0
 &fpow
 2/1:3/1:8
 3/1:3/1:27
diff --git a/lib/Math/BigRat/t/bigratpm.t b/lib/Math/BigRat/t/bigratpm.t
index 79943326e7..df23539df3 100755
--- a/lib/Math/BigRat/t/bigratpm.t
+++ b/lib/Math/BigRat/t/bigratpm.t
@@ -26,7 +26,7 @@ BEGIN
     }
   print "# INC = @INC\n";
 
-  plan tests => 534;
+  plan tests => 636;
   }
 
 use Math::BigRat;