X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?a=blobdiff_plain;f=lib%2FMath%2FBigInt.pm;h=839b746c24f440dc024aadf355a452daf51500f5;hb=b82d478d407f1381d69179104035c975c1d1402e;hp=a4d8b6bd182aba421005af7595a87a47cf5f1b8c;hpb=1e2e1ae8d60a2653b0297f8d75f9d4fe5abfc82b;p=p5sagit%2Fp5-mst-13.2.git diff --git a/lib/Math/BigInt.pm b/lib/Math/BigInt.pm index a4d8b6b..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 @@ -36,9 +44,20 @@ sub stringify { "${$_[0]}" } sub numify { 0 + "${$_[0]}" } # Not needed, additional overhead # comparing to direct compilation based on # stringify +sub import { + shift; + return unless @_; + die "unknown import: @_" unless @_ == 1 and $_[0] eq ':constant'; + overload::constant integer => sub {Math::BigInt->new(shift)}; +} $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. @@ -76,8 +95,8 @@ sub external { #(int_num_array) return num_str # Negate input value. sub bneg { #(num_str) return num_str local($_) = &bnorm(@_); - vec($_,0,8) ^= ord('+') ^ ord('-') unless $_ eq '+0'; - s/^H/N/; + return $_ if $_ eq '+0' or $_ eq 'NaN'; + vec($_,0,8) ^= ord('+') ^ ord('-'); $_; } @@ -100,7 +119,7 @@ sub bcmp { #(num_str, num_str) return cond_code } elsif ($y eq 'NaN') { undef; } else { - &cmp($x,$y); + &cmp($x,$y) <=> 0; } } @@ -171,11 +190,11 @@ sub add { #(int_num_array, int_num_array) return int_num_array $car = 0; for $x (@x) { last unless @y || $car; - $x -= 1e5 if $car = (($x += shift(@y) + $car) >= 1e5); + $x -= 1e5 if $car = (($x += (@y ? shift(@y) : 0) + $car) >= 1e5) ? 1 : 0; } for $y (@y) { last unless $car; - $y -= 1e5 if $car = (($y += $car) >= 1e5); + $y -= 1e5 if $car = (($y += $car) >= 1e5) ? 1 : 0; } (@x, @y, $car); } @@ -185,8 +204,8 @@ sub sub { #(int_num_array, int_num_array) return int_num_array local(*sx, *sy) = @_; $bar = 0; for $sx (@sx) { - last unless @y || $bar; - $sx += 1e5 if $bar = (($sx -= shift(@sy) + $bar) < 0); + last unless @sy || $bar; + $sx += 1e5 if $bar = (($sx -= (@sy ? shift(@sy) : 0) + $bar) < 0); } @sx; } @@ -214,9 +233,15 @@ sub mul { #(*int_num_array, *int_num_array) return int_num_array for $x (@x) { ($car, $cty) = (0, $[); for $y (@y) { - $prod = $x * $y + $prod[$cty] + $car; + $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; @@ -241,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,-1]; + $v2 = 0 unless $v2; while ($#x > $#y) { ($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) { @@ -322,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__ @@ -344,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 @@ -384,6 +495,19 @@ are not numbers, as well as the result of dividing by zero. '1 23 456 7890' canonical value '+1234567890' +=head1 Autocreating constants + +After C all the integer decimal constants +in the given scope are converted to C. This conversion +happens at compile time. + +In particular + + perl -MMath::BigInt=:constant -e 'print 2**100' + +print the integer value of C<2**100>. Note that without conversion of +constants the expression 2**100 will be calculated as floating point number. + =head1 BUGS The current version of this module is a preliminary version of the