X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?a=blobdiff_plain;f=lib%2FMath%2FBigInt.pm;h=839b746c24f440dc024aadf355a452daf51500f5;hb=b82d478d407f1381d69179104035c975c1d1402e;hp=b61b8845693432fda0779b8c26795af8b8d5b316;hpb=8dcee03ef4ed12141a63dec75da7d736915e7be4;p=p5sagit%2Fp5-mst-13.2.git

diff --git a/lib/Math/BigInt.pm b/lib/Math/BigInt.pm
index b61b884..839b746 100644
--- a/lib/Math/BigInt.pm
+++ b/lib/Math/BigInt.pm
@@ -1,13 +1,12 @@
 package Math::BigInt;
+$VERSION='0.01';
 
 use overload
 '+'	=>	sub {new Math::BigInt &badd},
 '-'	=>	sub {new Math::BigInt
 		       $_[2]? bsub($_[1],${$_[0]}) : bsub(${$_[0]},$_[1])},
-'<=>'	=>	sub {new Math::BigInt
-		       $_[2]? bcmp($_[1],${$_[0]}) : bcmp(${$_[0]},$_[1])},
-'cmp'	=>	sub {new Math::BigInt
-		       $_[2]? ($_[1] cmp ${$_[0]}) : (${$_[0]} cmp $_[1])},
+'<=>'	=>	sub {$_[2]? bcmp($_[1],${$_[0]}) : bcmp(${$_[0]},$_[1])},
+'cmp'	=>	sub {$_[2]? ($_[1] cmp ${$_[0]}) : (${$_[0]} cmp $_[1])},
 '*'	=>	sub {new Math::BigInt &bmul},
 '/'	=>	sub {new Math::BigInt 
 		       $_[2]? scalar bdiv($_[1],${$_[0]}) :
@@ -18,6 +17,15 @@ use overload
 		       $_[2]? bpow($_[1],${$_[0]}) : bpow(${$_[0]},$_[1])},
 'neg'	=>	sub {new Math::BigInt &bneg},
 'abs'	=>	sub {new Math::BigInt &babs},
