Upgrade to Math::BigInt pre-rel 1.66 as of

http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2003-09/msg00242.html
(the tar.gz link doesn't have 'v1.66', it has '1.66')
so that the smoke builds can start chewing it.

p4raw-id: //depot/perl@21025

1 files changed, 98 insertions, 13 deletions

diff --git a/lib/Math/BigInt/Calc.pm b/lib/Math/BigInt/Calc.pm
index a3091c75c8..c09e07a628 100644
--- a/lib/Math/BigInt/Calc.pm
+++ b/lib/Math/BigInt/Calc.pm
@@ -8,7 +8,7 @@ require Exporter;
 use vars qw/@ISA $VERSION/;
 @ISA = qw(Exporter);
 
-$VERSION = '0.35';
+$VERSION = '0.36';
 
 # Package to store unsigned big integers in decimal and do math with them
 
@@ -513,8 +513,18 @@ sub _div_use_mul
   {
   # ref to array, ref to array, modify first array and return remainder if 
   # in list context
+
+  # see comments in _div_use_div() for more explanations
+
   my ($c,$x,$yorg) = @_;
+  
+  # the general div algorithmn 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
+  # element contains 5..7 digits (depending on system).
+
+  # if both numbers have only one element:
   if (@$x == 1 && @$yorg == 1)
     {
     # shortcut, $yorg and $x are two small numbers
@@ -530,6 +540,8 @@ sub _div_use_mul
       return $x; 
       }
     }
+
+  # if x has more than one, but y has only one element:
   if (@$yorg == 1)
     {
     my $rem;
@@ -549,6 +561,69 @@ sub _div_use_mul
     return $x;
     }
 
+  # now x and y have more than one element
+
+  # check whether y has more elements than x, if yet, the result will be 0
+  if (@$yorg > @$x)
+    {
+    my $rem;
+    $rem = [@$x] if wantarray;                  # make copy
+    splice (@$x,1);                             # keep ref to original array
+    $x->[0] = 0;                                # set to 0
+    return ($x,$rem) if wantarray;              # including remainder?
+    return $x;					# only x, which is [0] now
+    }
+  # check whether the numbers have the same number of elements, in that case
+  # the result will fit into one element and can be computed efficiently
+  if (@$yorg == @$x)
+    {
+    my $rem;
+    # if $yorg has more digits than $x (it's leading element is longer than
+    # the one from $x), the result will also be 0:
+    if (length(int($yorg->[-1])) > length(int($x->[-1])))
+      {
+      $rem = [@$x] if wantarray;		# make copy
+      splice (@$x,1);				# keep ref to org array
+      $x->[0] = 0;				# set to 0
+      return ($x,$rem) if wantarray;		# including remainder?
+      return $x;
+      }
+    # now calculate $x / $yorg
+    if (length(int($yorg->[-1])) == length(int($x->[-1])))
+      {
+      # same length, so make full compare, and if equal, return 1
+      # hm, same lengths, but same contents? So we need to check all parts:
+      my $a = 0; my $j = scalar @$x - 1;
+      # manual way (abort if unequal, good for early ne)
+      while ($j >= 0)
+        {
+        last if ($a = $x->[$j] - $yorg->[$j]); $j--;
+        }
+      # $a contains the result of the compare between X and Y
+      # a < 0: x < y, a == 0 => x == y, a > 0: x > y
+      if ($a <= 0)
+        {
+        if (wantarray)
+	  {
+          $rem = [ 0 ];			# a = 0 => x == y => rem 1
+          $rem = [@$x] if $a != 0;	# a < 0 => x < y => rem = x
+	  }
+        splice(@$x,1);			# keep single element
+        $x->[0] = 0;			# if $a < 0
+        if ($a == 0)
+          {
+          # $x == $y
+          $x->[0] = 1;
+          }
+        return ($x,$rem) if wantarray;
+        return $x;
+        }
+      # $x >= $y, proceed normally
+      }
+    }
+
+  # all other cases:
+
   my $y = [ @$yorg ];				# always make copy to preserve
 
   my ($car,$bar,$prd,$dd,$xi,$yi,@q,$v2,$v1,@d,$tmp,$q,$u2,$u1,$u0);
@@ -580,7 +655,7 @@ sub _div_use_mul
     $u2 = 0 unless $u2;
     #warn "oups v1 is 0, u0: $u0 $y->[-2] $y->[-1] l ",scalar @$y,"\n"
     # if $v1 == 0;
-     $q = (($u0 == $v1) ? $MAX_VAL : int(($u0*$MBASE+$u1)/$v1));
+    $q = (($u0 == $v1) ? $MAX_VAL : int(($u0*$MBASE+$u1)/$v1));
     --$q while ($v2*$q > ($u0*$MBASE+$u1-$q*$v1)*$MBASE+$u2);
     if ($q)
       {
@@ -597,11 +672,12 @@ sub _div_use_mul
 	for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi) 
           {
 	  $x->[$xi] -= $MBASE
-	   if ($car = (($x->[$xi] += $y->[$yi] + $car) > $MBASE));
+	   if ($car = (($x->[$xi] += $y->[$yi] + $car) >= $MBASE));
 	  }
 	}   
       }
