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]}) :
$_[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
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.
# 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('-');
$_;
}
} elsif ($y eq 'NaN') {
undef;
} else {
- &cmp($x,$y);
+ &cmp($x,$y) <=> 0;
}
}
$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);
}
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;
}
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;
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) {
}
}
+# 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__
$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
'1 23 456 7890' canonical value '+1234567890'
+=head1 Autocreating constants
+
+After C<use Math::BigInt ':constant'> all the integer decimal constants
+in the given scope are converted to C<Math::BigInt>. 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
projects / p5sagit/p5-mst-13.2.git / blobdiff