+'<<'	=>	sub {new Math::BigInt
+		       $_[2]? blsft($_[1],${$_[0]}) : blsft(${$_[0]},$_[1])},
+'>>'	=>	sub {new Math::BigInt
+		       $_[2]? brsft($_[1],${$_[0]}) : brsft(${$_[0]},$_[1])},
+'&'	=>	sub {new Math::BigInt &band},
+'|'	=>	sub {new Math::BigInt &bior},
+'^'	=>	sub {new Math::BigInt &bxor},
+'~'	=>	sub {new Math::BigInt &bnot},
+'int'	=>	sub { shift },
 
 qw(
 ""	stringify
@@ -45,6 +53,11 @@ sub import {
 
 $zero = 0;
 
+# overcome a floating point problem on certain osnames (posix-bc, os390)
+BEGIN {
+    my $x = 100000.0;
+    my $use_mult = int($x*1e-5)*1e5 == $x ? 1 : 0;
+}
 
 # normalize string form of number.   Strip leading zeros.  Strip any
 #   white space and add a sign, if missing.
@@ -221,8 +234,14 @@ sub mul { #(*int_num_array, *int_num_array) return int_num_array
       ($car, $cty) = (0, $[);
       for $y (@y) {
 	$prod = $x * $y + ($prod[$cty] || 0) + $car;
+        if ($use_mult) {
 	$prod[$cty++] =
 	  $prod - ($car = int($prod * 1e-5)) * 1e5;
+        }
+        else {
+	$prod[$cty++] =
+	  $prod - ($car = int($prod / 1e5)) * 1e5;
+        }
       }
       $prod[$cty] += $car if $car;
       $x = shift @prod;
@@ -247,27 +266,44 @@ sub bdiv { #(dividend: num_str, divisor: num_str) return num_str
     if (($dd = int(1e5/($y[$#y]+1))) != 1) {
 	for $x (@x) {
 	    $x = $x * $dd + $car;
+            if ($use_mult) {
 	    $x -= ($car = int($x * 1e-5)) * 1e5;
+            }
+            else {
+	    $x -= ($car = int($x / 1e5)) * 1e5;
+            }
 	}
 	push(@x, $car); $car = 0;
 	for $y (@y) {
 	    $y = $y * $dd + $car;
+            if ($use_mult) {
 	    $y -= ($car = int($y * 1e-5)) * 1e5;
+            }
+            else {
+	    $y -= ($car = int($y / 1e5)) * 1e5;
+            }
 	}
     }
     else {
 	push(@x, 0);
     }
-    @q = (); ($v2,$v1) = ($y[-2] || 0, $y[-1]);
+    @q = (); ($v2,$v1) = @y[-2,-1];
+    $v2 = 0 unless $v2;
     while ($#x > $#y) {
-	($u2,$u1,$u0) = ($x[-3] || 0, $x[-2] || 0, $x[-1]);
+	($u2,$u1,$u0) = @x[-3..-1];
+	$u2 = 0 unless $u2;
 	$q = (($u0 == $v1) ? 99999 : int(($u0*1e5+$u1)/$v1));
 	--$q while ($v2*$q > ($u0*1e5+$u1-$q*$v1)*1e5+$u2);
 	if ($q) {
 	    ($car, $bar) = (0,0);
 	    for ($y = $[, $x = $#x-$#y+$[-1; $y <= $#y; ++$y,++$x) {
 		$prd = $q * $y[$y] + $car;
+                if ($use_mult) {
 		$prd -= ($car = int($prd * 1e-5)) * 1e5;
+                }
+                else {
+		$prd -= ($car = int($prd / 1e5)) * 1e5;
+                }
 		$x[$x] += 1e5 if ($bar = (($x[$x] -= $prd + $bar) < 0));
 	    }
 	    if ($x[$#x] < $car + $bar) {
@@ -328,6 +364,69 @@ sub bpow { #(num_str, num_str) return num_str
     }
 }
 
+# compute x << y, y >= 0
+sub blsft { #(num_str, num_str) return num_str
+    &bmul($_[$[], &bpow(2, $_[$[+1]));
+}
+
+# compute x >> y, y >= 0
+sub brsft { #(num_str, num_str) return num_str
+    &bdiv($_[$[], &bpow(2, $_[$[+1]));
+}
+
+# compute x & y
+sub band { #(num_str, num_str) return num_str
+    local($x,$y,$r,$m,$xr,$yr) = (&bnorm($_[$[]),&bnorm($_[$[+1]),0,1);
+    if ($x eq 'NaN' || $y eq 'NaN') {
+	'NaN';
+    } else {
+	while ($x ne '+0' && $y ne '+0') {
+	    ($x, $xr) = &bdiv($x, 0x10000);
+	    ($y, $yr) = &bdiv($y, 0x10000);
+	    $r = &badd(&bmul(int $xr & $yr, $m), $r);
+	    $m = &bmul($m, 0x10000);
+	}
+	$r;
+    }
+}
+
+# compute x | y
+sub bior { #(num_str, num_str) return num_str
+    local($x,$y,$r,$m,$xr,$yr) = (&bnorm($_[$[]),&bnorm($_[$[+1]),0,1);
+    if ($x eq 'NaN' || $y eq 'NaN') {
+	'NaN';
+    } else {
+	while ($x ne '+0' || $y ne '+0') {
+	    ($x, $xr) = &bdiv($x, 0x10000);
+	    ($y, $yr) = &bdiv($y, 0x10000);
+	    $r = &badd(&bmul(int $xr | $yr, $m), $r);
+	    $m = &bmul($m, 0x10000);
+	}
+	$r;
+    }
+}
+
+# compute x ^ y
+sub bxor { #(num_str, num_str) return num_str
+    local($x,$y,$r,$m,$xr,$yr) = (&bnorm($_[$[]),&bnorm($_[$[+1]),0,1);
+    if ($x eq 'NaN' || $y eq 'NaN') {
+	'NaN';
+    } else {
+	while ($x ne '+0' || $y ne '+0') {
+	    ($x, $xr) = &bdiv($x, 0x10000);
+	    ($y, $yr) = &bdiv($y, 0x10000);
+	    $r = &badd(&bmul(int $xr ^ $yr, $m), $r);
+	    $m = &bmul($m, 0x10000);
+	}
+	$r;
+    }
+}
+
+# represent ~x as twos-complement number
+sub bnot { #(num_str) return num_str
+    &bsub(-1,$_[$[]);
+}
+
 1;
 __END__
 
@@ -350,6 +449,12 @@ Math::BigInt - Arbitrary size integer math package
   $i->bmod(BINT) return BINT         modulus
   $i->bgcd(BINT) return BINT         greatest common divisor
   $i->bnorm return BINT              normalization
+  $i->blsft(BINT) return BINT        left shift
+  $i->brsft(BINT) return (BINT,BINT) right shift (quo,rem) just quo if scalar
+  $i->band(BINT) return BINT         bit-wise and
+  $i->bior(BINT) return BINT         bit-wise inclusive or
+  $i->bxor(BINT) return BINT         bit-wise exclusive or
+  $i->bnot return BINT               bit-wise not
 
 =head1 DESCRIPTION