-      pop(@$x); unshift(@q, $q);
+    pop(@$x);
+    unshift(@q, $q);
     }
   if (wantarray) 
     {
@@ -688,7 +764,7 @@ sub _div_use_div
     splice (@$x,1);				# keep ref to original array
     $x->[0] = 0;				# set to 0
     return ($x,$rem) if wantarray;		# including remainder?
-    return $x;
+    return $x;					# only x, which is [0] now
     }
   # check whether the numbers have the same number of elements, in that case
   # the result will fit into one element and can be computed efficiently
@@ -709,18 +785,23 @@ sub _div_use_div
     if (length(int($yorg->[-1])) == length(int($x->[-1])))
       {
       # same length, so make full compare, and if equal, return 1
-      # hm, same lengths,  but same contents? So we need to check all parts:
+      # hm, same lengths, but same contents? So we need to check all parts:
       my $a = 0; my $j = scalar @$x - 1;
       # manual way (abort if unequal, good for early ne)
       while ($j >= 0)
         {
         last if ($a = $x->[$j] - $yorg->[$j]); $j--;
         }
+      # $a contains the result of the compare between X and Y
       # a < 0: x < y, a == 0 => x == y, a > 0: x > y
       if ($a <= 0)
         {
-        $rem = [@$x] if wantarray;
-        splice(@$x,1);
+        if (wantarray)
+	  {
+          $rem = [ 0 ];			# a = 0 => x == y => rem 1
+          $rem = [@$x] if $a != 0;	# a < 0 => x < y => rem = x
+	  }
+        splice(@$x,1);			# keep single element
         $x->[0] = 0;			# if $a < 0
         if ($a == 0)
           {
@@ -730,9 +811,8 @@ sub _div_use_div
         return ($x,$rem) if wantarray;
         return $x;
         }
-      # $x >= $y, proceed normally
+      # $x >= $y, so proceed normally
       }
-
     }
 
   # all other cases:
@@ -760,6 +840,10 @@ sub _div_use_div
     {
     push(@$x, 0);
     }
+
+  # @q will accumulate the final result, $q contains the current computed
+  # part of the final result
+
   @q = (); ($v2,$v1) = @$y[-2,-1];
   $v2 = 0 unless $v2;
   while ($#$x > $#$y) 
@@ -768,7 +852,7 @@ sub _div_use_div
     $u2 = 0 unless $u2;
     #warn "oups v1 is 0, u0: $u0 $y->[-2] $y->[-1] l ",scalar @$y,"\n"
     # if $v1 == 0;
-     $q = (($u0 == $v1) ? $MAX_VAL : int(($u0*$MBASE+$u1)/$v1));
+    $q = (($u0 == $v1) ? $MAX_VAL : int(($u0*$MBASE+$u1)/$v1));
     --$q while ($v2*$q > ($u0*$MBASE+$u1-$q*$v1)*$MBASE+$u2);
     if ($q)
       {
@@ -785,7 +869,7 @@ sub _div_use_div
 	for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi) 
           {
 	  $x->[$xi] -= $MBASE
-	   if ($car = (($x->[$xi] += $y->[$yi] + $car) > $MBASE));
+	   if ($car = (($x->[$xi] += $y->[$yi] + $car) >= $MBASE));
 	  }
 	}   
       }
@@ -1013,6 +1097,7 @@ sub _mod
     my ($xo,$rem) = _div($c,$x,$yo);
     return $rem;
     }
+
   my $y = $yo->[0];
   # both are single element arrays
   if (scalar @$x == 1)
@@ -1021,7 +1106,7 @@ sub _mod
     return $x;
     }
 
-  # @y is single element, but @x has more than one
+  # @y is a single element, but @x has more than one element
   my $b = $BASE % $y;
   if ($b == 0)
     {