1 package Math::BigInt::Calc;
5 # use warnings; # dont use warnings for older Perls
8 use vars qw/@ISA $VERSION/;
13 # Package to store unsigned big integers in decimal and do math with them
15 # Internally the numbers are stored in an array with at least 1 element, no
16 # leading zero parts (except the first) and in base 1eX where X is determined
17 # automatically at loading time to be the maximum possible value
20 # - fully remove funky $# stuff (maybe)
22 # USE_MUL: due to problems on certain os (os390, posix-bc) "* 1e-5" is used
23 # instead of "/ 1e5" at some places, (marked with USE_MUL). Other platforms
24 # BS2000, some Crays need USE_DIV instead.
25 # The BEGIN block is used to determine which of the two variants gives the
28 ##############################################################################
29 # global constants, flags and accessory
31 # constants for easier life
33 my ($MBASE,$BASE,$RBASE,$BASE_LEN,$MAX_VAL,$BASE_LEN2,$BASE_LEN_SMALL);
34 my ($AND_BITS,$XOR_BITS,$OR_BITS);
35 my ($AND_MASK,$XOR_MASK,$OR_MASK);
40 # set/get the BASE_LEN and assorted other, connected values
41 # used only be the testsuite, set is used only by the BEGIN block below
47 # find whether we can use mul or div or none in mul()/div()
48 # (in last case reduce BASE_LEN_SMALL)
49 $BASE_LEN_SMALL = $b+1;
51 while (--$BASE_LEN_SMALL > 5)
53 $MBASE = int("1e".$BASE_LEN_SMALL);
54 $RBASE = abs('1e-'.$BASE_LEN_SMALL); # see USE_MUL
56 $caught += 1 if (int($MBASE * $RBASE) != 1); # should be 1
57 $caught += 2 if (int($MBASE / $MBASE) != 1); # should be 1
60 # BASE_LEN is used for anything else than mul()/div()
61 $BASE_LEN = $BASE_LEN_SMALL;
62 $BASE_LEN = shift if (defined $_[0]); # one more arg?
63 $BASE = int("1e".$BASE_LEN);
65 $BASE_LEN2 = int($BASE_LEN_SMALL / 2); # for mul shortcut
66 $MBASE = int("1e".$BASE_LEN_SMALL);
67 $RBASE = abs('1e-'.$BASE_LEN_SMALL); # see USE_MUL
70 $LEN_CONVERT = 1 if $BASE_LEN_SMALL != $BASE_LEN;
72 #print "BASE_LEN: $BASE_LEN MAX_VAL: $MAX_VAL BASE: $BASE RBASE: $RBASE ";
73 #print "BASE_LEN_SMALL: $BASE_LEN_SMALL MBASE: $MBASE\n";
80 *{_mul} = \&_mul_use_mul;
81 *{_div} = \&_div_use_mul;
83 else # $caught must be 2, since it can't be 1 nor 3
86 *{_mul} = \&_mul_use_div;
87 *{_div} = \&_div_use_div;
90 return $BASE_LEN unless wantarray;
91 return ($BASE_LEN, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN_SMALL, $MAX_VAL);
96 # from Daniel Pfeiffer: determine largest group of digits that is precisely
97 # multipliable with itself plus carry
98 # Test now changed to expect the proper pattern, not a result off by 1 or 2
99 my ($e, $num) = 3; # lowest value we will use is 3+1-1 = 3
102 $num = ('9' x ++$e) + 0;
104 } while ("$num" =~ /9{$e}0{$e}/); # must be a certain pattern
105 $e--; # last test failed, so retract one step
106 # the limits below brush the problems with the test above under the rug:
107 # the test should be able to find the proper $e automatically
108 $e = 5 if $^O =~ /^uts/; # UTS get's some special treatment
109 $e = 5 if $^O =~ /^unicos/; # unicos is also problematic (6 seems to work
110 # there, but we play safe)
111 $e = 7 if $e > 7; # cap, for VMS, OS/390 and other 64 bit systems
112 # 8 fails inside random testsuite, so take 7
114 # determine how many digits fit into an integer and can be safely added
115 # together plus carry w/o causing an overflow
117 # this below detects 15 on a 64 bit system, because after that it becomes
118 # 1e16 and not 1000000 :/ I can make it detect 18, but then I get a lot of
119 # test failures. Ugh! (Tomake detect 18: uncomment lines marked with *)
121 my $bi = 5; # approx. 16 bit
122 $num = int('9' x $bi);
124 # while ( ($num+$num+1) eq '1' . '9' x $bi) # *
125 while ( int($num+$num+1) eq '1' . '9' x $bi)
127 $bi++; $num = int('9' x $bi);
128 # $bi++; $num *= 10; $num += 9; # *
130 $bi--; # back off one step
131 # by setting them equal, we ignore the findings and use the default
132 # one-size-fits-all approach from former versions
133 $bi = $e; # XXX, this should work always
135 __PACKAGE__->_base_len($e,$bi); # set and store
137 # find out how many bits _and, _or and _xor can take (old default = 16)
138 # I don't think anybody has yet 128 bit scalars, so let's play safe.
139 local $^W = 0; # don't warn about 'nonportable number'
140 $AND_BITS = 15; $XOR_BITS = 15; $OR_BITS = 15;
142 # find max bits, we will not go higher than numberofbits that fit into $BASE
143 # to make _and etc simpler (and faster for smaller, slower for large numbers)
145 while (2 ** $max < $BASE) { $max++; }
149 $x = oct('0b' . '1' x $AND_BITS); $y = $x & $x;
150 $z = (2 ** $AND_BITS) - 1;
151 } while ($AND_BITS < $max && $x == $z && $y == $x);
152 $AND_BITS --; # retreat one step
155 $x = oct('0b' . '1' x $XOR_BITS); $y = $x ^ 0;
156 $z = (2 ** $XOR_BITS) - 1;
157 } while ($XOR_BITS < $max && $x == $z && $y == $x);
158 $XOR_BITS --; # retreat one step
161 $x = oct('0b' . '1' x $OR_BITS); $y = $x | $x;
162 $z = (2 ** $OR_BITS) - 1;
163 } while ($OR_BITS < $max && $x == $z && $y == $x);
164 $OR_BITS --; # retreat one step
168 ##############################################################################
169 # convert between the "small" and the "large" representation
173 # take an array in base $BASE_LEN_SMALL and convert it in-place to $BASE_LEN
176 # print "_to_large $BASE_LEN_SMALL => $BASE_LEN\n";
178 return $x if $LEN_CONVERT == 0 || # nothing to converconvertor
179 @$x == 1; # only one element => early out
181 # 12345 67890 12345 67890 contents
183 # 123456 7890123 4567890 contents
186 # my @d; my $str = '';
187 # my $z = '0' x $BASE_LEN_SMALL;
190 # # ... . 04321 . 000321
191 # $str = substr($z.$_,-$BASE_LEN_SMALL,$BASE_LEN_SMALL) . $str;
192 # if (length($str) > $BASE_LEN)
194 # push @d, substr($str,-$BASE_LEN,$BASE_LEN); # extract one piece
195 # substr($str,-$BASE_LEN,$BASE_LEN) = ''; # remove it
198 # push @d, $str if $str !~ /^0*$/; # extract last piece
200 # $x->[-1] = int($x->[-1]); # strip leading zero
204 my $l = scalar @$x; # number of parts
205 $l --; $ret .= int($x->[$l]); $l--;
206 my $z = '0' x ($BASE_LEN_SMALL-1);
209 $ret .= substr($z.$x->[$l],-$BASE_LEN_SMALL);
212 my $str = _new($c,\$ret); # make array
213 @$x = @$str; # clobber contents of $x
214 $x->[-1] = int($x->[-1]); # strip leading zero
219 # take an array in base $BASE_LEN and convert it in-place to $BASE_LEN_SMALL
222 return $x if $LEN_CONVERT == 0; # nothing to do
223 return $x if @$x == 1 && length(int($x->[0])) <= $BASE_LEN_SMALL;
226 my $il = length($$d)-1;
227 ## this leaves '00000' instead of int 0 and will be corrected after any op
228 # clobber contents of $x
229 @$x = reverse(unpack("a" . ($il % $BASE_LEN_SMALL+1)
230 . ("a$BASE_LEN_SMALL" x ($il / $BASE_LEN_SMALL)), $$d));
232 $x->[-1] = int($x->[-1]); # strip leading zero
235 ###############################################################################
239 # (ref to string) return ref to num_array
240 # Convert a number from string format (without sign) to internal base
241 # 1ex format. Assumes normalized value as input.
243 my $il = length($$d)-1;
244 # this leaves '00000' instead of int 0 and will be corrected after any op
245 [ reverse(unpack("a" . ($il % $BASE_LEN+1)
246 . ("a$BASE_LEN" x ($il / $BASE_LEN)), $$d)) ];
251 $AND_MASK = __PACKAGE__->_new( \( 2 ** $AND_BITS ));
252 $XOR_MASK = __PACKAGE__->_new( \( 2 ** $XOR_BITS ));
253 $OR_MASK = __PACKAGE__->_new( \( 2 ** $OR_BITS ));
270 # create a two (for _pow)
279 # catch and throw away
282 ##############################################################################
283 # convert back to string and number
287 # (ref to BINT) return num_str
288 # Convert number from internal base 100000 format to string format.
289 # internal format is always normalized (no leading zeros, "-0" => "+0")
293 my $l = scalar @$ar; # number of parts
294 return $nan if $l < 1; # should not happen
296 # handle first one different to strip leading zeros from it (there are no
297 # leading zero parts in internal representation)
298 $l --; $ret .= int($ar->[$l]); $l--;
299 # Interestingly, the pre-padd method uses more time
300 # the old grep variant takes longer (14 to 10 sec)
301 my $z = '0' x ($BASE_LEN-1);
304 $ret .= substr($z.$ar->[$l],-$BASE_LEN); # fastest way I could think of
312 # Make a number (scalar int/float) from a BigInt object
314 return $x->[0] if scalar @$x == 1; # below $BASE
319 $num += $fac*$_; $fac *= $BASE;
324 ##############################################################################
329 # (ref to int_num_array, ref to int_num_array)
330 # routine to add two base 1eX numbers
331 # stolen from Knuth Vol 2 Algorithm A pg 231
332 # there are separate routines to add and sub as per Knuth pg 233
333 # This routine clobbers up array x, but not y.
337 return $x if (@$y == 1) && $y->[0] == 0; # $x + 0 => $x
338 if ((@$x == 1) && $x->[0] == 0) # 0 + $y => $y->copy
340 # twice as slow as $x = [ @$y ], but necc. to retain $x as ref :(
341 @$x = @$y; return $x;
344 # for each in Y, add Y to X and carry. If after that, something is left in
345 # X, foreach in X add carry to X and then return X, carry
346 # Trades one "$j++" for having to shift arrays, $j could be made integer
347 # but this would impose a limit to number-length of 2**32.
348 my $i; my $car = 0; my $j = 0;
351 $x->[$j] -= $BASE if $car = (($x->[$j] += $i + $car) >= $BASE) ? 1 : 0;
356 $x->[$j] -= $BASE if $car = (($x->[$j] += $car) >= $BASE) ? 1 : 0; $j++;
363 # (ref to int_num_array, ref to int_num_array)
364 # routine to add 1 to a base 1eX numbers
365 # This routine clobbers up array x, but not y.
370 return $x if (($i += 1) < $BASE); # early out
371 $i = 0; # overflow, next
373 push @$x,1 if ($x->[-1] == 0); # last overflowed, so extend
379 # (ref to int_num_array, ref to int_num_array)
380 # routine to add 1 to a base 1eX numbers
381 # This routine clobbers up array x, but not y.
384 my $MAX = $BASE-1; # since MAX_VAL based on MBASE
387 last if (($i -= 1) >= 0); # early out
388 $i = $MAX; # overflow, next
390 pop @$x if $x->[-1] == 0 && @$x > 1; # last overflowed (but leave 0)
396 # (ref to int_num_array, ref to int_num_array, swap)
397 # subtract base 1eX numbers -- stolen from Knuth Vol 2 pg 232, $x > $y
398 # subtract Y from X by modifying x in place
399 my ($c,$sx,$sy,$s) = @_;
401 my $car = 0; my $i; my $j = 0;
407 last unless defined $sy->[$j] || $car;
408 $i += $BASE if $car = (($i -= ($sy->[$j] || 0) + $car) < 0); $j++;
410 # might leave leading zeros, so fix that
411 return __strip_zeros($sx);
413 #print "case 1 (swap)\n";
416 # we can't do an early out if $x is than $y, since we
417 # need to copy the high chunks from $y. Found by Bob Mathews.
418 #last unless defined $sy->[$j] || $car;
420 if $car = (($sy->[$j] = $i-($sy->[$j]||0) - $car) < 0);
423 # might leave leading zeros, so fix that
429 # compute $x ** 2 or $x * $x in-place and return $x
432 # From: Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and
433 # S. Vanstone., Chapter 14
435 #14.16 Algorithm Multiple-precision squaring
436 #INPUT: positive integer x = (xt 1 xt 2 ... x1 x0)b.
437 #OUTPUT: x * x = x ** 2 in radix b representation.
438 #1. For i from 0 to (2t - 1) do: wi <- 0.
439 #2. For i from 0 to (t - 1) do the following:
440 # 2.1 (uv)b w2i + xi * xi, w2i v, c u.
441 # 2.2 For j from (i + 1)to (t - 1) do the following:
442 # (uv)b <- wi+j + 2*xj * xi + c, wi+j <- v, c <- u.
444 #3. Return((w2t-1 w2t-2 ... w1 w0)b).
446 # # Note: That description is crap. Half of the symbols are not explained or
447 # # used with out beeing set.
448 # my $t = scalar @$x; # count
450 # for ($i = 0; $i < $t; $i++)
452 # $x->[$i] = $x->[$i*2] + $x[$i]*$x[$i];
453 # $x->[$i*2] = $x[$i]; $c = $x[$i];
454 # for ($j = $i+1; $j < $t; $j++)
456 # $x->[$i] = $x->[$i+$j] + 2 * $x->[$i] * $x->[$j];
457 # $x->[$i+$j] = $x[$j]; $c = $x[$i];
459 # $x->[$i+$t] = $x[$i];
466 # (ref to int_num_array, ref to int_num_array)
467 # multiply two numbers in internal representation
468 # modifies first arg, second need not be different from first
469 my ($c,$xv,$yv) = @_;
471 # shortcut for two very short numbers (improved by Nathan Zook)
472 # works also if xv and yv are the same reference
473 if ((@$xv == 1) && (@$yv == 1))
475 if (($xv->[0] *= $yv->[0]) >= $MBASE)
477 $xv->[0] = $xv->[0] - ($xv->[1] = int($xv->[0] * $RBASE)) * $MBASE;
481 # shortcut for result == 0
482 if ( ((@$xv == 1) && ($xv->[0] == 0)) ||
483 ((@$yv == 1) && ($yv->[0] == 0)) )
489 # since multiplying $x with $x fails, make copy in this case
490 $yv = [@$xv] if $xv == $yv; # same references?
491 # $yv = [@$xv] if "$xv" eq "$yv"; # same references?
493 # since multiplying $x with $x would fail here, use the faster squaring
494 # return _square($c,$xv) if $xv == $yv; # same reference?
496 if ($LEN_CONVERT != 0)
498 $c->_to_small($xv); $c->_to_small($yv);
501 my @prod = (); my ($prod,$car,$cty,$xi,$yi);
510 # $prod = $xi * $yi + ($prod[$cty] || 0) + $car;
512 # $prod - ($car = int($prod * RBASE)) * $MBASE; # see USE_MUL
514 # $prod[$cty] += $car if $car; # need really to check for 0?
518 # looping through this if $xi == 0 is silly - so optimize it away!
519 $xi = (shift @prod || 0), next if $xi == 0;
522 $prod = $xi * $yi + ($prod[$cty] || 0) + $car;
523 ## this is actually a tad slower
524 ## $prod = $prod[$cty]; $prod += ($car + $xi * $yi); # no ||0 here
526 $prod - ($car = int($prod * $RBASE)) * $MBASE; # see USE_MUL
528 $prod[$cty] += $car if $car; # need really to check for 0?
529 $xi = shift @prod || 0; # || 0 makes v5.005_3 happy
532 if ($LEN_CONVERT != 0)
546 # (ref to int_num_array, ref to int_num_array)
547 # multiply two numbers in internal representation
548 # modifies first arg, second need not be different from first
549 my ($c,$xv,$yv) = @_;
551 # shortcut for two very short numbers (improved by Nathan Zook)
552 # works also if xv and yv are the same reference
553 if ((@$xv == 1) && (@$yv == 1))
555 if (($xv->[0] *= $yv->[0]) >= $MBASE)
558 $xv->[0] - ($xv->[1] = int($xv->[0] / $MBASE)) * $MBASE;
562 # shortcut for result == 0
563 if ( ((@$xv == 1) && ($xv->[0] == 0)) ||
564 ((@$yv == 1) && ($yv->[0] == 0)) )
571 # since multiplying $x with $x fails, make copy in this case
572 $yv = [@$xv] if $xv == $yv; # same references?
573 # $yv = [@$xv] if "$xv" eq "$yv"; # same references?
574 # since multiplying $x with $x would fail here, use the faster squaring
575 # return _square($c,$xv) if $xv == $yv; # same reference?
577 if ($LEN_CONVERT != 0)
579 $c->_to_small($xv); $c->_to_small($yv);
582 my @prod = (); my ($prod,$car,$cty,$xi,$yi);
586 # looping through this if $xi == 0 is silly - so optimize it away!
587 $xi = (shift @prod || 0), next if $xi == 0;
590 $prod = $xi * $yi + ($prod[$cty] || 0) + $car;
592 $prod - ($car = int($prod / $MBASE)) * $MBASE;
594 $prod[$cty] += $car if $car; # need really to check for 0?
595 $xi = shift @prod || 0; # || 0 makes v5.005_3 happy
598 if ($LEN_CONVERT != 0)
612 # ref to array, ref to array, modify first array and return remainder if
614 my ($c,$x,$yorg) = @_;
616 if (@$x == 1 && @$yorg == 1)
618 # shortcut, $yorg and $x are two small numbers
621 my $r = [ $x->[0] % $yorg->[0] ];
622 $x->[0] = int($x->[0] / $yorg->[0]);
627 $x->[0] = int($x->[0] / $yorg->[0]);
634 $rem = _mod($c,[ @$x ],$yorg) if wantarray;
636 # shortcut, $y is < $BASE
637 my $j = scalar @$x; my $r = 0;
638 my $y = $yorg->[0]; my $b;
641 $b = $r * $MBASE + $x->[$j];
642 $x->[$j] = int($b/$y);
645 pop @$x if @$x > 1 && $x->[-1] == 0; # splice up a leading zero
646 return ($x,$rem) if wantarray;
650 my $y = [ @$yorg ]; # always make copy to preserve
651 if ($LEN_CONVERT != 0)
653 $c->_to_small($x); $c->_to_small($y);
656 my ($car,$bar,$prd,$dd,$xi,$yi,@q,$v2,$v1,@d,$tmp,$q,$u2,$u1,$u0);
658 $car = $bar = $prd = 0;
659 if (($dd = int($MBASE/($y->[-1]+1))) != 1)
663 $xi = $xi * $dd + $car;
664 $xi -= ($car = int($xi * $RBASE)) * $MBASE; # see USE_MUL
666 push(@$x, $car); $car = 0;
669 $yi = $yi * $dd + $car;
670 $yi -= ($car = int($yi * $RBASE)) * $MBASE; # see USE_MUL
677 @q = (); ($v2,$v1) = @$y[-2,-1];
681 ($u2,$u1,$u0) = @$x[-3..-1];
683 #warn "oups v1 is 0, u0: $u0 $y->[-2] $y->[-1] l ",scalar @$y,"\n"
685 $q = (($u0 == $v1) ? $MAX_VAL : int(($u0*$MBASE+$u1)/$v1));
686 --$q while ($v2*$q > ($u0*$MBASE+$u1-$q*$v1)*$MBASE+$u2);
689 ($car, $bar) = (0,0);
690 for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
692 $prd = $q * $y->[$yi] + $car;
693 $prd -= ($car = int($prd * $RBASE)) * $MBASE; # see USE_MUL
694 $x->[$xi] += $MBASE if ($bar = (($x->[$xi] -= $prd + $bar) < 0));
696 if ($x->[-1] < $car + $bar)
699 for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
702 if ($car = (($x->[$xi] += $y->[$yi] + $car) > $MBASE));
706 pop(@$x); unshift(@q, $q);
714 for $xi (reverse @$x)
716 $prd = $car * $MBASE + $xi;
717 $car = $prd - ($tmp = int($prd / $dd)) * $dd; # see USE_MUL
727 if ($LEN_CONVERT != 0)
729 $c->_to_large($x); $c->_to_large($d);
739 if ($LEN_CONVERT != 0)
752 # ref to array, ref to array, modify first array and return remainder if
754 my ($c,$x,$yorg) = @_;
756 if (@$x == 1 && @$yorg == 1)
758 # shortcut, $yorg and $x are two small numbers
761 my $r = [ $x->[0] % $yorg->[0] ];
762 $x->[0] = int($x->[0] / $yorg->[0]);
767 $x->[0] = int($x->[0] / $yorg->[0]);
774 $rem = _mod($c,[ @$x ],$yorg) if wantarray;
776 # shortcut, $y is < $BASE
777 my $j = scalar @$x; my $r = 0;
778 my $y = $yorg->[0]; my $b;
781 $b = $r * $MBASE + $x->[$j];
782 $x->[$j] = int($b/$y);
785 pop @$x if @$x > 1 && $x->[-1] == 0; # splice up a leading zero
786 return ($x,$rem) if wantarray;
790 my $y = [ @$yorg ]; # always make copy to preserve
791 if ($LEN_CONVERT != 0)
793 $c->_to_small($x); $c->_to_small($y);
796 my ($car,$bar,$prd,$dd,$xi,$yi,@q,$v2,$v1,@d,$tmp,$q,$u2,$u1,$u0);
798 $car = $bar = $prd = 0;
799 if (($dd = int($MBASE/($y->[-1]+1))) != 1)
803 $xi = $xi * $dd + $car;
804 $xi -= ($car = int($xi / $MBASE)) * $MBASE;
806 push(@$x, $car); $car = 0;
809 $yi = $yi * $dd + $car;
810 $yi -= ($car = int($yi / $MBASE)) * $MBASE;
817 @q = (); ($v2,$v1) = @$y[-2,-1];
821 ($u2,$u1,$u0) = @$x[-3..-1];
823 #warn "oups v1 is 0, u0: $u0 $y->[-2] $y->[-1] l ",scalar @$y,"\n"
825 $q = (($u0 == $v1) ? $MAX_VAL : int(($u0*$MBASE+$u1)/$v1));
826 --$q while ($v2*$q > ($u0*$MBASE+$u1-$q*$v1)*$MBASE+$u2);
829 ($car, $bar) = (0,0);
830 for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
832 $prd = $q * $y->[$yi] + $car;
833 $prd -= ($car = int($prd / $MBASE)) * $MBASE;
834 $x->[$xi] += $MBASE if ($bar = (($x->[$xi] -= $prd + $bar) < 0));
836 if ($x->[-1] < $car + $bar)
839 for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
842 if ($car = (($x->[$xi] += $y->[$yi] + $car) > $MBASE));
846 pop(@$x); unshift(@q, $q);
854 for $xi (reverse @$x)
856 $prd = $car * $MBASE + $xi;
857 $car = $prd - ($tmp = int($prd / $dd)) * $dd;
867 if ($LEN_CONVERT != 0)
869 $c->_to_large($x); $c->_to_large($d);
879 if ($LEN_CONVERT != 0)
890 ##############################################################################
895 # internal absolute post-normalized compare (ignore signs)
896 # ref to array, ref to array, return <0, 0, >0
897 # arrays must have at least one entry; this is not checked for
899 my ($c,$cx,$cy) = @_;
901 # fast comp based on array elements
902 my $lxy = scalar @$cx - scalar @$cy;
903 return -1 if $lxy < 0; # already differs, ret
904 return 1 if $lxy > 0; # ditto
906 # now calculate length based on digits, not parts
907 $lxy = _len($c,$cx) - _len($c,$cy); # difference
908 return -1 if $lxy < 0;
909 return 1 if $lxy > 0;
911 # hm, same lengths, but same contents?
913 # first way takes 5.49 sec instead of 4.87, but has the early out advantage
914 # so grep is slightly faster, but more inflexible. hm. $_ instead of $k
915 # yields 5.6 instead of 5.5 sec huh?
916 # manual way (abort if unequal, good for early ne)
917 my $j = scalar @$cx - 1;
920 last if ($a = $cx->[$j] - $cy->[$j]); $j--;
922 # my $j = scalar @$cx;
925 # last if ($a = $cx->[$j] - $cy->[$j]);
931 # while it early aborts, it is even slower than the manual variant
932 #grep { return $a if ($a = $_ - $cy->[$i++]); } @$cx;
933 # grep way, go trough all (bad for early ne)
934 #grep { $a = $_ - $cy->[$i++]; } @$cx;
940 # compute number of digits in bigint, minus the sign
942 # int() because add/sub sometimes leaves strings (like '00005') instead of
943 # '5' in this place, thus causing length() to report wrong length
946 return (@$cx-1)*$BASE_LEN+length(int($cx->[-1]));
951 # return the nth digit, negative values count backward
952 # zero is rightmost, so _digit(123,0) will give 3
955 my $len = _len('',$x);
957 $n = $len+$n if $n < 0; # -1 last, -2 second-to-last
958 $n = abs($n); # if negative was too big
959 $len--; $n = $len if $n > $len; # n to big?
961 my $elem = int($n / $BASE_LEN); # which array element
962 my $digit = $n % $BASE_LEN; # which digit in this element
963 $elem = '0000'.@$x[$elem]; # get element padded with 0's
964 return substr($elem,-$digit-1,1);
969 # return amount of trailing zeros in decimal
970 # check each array elem in _m for having 0 at end as long as elem == 0
971 # Upon finding a elem != 0, stop
973 my $zeros = 0; my $elem;
978 $elem = "$e"; # preserve x
979 $elem =~ s/.*?(0*$)/$1/; # strip anything not zero
980 $zeros *= $BASE_LEN; # elems * 5
981 $zeros += length($elem); # count trailing zeros
984 $zeros ++; # real else branch: 50% slower!
989 ##############################################################################
994 # return true if arg (BINT or num_str) is zero (array '+', '0')
997 (((scalar @$x == 1) && ($x->[0] == 0))) <=> 0;
1002 # return true if arg (BINT or num_str) is even
1004 (!($x->[0] & 1)) <=> 0;
1009 # return true if arg (BINT or num_str) is even
1012 (($x->[0] & 1)) <=> 0;
1017 # return true if arg (BINT or num_str) is one (array '+', '1')
1020 (scalar @$x == 1) && ($x->[0] == 1) <=> 0;
1025 # internal normalization function that strips leading zeros from the array
1026 # args: ref to array
1029 my $cnt = scalar @$s; # get count of parts
1031 push @$s,0 if $i < 0; # div might return empty results, so fix it
1033 return $s if @$s == 1; # early out
1035 #print "strip: cnt $cnt i $i\n";
1036 # '0', '3', '4', '0', '0',
1041 # => fcnt = cnt - i (5-2 => 3, cnt => 5-1 = 4, throw away from 4th pos)
1042 # >= 1: skip first part (this can be zero)
1043 while ($i > 0) { last if $s->[$i] != 0; $i--; }
1044 $i++; splice @$s,$i if ($i < $cnt); # $i cant be 0
1048 ###############################################################################
1049 # check routine to test internal state of corruptions
1053 # used by the test suite
1056 return "$x is not a reference" if !ref($x);
1058 # are all parts are valid?
1059 my $i = 0; my $j = scalar @$x; my ($e,$try);
1062 $e = $x->[$i]; $e = 'undef' unless defined $e;
1063 $try = '=~ /^[\+]?[0-9]+\$/; '."($x, $e)";
1064 last if $e !~ /^[+]?[0-9]+$/;
1065 $try = '=~ /^[\+]?[0-9]+\$/; '."($x, $e) (stringify)";
1066 last if "$e" !~ /^[+]?[0-9]+$/;
1067 $try = '=~ /^[\+]?[0-9]+\$/; '."($x, $e) (cat-stringify)";
1068 last if '' . "$e" !~ /^[+]?[0-9]+$/;
1069 $try = ' < 0 || >= $BASE; '."($x, $e)";
1070 last if $e <0 || $e >= $BASE;
1071 # this test is disabled, since new/bnorm and certain ops (like early out
1072 # in add/sub) are allowed/expected to leave '00000' in some elements
1073 #$try = '=~ /^00+/; '."($x, $e)";
1074 #last if $e =~ /^00+/;
1077 return "Illegal part '$e' at pos $i (tested: $try)" if $i < $j;
1082 ###############################################################################
1083 ###############################################################################
1084 # some optional routines to make BigInt faster
1088 # if possible, use mod shortcut
1089 my ($c,$x,$yo) = @_;
1091 # slow way since $y to big
1092 if (scalar @$yo > 1)
1094 my ($xo,$rem) = _div($c,$x,$yo);
1098 # both are single element arrays
1099 if (scalar @$x == 1)
1105 # @y is single element, but @x has more than one
1109 # when BASE % Y == 0 then (B * BASE) % Y == 0
1110 # (B * BASE) % $y + A % Y => A % Y
1111 # so need to consider only last element: O(1)
1116 # else need to go trough all elements: O(N), but loop is a bit simplified
1120 $r = ($r + $_) % $y; # not much faster, but heh...
1121 #$r += $_ % $y; $r %= $y;
1128 # else need to go trough all elements: O(N)
1129 my $r = 0; my $bm = 1;
1132 $r = ($_ * $bm + $r) % $y;
1133 $bm = ($bm * $b) % $y;
1135 #$r += ($_ % $y) * $bm;
1147 ##############################################################################
1152 my ($c,$x,$y,$n) = @_;
1156 $n = _new($c,\$n); return _div($c,$x, _pow($c,$n,$y));
1159 # shortcut (faster) for shifting by 10)
1160 # multiples of $BASE_LEN
1161 my $dst = 0; # destination
1162 my $src = _num($c,$y); # as normal int
1163 my $rem = $src % $BASE_LEN; # remainder to shift
1164 $src = int($src / $BASE_LEN); # source
1167 splice (@$x,0,$src); # even faster, 38.4 => 39.3
1171 my $len = scalar @$x - $src; # elems to go
1172 my $vd; my $z = '0'x $BASE_LEN;
1173 $x->[scalar @$x] = 0; # avoid || 0 test inside loop
1176 $vd = $z.$x->[$src];
1177 $vd = substr($vd,-$BASE_LEN,$BASE_LEN-$rem);
1179 $vd = substr($z.$x->[$src],-$rem,$rem) . $vd;
1180 $vd = substr($vd,-$BASE_LEN,$BASE_LEN) if length($vd) > $BASE_LEN;
1181 $x->[$dst] = int($vd);
1184 splice (@$x,$dst) if $dst > 0; # kill left-over array elems
1185 pop @$x if $x->[-1] == 0 && @$x > 1; # kill last element if 0
1192 my ($c,$x,$y,$n) = @_;
1196 $n = _new($c,\$n); return _mul($c,$x, _pow($c,$n,$y));
1199 # shortcut (faster) for shifting by 10) since we are in base 10eX
1200 # multiples of $BASE_LEN:
1201 my $src = scalar @$x; # source
1202 my $len = _num($c,$y); # shift-len as normal int
1203 my $rem = $len % $BASE_LEN; # remainder to shift
1204 my $dst = $src + int($len/$BASE_LEN); # destination
1205 my $vd; # further speedup
1206 $x->[$src] = 0; # avoid first ||0 for speed
1207 my $z = '0' x $BASE_LEN;
1210 $vd = $x->[$src]; $vd = $z.$vd;
1211 $vd = substr($vd,-$BASE_LEN+$rem,$BASE_LEN-$rem);
1212 $vd .= $src > 0 ? substr($z.$x->[$src-1],-$BASE_LEN,$rem) : '0' x $rem;
1213 $vd = substr($vd,-$BASE_LEN,$BASE_LEN) if length($vd) > $BASE_LEN;
1214 $x->[$dst] = int($vd);
1217 # set lowest parts to 0
1218 while ($dst >= 0) { $x->[$dst--] = 0; }
1219 # fix spurios last zero element
1220 splice @$x,-1 if $x->[-1] == 0;
1227 # ref to array, ref to array, return ref to array
1228 my ($c,$cx,$cy) = @_;
1232 my $y1 = _copy($c,$cy);
1233 while (!_is_one($c,$y1))
1235 _mul($c,$pow2,$cx) if _is_odd($c,$y1);
1239 _mul($c,$cx,$pow2) unless _is_one($c,$pow2);
1246 # ref to array, return ref to array
1249 if ((@$cx == 1) && ($cx->[0] <= 2))
1251 $cx->[0] = 1 * ($cx->[0]||1); # 0,1 => 1, 2 => 2
1255 # go forward until $base is exceeded
1256 # limit is either $x or $base (x == 100 means as result too high)
1257 my $steps = 100; $steps = $cx->[0] if @$cx == 1;
1258 my $r = 2; my $cf = 3; my $step = 1; my $last = $r;
1259 while ($r < $BASE && $step < $steps)
1261 $last = $r; $r *= $cf++; $step++;
1263 if ((@$cx == 1) && ($step == $cx->[0]))
1269 my $n = _copy($c,$cx);
1273 while (!(@$n == 1 && $n->[0] == $step))
1275 _mul($c,$cx,$n); _dec($c,$n);
1280 use constant DEBUG => 0;
1284 sub steps { $steps };
1289 # ref to array, return ref to array
1292 if (scalar @$x == 1)
1294 # fit's into one Perl scalar
1295 $x->[0] = int(sqrt($x->[0]));
1298 my $y = _copy($c,$x);
1299 # hopefully _len/2 is < $BASE, the -1 is to always undershot the guess
1300 # since our guess will "grow"
1301 my $l = int((_len($c,$x)-1) / 2);
1303 my $lastelem = $x->[-1]; # for guess
1304 my $elems = scalar @$x - 1;
1305 # not enough digits, but could have more?
1306 if ((length($lastelem) <= 3) && ($elems > 1))
1308 # right-align with zero pad
1309 my $len = length($lastelem) & 1;
1310 print "$lastelem => " if DEBUG;
1311 $lastelem .= substr($x->[-2] . '0' x $BASE_LEN,0,$BASE_LEN);
1312 # former odd => make odd again, or former even to even again
1313 $lastelem = $lastelem / 10 if (length($lastelem) & 1) != $len;
1314 print "$lastelem\n" if DEBUG;
1317 # construct $x (instead of _lsft($c,$x,$l,10)
1318 my $r = $l % $BASE_LEN; # 10000 00000 00000 00000 ($BASE_LEN=5)
1319 $l = int($l / $BASE_LEN);
1320 print "l = $l " if DEBUG;
1322 splice @$x,$l; # keep ref($x), but modify it
1324 # we make the first part of the guess not '1000...0' but int(sqrt($lastelem))
1326 # 14400 00000 => sqrt(14400) => 120
1327 # 144000 000000 => sqrt(144000) => 379
1329 # $x->[$l--] = int('1' . '0' x $r); # old way of guessing
1330 print "$lastelem (elems $elems) => " if DEBUG;
1331 $lastelem = $lastelem / 10 if ($elems & 1 == 1); # odd or even?
1332 my $g = sqrt($lastelem); $g =~ s/\.//; # 2.345 => 2345
1333 $r -= 1 if $elems & 1 == 0; # 70 => 7
1335 # padd with zeros if result is too short
1336 $x->[$l--] = int(substr($g . '0' x $r,0,$r+1));
1337 print "now ",$x->[-1] if DEBUG;
1338 print " would have been ", int('1' . '0' x $r),"\n" if DEBUG;
1340 # If @$x > 1, we could compute the second elem of the guess, too, to create
1341 # an even better guess. Not implemented yet.
1342 $x->[$l--] = 0 while ($l >= 0); # all other digits of guess are zero
1344 print "start x= ",${_str($c,$x)},"\n" if DEBUG;
1347 my $lastlast = _zero();
1348 $steps = 0 if DEBUG;
1349 while (_acmp($c,$last,$x) != 0 && _acmp($c,$lastlast,$x) != 0)
1352 $lastlast = _copy($c,$last);
1353 $last = _copy($c,$x);
1354 _add($c,$x, _div($c,_copy($c,$y),$x));
1356 print " x= ",${_str($c,$x)},"\n" if DEBUG;
1358 print "\nsteps in sqrt: $steps, " if DEBUG;
1359 _dec($c,$x) if _acmp($c,$y,_mul($c,_copy($c,$x),$x)) < 0; # overshot?
1360 print " final ",$x->[-1],"\n" if DEBUG;
1364 ##############################################################################
1371 # the shortcut makes equal, large numbers _really_ fast, and makes only a
1372 # very small performance drop for small numbers (e.g. something with less
1373 # than 32 bit) Since we optimize for large numbers, this is enabled.
1374 return $x if _acmp($c,$x,$y) == 0; # shortcut
1376 my $m = _one(); my ($xr,$yr);
1377 my $mask = $AND_MASK;
1380 my $y1 = _copy($c,$y); # make copy
1384 while (!_is_zero($c,$x1) && !_is_zero($c,$y1))
1386 ($x1, $xr) = _div($c,$x1,$mask);
1387 ($y1, $yr) = _div($c,$y1,$mask);
1389 # make ints() from $xr, $yr
1390 # this is when the AND_BITS are greater tahn $BASE and is slower for
1391 # small (<256 bits) numbers, but faster for large numbers. Disabled
1392 # due to KISS principle
1394 # $b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }
1395 # $b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }
1396 # _add($c,$x, _mul($c, _new( $c, \($xrr & $yrr) ), $m) );
1398 # 0+ due to '&' doesn't work in strings
1399 _add($c,$x, _mul($c, [ 0+$xr->[0] & 0+$yr->[0] ], $m) );
1409 return _zero() if _acmp($c,$x,$y) == 0; # shortcut (see -and)
1411 my $m = _one(); my ($xr,$yr);
1412 my $mask = $XOR_MASK;
1415 my $y1 = _copy($c,$y); # make copy
1419 while (!_is_zero($c,$x1) && !_is_zero($c,$y1))
1421 ($x1, $xr) = _div($c,$x1,$mask);
1422 ($y1, $yr) = _div($c,$y1,$mask);
1423 # make ints() from $xr, $yr (see _and())
1424 #$b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }
1425 #$b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }
1426 #_add($c,$x, _mul($c, _new( $c, \($xrr ^ $yrr) ), $m) );
1428 # 0+ due to '^' doesn't work in strings
1429 _add($c,$x, _mul($c, [ 0+$xr->[0] ^ 0+$yr->[0] ], $m) );
1432 # the loop stops when the shorter of the two numbers is exhausted
1433 # the remainder of the longer one will survive bit-by-bit, so we simple
1434 # multiply-add it in
1435 _add($c,$x, _mul($c, $x1, $m) ) if !_is_zero($c,$x1);
1436 _add($c,$x, _mul($c, $y1, $m) ) if !_is_zero($c,$y1);
1445 return $x if _acmp($c,$x,$y) == 0; # shortcut (see _and)
1447 my $m = _one(); my ($xr,$yr);
1448 my $mask = $OR_MASK;
1451 my $y1 = _copy($c,$y); # make copy
1455 while (!_is_zero($c,$x1) && !_is_zero($c,$y1))
1457 ($x1, $xr) = _div($c,$x1,$mask);
1458 ($y1, $yr) = _div($c,$y1,$mask);
1459 # make ints() from $xr, $yr (see _and())
1460 # $b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }
1461 # $b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }
1462 # _add($c,$x, _mul($c, _new( $c, \($xrr | $yrr) ), $m) );
1464 # 0+ due to '|' doesn't work in strings
1465 _add($c,$x, _mul($c, [ 0+$xr->[0] | 0+$yr->[0] ], $m) );
1468 # the loop stops when the shorter of the two numbers is exhausted
1469 # the remainder of the longer one will survive bit-by-bit, so we simple
1470 # multiply-add it in
1471 _add($c,$x, _mul($c, $x1, $m) ) if !_is_zero($c,$x1);
1472 _add($c,$x, _mul($c, $y1, $m) ) if !_is_zero($c,$y1);
1479 # convert a decimal number to hex (ref to array, return ref to string)
1482 my $x1 = _copy($c,$x);
1486 my $x10000 = [ 0x10000 ];
1487 while (! _is_zero($c,$x1))
1489 ($x1, $xr) = _div($c,$x1,$x10000);
1490 $es .= unpack('h4',pack('v',$xr->[0]));
1493 $es =~ s/^[0]+//; # strip leading zeros
1500 # convert a decimal number to bin (ref to array, return ref to string)
1503 my $x1 = _copy($c,$x);
1507 my $x10000 = [ 0x10000 ];
1508 while (! _is_zero($c,$x1))
1510 ($x1, $xr) = _div($c,$x1,$x10000);
1511 $es .= unpack('b16',pack('v',$xr->[0]));
1514 $es =~ s/^[0]+//; # strip leading zeros
1521 # convert a hex number to decimal (ref to string, return ref to array)
1525 my $m = [ 0x10000 ]; # 16 bit at a time
1528 my $len = length($$hs)-2;
1529 $len = int($len/4); # 4-digit parts, w/o '0x'
1530 my $val; my $i = -4;
1533 $val = substr($$hs,$i,4);
1534 $val =~ s/^[+-]?0x// if $len == 0; # for last part only because
1535 $val = hex($val); # hex does not like wrong chars
1537 _add ($c, $x, _mul ($c, [ $val ], $mul ) ) if $val != 0;
1538 _mul ($c, $mul, $m ) if $len >= 0; # skip last mul
1545 # convert a hex number to decimal (ref to string, return ref to array)
1548 # instead of converting 8 bit at a time, it is faster to convert the
1549 # number to hex, and then call _from_hex.
1552 $hs =~ s/^[+-]?0b//; # remove sign and 0b
1553 my $l = length($hs); # bits
1554 $hs = '0' x (8-($l % 8)) . $hs if ($l % 8) != 0; # padd left side w/ 0
1555 my $h = unpack('H*', pack ('B*', $hs)); # repack as hex
1556 return $c->_from_hex(\('0x'.$h));
1559 my $m = [ 0x100 ]; # 8 bit at a time
1562 my $len = length($$bs)-2;
1563 $len = int($len/8); # 4-digit parts, w/o '0x'
1564 my $val; my $i = -8;
1567 $val = substr($$bs,$i,8);
1568 $val =~ s/^[+-]?0b// if $len == 0; # for last part only
1570 $val = ord(pack('B8',substr('00000000'.$val,-8,8)));
1573 _add ($c, $x, _mul ($c, [ $val ], $mul ) ) if $val != 0;
1574 _mul ($c, $mul, $m ) if $len >= 0; # skip last mul
1586 # modulus of power ($x ** $y) % $z
1589 ##############################################################################
1590 ##############################################################################
1597 Math::BigInt::Calc - Pure Perl module to support Math::BigInt
1601 Provides support for big integer calculations. Not intended to be used by other
1602 modules (except Math::BigInt::Cached). Other modules which sport the same
1603 functions can also be used to support Math::Bigint, like Math::BigInt::Pari.
1607 In order to allow for multiple big integer libraries, Math::BigInt was
1608 rewritten to use library modules for core math routines. Any module which
1609 follows the same API as this can be used instead by using the following:
1611 use Math::BigInt lib => 'libname';
1613 'libname' is either the long name ('Math::BigInt::Pari'), or only the short
1614 version like 'Pari'.
1618 The following functions MUST be defined in order to support the use by
1621 _new(string) return ref to new object from ref to decimal string
1622 _zero() return a new object with value 0
1623 _one() return a new object with value 1
1625 _str(obj) return ref to a string representing the object
1626 _num(obj) returns a Perl integer/floating point number
1627 NOTE: because of Perl numeric notation defaults,
1628 the _num'ified obj may lose accuracy due to
1629 machine-dependend floating point size limitations
1631 _add(obj,obj) Simple addition of two objects
1632 _mul(obj,obj) Multiplication of two objects
1633 _div(obj,obj) Division of the 1st object by the 2nd
1634 In list context, returns (result,remainder).
1635 NOTE: this is integer math, so no
1636 fractional part will be returned.
1637 _sub(obj,obj) Simple subtraction of 1 object from another
1638 a third, optional parameter indicates that the params
1639 are swapped. In this case, the first param needs to
1640 be preserved, while you can destroy the second.
1641 sub (x,y,1) => return x - y and keep x intact!
1642 _dec(obj) decrement object by one (input is garant. to be > 0)
1643 _inc(obj) increment object by one
1646 _acmp(obj,obj) <=> operator for objects (return -1, 0 or 1)
1648 _len(obj) returns count of the decimal digits of the object
1649 _digit(obj,n) returns the n'th decimal digit of object
1651 _is_one(obj) return true if argument is +1
1652 _is_zero(obj) return true if argument is 0
1653 _is_even(obj) return true if argument is even (0,2,4,6..)
1654 _is_odd(obj) return true if argument is odd (1,3,5,7..)
1656 _copy return a ref to a true copy of the object
1658 _check(obj) check whether internal representation is still intact
1659 return 0 for ok, otherwise error message as string
1661 The following functions are optional, and can be defined if the underlying lib
1662 has a fast way to do them. If undefined, Math::BigInt will use pure Perl (hence
1663 slow) fallback routines to emulate these:
1665 _from_hex(str) return ref to new object from ref to hexadecimal string
1666 _from_bin(str) return ref to new object from ref to binary string
1668 _as_hex(str) return ref to scalar string containing the value as
1669 unsigned hex string, with the '0x' prepended.
1670 Leading zeros must be stripped.
1671 _as_bin(str) Like as_hex, only as binary string containing only
1672 zeros and ones. Leading zeros must be stripped and a
1673 '0b' must be prepended.
1675 _rsft(obj,N,B) shift object in base B by N 'digits' right
1676 For unsupported bases B, return undef to signal failure
1677 _lsft(obj,N,B) shift object in base B by N 'digits' left
1678 For unsupported bases B, return undef to signal failure
1680 _xor(obj1,obj2) XOR (bit-wise) object 1 with object 2
1681 Note: XOR, AND and OR pad with zeros if size mismatches
1682 _and(obj1,obj2) AND (bit-wise) object 1 with object 2
1683 _or(obj1,obj2) OR (bit-wise) object 1 with object 2
1685 _mod(obj,obj) Return remainder of div of the 1st by the 2nd object
1686 _sqrt(obj) return the square root of object (truncate to int)
1687 _fac(obj) return factorial of object 1 (1*2*3*4..)
1688 _pow(obj,obj) return object 1 to the power of object 2
1689 _gcd(obj,obj) return Greatest Common Divisor of two objects
1691 _zeros(obj) return number of trailing decimal zeros
1692 _modinv return inverse modulus
1693 _modpow return modulus of power ($x ** $y) % $z
1695 Input strings come in as unsigned but with prefix (i.e. as '123', '0xabc'
1698 Testing of input parameter validity is done by the caller, so you need not
1699 worry about underflow (f.i. in C<_sub()>, C<_dec()>) nor about division by
1700 zero or similar cases.
1702 The first parameter can be modified, that includes the possibility that you
1703 return a reference to a completely different object instead. Although keeping
1704 the reference and just changing it's contents is prefered over creating and
1705 returning a different reference.
1707 Return values are always references to objects or strings. Exceptions are
1708 C<_lsft()> and C<_rsft()>, which return undef if they can not shift the
1709 argument. This is used to delegate shifting of bases different than the one
1710 you can support back to Math::BigInt, which will use some generic code to
1711 calculate the result.
1713 =head1 WRAP YOUR OWN
1715 If you want to port your own favourite c-lib for big numbers to the
1716 Math::BigInt interface, you can take any of the already existing modules as
1717 a rough guideline. You should really wrap up the latest BigInt and BigFloat
1718 testsuites with your module, and replace in them any of the following:
1724 use Math::BigInt lib => 'yourlib';
1726 This way you ensure that your library really works 100% within Math::BigInt.
1730 This program is free software; you may redistribute it and/or modify it under
1731 the same terms as Perl itself.
1735 Original math code by Mark Biggar, rewritten by Tels L<http://bloodgate.com/>
1737 Seperated from BigInt and shaped API with the help of John Peacock.
1741 L<Math::BigInt>, L<Math::BigFloat>, L<Math::BigInt::BitVect>,
1742 L<Math::BigInt::GMP>, L<Math::BigInt::Cached> and L<Math::BigInt::Pari>.