4 '+' => sub {new Math::BigInt &badd},
5 '-' => sub {new Math::BigInt
6 $_[2]? bsub($_[1],${$_[0]}) : bsub(${$_[0]},$_[1])},
7 '<=>' => sub {$_[2]? bcmp($_[1],${$_[0]}) : bcmp(${$_[0]},$_[1])},
8 'cmp' => sub {$_[2]? ($_[1] cmp ${$_[0]}) : (${$_[0]} cmp $_[1])},
9 '*' => sub {new Math::BigInt &bmul},
10 '/' => sub {new Math::BigInt
11 $_[2]? scalar bdiv($_[1],${$_[0]}) :
12 scalar bdiv(${$_[0]},$_[1])},
13 '%' => sub {new Math::BigInt
14 $_[2]? bmod($_[1],${$_[0]}) : bmod(${$_[0]},$_[1])},
15 '**' => sub {new Math::BigInt
16 $_[2]? bpow($_[1],${$_[0]}) : bpow(${$_[0]},$_[1])},
17 'neg' => sub {new Math::BigInt &bneg},
18 'abs' => sub {new Math::BigInt &babs},
22 0+ numify) # Order of arguments unsignificant
29 my($foo) = bnorm(shift);
30 die "Not a number initialized to Math::BigInt" if !$NaNOK && $foo eq "NaN";
33 sub stringify { "${$_[0]}" }
34 sub numify { 0 + "${$_[0]}" } # Not needed, additional overhead
35 # comparing to direct compilation based on
40 die "unknown import: @_" unless @_ == 1 and $_[0] eq ':constant';
41 overload::constant integer => sub {Math::BigInt->new(shift)};
47 # normalize string form of number. Strip leading zeros. Strip any
48 # white space and add a sign, if missing.
49 # Strings that are not numbers result the value 'NaN'.
51 sub bnorm { #(num_str) return num_str
53 s/\s+//g; # strip white space
54 if (s/^([+-]?)0*(\d+)$/$1$2/) { # test if number
55 substr($_,$[,0) = '+' unless $1; # Add missing sign
63 # Convert a number from string format to internal base 100000 format.
64 # Assumes normalized value as input.
65 sub internal { #(num_str) return int_num_array
67 ($is,$il) = (substr($d,$[,1),length($d)-2);
69 ($is, reverse(unpack("a" . ($il%5+1) . ("a5" x ($il/5)), $d)));
72 # Convert a number from internal base 100000 format to string format.
73 # This routine scribbles all over input array.
74 sub external { #(int_num_array) return num_str
76 grep($_ > 9999 || ($_ = substr('0000'.$_,-5)), @_); # zero pad
77 &bnorm(join('', $es, reverse(@_))); # reverse concat and normalize
81 sub bneg { #(num_str) return num_str
82 local($_) = &bnorm(@_);
83 return $_ if $_ eq '+0' or $_ eq 'NaN';
84 vec($_,0,8) ^= ord('+') ^ ord('-');
88 # Returns the absolute value of the input.
89 sub babs { #(num_str) return num_str
93 sub abs { # post-normalized abs for internal use
99 # Compares 2 values. Returns one of undef, <0, =0, >0. (suitable for sort)
100 sub bcmp { #(num_str, num_str) return cond_code
101 local($x,$y) = (&bnorm($_[$[]),&bnorm($_[$[+1]));
104 } elsif ($y eq 'NaN') {
111 sub cmp { # post-normalized compare for internal use
112 local($cx, $cy) = @_;
114 return 0 if ($cx eq $cy);
116 local($sx, $sy) = (substr($cx, 0, 1), substr($cy, 0, 1));
120 return 1 if ($sy eq '-' || $cy eq '+0');
121 $ld = length($cx) - length($cy);
124 } else { # $sx eq '-'
125 return -1 if ($sy eq '+');
126 $ld = length($cy) - length($cx);
132 sub badd { #(num_str, num_str) return num_str
133 local(*x, *y); ($x, $y) = (&bnorm($_[$[]),&bnorm($_[$[+1]));
136 } elsif ($y eq 'NaN') {
139 @x = &internal($x); # convert to internal form
141 local($sx, $sy) = (shift @x, shift @y); # get signs
143 &external($sx, &add(*x, *y)); # if same sign add
145 ($x, $y) = (&abs($x),&abs($y)); # make abs
146 if (&cmp($y,$x) > 0) {
147 &external($sy, &sub(*y, *x));
149 &external($sx, &sub(*x, *y));
155 sub bsub { #(num_str, num_str) return num_str
156 &badd($_[$[],&bneg($_[$[+1]));
159 # GCD -- Euclids algorithm Knuth Vol 2 pg 296
160 sub bgcd { #(num_str, num_str) return num_str
161 local($x,$y) = (&bnorm($_[$[]),&bnorm($_[$[+1]));
162 if ($x eq 'NaN' || $y eq 'NaN') {
165 ($x, $y) = ($y,&bmod($x,$y)) while $y ne '+0';
170 # routine to add two base 1e5 numbers
171 # stolen from Knuth Vol 2 Algorithm A pg 231
172 # there are separate routines to add and sub as per Kunth pg 233
173 sub add { #(int_num_array, int_num_array) return int_num_array
177 last unless @y || $car;
178 $x -= 1e5 if $car = (($x += (@y ? shift(@y) : 0) + $car) >= 1e5) ? 1 : 0;
182 $y -= 1e5 if $car = (($y += $car) >= 1e5) ? 1 : 0;
187 # subtract base 1e5 numbers -- stolen from Knuth Vol 2 pg 232, $x > $y
188 sub sub { #(int_num_array, int_num_array) return int_num_array
189 local(*sx, *sy) = @_;
192 last unless @sy || $bar;
193 $sx += 1e5 if $bar = (($sx -= (@sy ? shift(@sy) : 0) + $bar) < 0);
198 # multiply two numbers -- stolen from Knuth Vol 2 pg 233
199 sub bmul { #(num_str, num_str) return num_str
200 local(*x, *y); ($x, $y) = (&bnorm($_[$[]), &bnorm($_[$[+1]));
203 } elsif ($y eq 'NaN') {
208 &external(&mul(*x,*y));
212 # multiply two numbers in internal representation
213 # destroys the arguments, supposes that two arguments are different
214 sub mul { #(*int_num_array, *int_num_array) return int_num_array
215 local(*x, *y) = (shift, shift);
216 local($signr) = (shift @x ne shift @y) ? '-' : '+';
219 ($car, $cty) = (0, $[);
221 $prod = $x * $y + ($prod[$cty] || 0) + $car;
223 $prod - ($car = int($prod * 1e-5)) * 1e5;
225 $prod[$cty] += $car if $car;
232 sub bmod { #(num_str, num_str) return num_str
236 sub bdiv { #(dividend: num_str, divisor: num_str) return num_str
237 local (*x, *y); ($x, $y) = (&bnorm($_[$[]), &bnorm($_[$[+1]));
238 return wantarray ? ('NaN','NaN') : 'NaN'
239 if ($x eq 'NaN' || $y eq 'NaN' || $y eq '+0');
240 return wantarray ? ('+0',$x) : '+0' if (&cmp(&abs($x),&abs($y)) < 0);
241 @x = &internal($x); @y = &internal($y);
243 $sr = (shift @x ne shift @y) ? '-' : '+';
244 $car = $bar = $prd = 0;
245 if (($dd = int(1e5/($y[$#y]+1))) != 1) {
247 $x = $x * $dd + $car;
248 $x -= ($car = int($x * 1e-5)) * 1e5;
250 push(@x, $car); $car = 0;
252 $y = $y * $dd + $car;
253 $y -= ($car = int($y * 1e-5)) * 1e5;
259 @q = (); ($v2,$v1) = @y[-2,-1];
261 ($u2,$u1,$u0) = @x[-3..-1];
262 $q = (($u0 == $v1) ? 99999 : int(($u0*1e5+$u1)/$v1));
263 --$q while ($v2*$q > ($u0*1e5+$u1-$q*$v1)*1e5+$u2);
265 ($car, $bar) = (0,0);
266 for ($y = $[, $x = $#x-$#y+$[-1; $y <= $#y; ++$y,++$x) {
267 $prd = $q * $y[$y] + $car;
268 $prd -= ($car = int($prd * 1e-5)) * 1e5;
269 $x[$x] += 1e5 if ($bar = (($x[$x] -= $prd + $bar) < 0));
271 if ($x[$#x] < $car + $bar) {
273 for ($y = $[, $x = $#x-$#y+$[-1; $y <= $#y; ++$y,++$x) {
275 if ($car = (($x[$x] += $y[$y] + $car) > 1e5));
279 pop(@x); unshift(@q, $q);
285 for $x (reverse @x) {
286 $prd = $car * 1e5 + $x;
287 $car = $prd - ($tmp = int($prd / $dd)) * $dd;
294 (&external($sr, @q), &external($srem, @d, $zero));
300 # compute power of two numbers -- stolen from Knuth Vol 2 pg 233
301 sub bpow { #(num_str, num_str) return num_str
302 local(*x, *y); ($x, $y) = (&bnorm($_[$[]), &bnorm($_[$[+1]));
305 } elsif ($y eq 'NaN') {
307 } elsif ($x eq '+1') {
309 } elsif ($x eq '-1') {
310 &bmod($x,2) ? '-1': '+1';
311 } elsif ($y =~ /^-/) {
313 } elsif ($x eq '+0' && $y eq '+0') {
318 local(@pow)=&internal("+1");
319 local($y1,$res,@tmp1,@tmp2)=(1); # need tmp to send to mul
321 ($y,$res)=&bdiv($y,2);
322 if ($res ne '+0') {@tmp=@pow2; @pow=&mul(*pow,*tmp);}
323 if ($y ne '+0') {@tmp=@pow2;@pow2=&mul(*pow2,*tmp);}
334 Math::BigInt - Arbitrary size integer math package
339 $i = Math::BigInt->new($string);
341 $i->bneg return BINT negation
342 $i->babs return BINT absolute value
343 $i->bcmp(BINT) return CODE compare numbers (undef,<0,=0,>0)
344 $i->badd(BINT) return BINT addition
345 $i->bsub(BINT) return BINT subtraction
346 $i->bmul(BINT) return BINT multiplication
347 $i->bdiv(BINT) return (BINT,BINT) division (quo,rem) just quo if scalar
348 $i->bmod(BINT) return BINT modulus
349 $i->bgcd(BINT) return BINT greatest common divisor
350 $i->bnorm return BINT normalization
354 All basic math operations are overloaded if you declare your big
357 $i = new Math::BigInt '123 456 789 123 456 789';
362 =item Canonical notation
364 Big integer value are strings of the form C</^[+-]\d+$/> with leading
369 Input values to these routines may be strings of the form
370 C</^\s*[+-]?[\d\s]+$/>.
374 Output values always always in canonical form
378 Actual math is done in an internal format consisting of an array
379 whose first element is the sign (/^[+-]$/) and whose remaining
380 elements are base 100000 digits with the least significant digit first.
381 The string 'NaN' is used to represent the result when input arguments
382 are not numbers, as well as the result of dividing by zero.
386 '+0' canonical zero value
387 ' -123 123 123' canonical value '-123123123'
388 '1 23 456 7890' canonical value '+1234567890'
391 =head1 Autocreating constants
393 After C<use Math::BigInt ':constant'> all the integer decimal constants
394 in the given scope are converted to C<Math::BigInt>. This conversion
395 happens at compile time.
399 perl -MMath::BigInt=:constant -e 'print 2**100'
401 print the integer value of C<2**100>. Note that without conversion of
402 constants the expression 2**100 will be calculated as floating point number.
406 The current version of this module is a preliminary version of the
407 real thing that is currently (as of perl5.002) under development.
411 Mark Biggar, overloaded interface by Ilya Zakharevich.