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 = 5 if $] < 5.006; # cap, for older Perls
112 $e = 7 if $e > 7; # cap, for VMS, OS/390 and other 64 bit systems
113 # 8 fails inside random testsuite, so take 7
115 # determine how many digits fit into an integer and can be safely added
116 # together plus carry w/o causing an overflow
118 # this below detects 15 on a 64 bit system, because after that it becomes
119 # 1e16 and not 1000000 :/ I can make it detect 18, but then I get a lot of
120 # test failures. Ugh! (Tomake detect 18: uncomment lines marked with *)
122 my $bi = 5; # approx. 16 bit
123 $num = int('9' x $bi);
125 # while ( ($num+$num+1) eq '1' . '9' x $bi) # *
126 while ( int($num+$num+1) eq '1' . '9' x $bi)
128 $bi++; $num = int('9' x $bi);
129 # $bi++; $num *= 10; $num += 9; # *
131 $bi--; # back off one step
132 # by setting them equal, we ignore the findings and use the default
133 # one-size-fits-all approach from former versions
134 $bi = $e; # XXX, this should work always
136 __PACKAGE__->_base_len($e,$bi); # set and store
138 # find out how many bits _and, _or and _xor can take (old default = 16)
139 # I don't think anybody has yet 128 bit scalars, so let's play safe.
140 local $^W = 0; # don't warn about 'nonportable number'
141 $AND_BITS = 15; $XOR_BITS = 15; $OR_BITS = 15;
143 # find max bits, we will not go higher than numberofbits that fit into $BASE
144 # to make _and etc simpler (and faster for smaller, slower for large numbers)
146 while (2 ** $max < $BASE) { $max++; }
150 $x = oct('0b' . '1' x $AND_BITS); $y = $x & $x;
151 $z = (2 ** $AND_BITS) - 1;
152 } while ($AND_BITS < $max && $x == $z && $y == $x);
153 $AND_BITS --; # retreat one step
156 $x = oct('0b' . '1' x $XOR_BITS); $y = $x ^ 0;
157 $z = (2 ** $XOR_BITS) - 1;
158 } while ($XOR_BITS < $max && $x == $z && $y == $x);
159 $XOR_BITS --; # retreat one step
162 $x = oct('0b' . '1' x $OR_BITS); $y = $x | $x;
163 $z = (2 ** $OR_BITS) - 1;
164 } while ($OR_BITS < $max && $x == $z && $y == $x);
165 $OR_BITS --; # retreat one step
169 ##############################################################################
170 # convert between the "small" and the "large" representation
174 # take an array in base $BASE_LEN_SMALL and convert it in-place to $BASE_LEN
177 # print "_to_large $BASE_LEN_SMALL => $BASE_LEN\n";
179 return $x if $LEN_CONVERT == 0 || # nothing to converconvertor
180 @$x == 1; # only one element => early out
182 # 12345 67890 12345 67890 contents
184 # 123456 7890123 4567890 contents
187 # my @d; my $str = '';
188 # my $z = '0' x $BASE_LEN_SMALL;
191 # # ... . 04321 . 000321
192 # $str = substr($z.$_,-$BASE_LEN_SMALL,$BASE_LEN_SMALL) . $str;
193 # if (length($str) > $BASE_LEN)
195 # push @d, substr($str,-$BASE_LEN,$BASE_LEN); # extract one piece
196 # substr($str,-$BASE_LEN,$BASE_LEN) = ''; # remove it
199 # push @d, $str if $str !~ /^0*$/; # extract last piece
201 # $x->[-1] = int($x->[-1]); # strip leading zero
205 my $l = scalar @$x; # number of parts
206 $l --; $ret .= int($x->[$l]); $l--;
207 my $z = '0' x ($BASE_LEN_SMALL-1);
210 $ret .= substr($z.$x->[$l],-$BASE_LEN_SMALL);
213 my $str = _new($c,\$ret); # make array
214 @$x = @$str; # clobber contents of $x
215 $x->[-1] = int($x->[-1]); # strip leading zero
220 # take an array in base $BASE_LEN and convert it in-place to $BASE_LEN_SMALL
223 return $x if $LEN_CONVERT == 0; # nothing to do
224 return $x if @$x == 1 && length(int($x->[0])) <= $BASE_LEN_SMALL;
227 my $il = length($$d)-1;
228 ## this leaves '00000' instead of int 0 and will be corrected after any op
229 # clobber contents of $x
230 @$x = reverse(unpack("a" . ($il % $BASE_LEN_SMALL+1)
231 . ("a$BASE_LEN_SMALL" x ($il / $BASE_LEN_SMALL)), $$d));
233 $x->[-1] = int($x->[-1]); # strip leading zero
236 ###############################################################################
240 # (ref to string) return ref to num_array
241 # Convert a number from string format (without sign) to internal base
242 # 1ex format. Assumes normalized value as input.
244 my $il = length($$d)-1;
245 # this leaves '00000' instead of int 0 and will be corrected after any op
246 [ reverse(unpack("a" . ($il % $BASE_LEN+1)
247 . ("a$BASE_LEN" x ($il / $BASE_LEN)), $$d)) ];
252 $AND_MASK = __PACKAGE__->_new( \( 2 ** $AND_BITS ));
253 $XOR_MASK = __PACKAGE__->_new( \( 2 ** $XOR_BITS ));
254 $OR_MASK = __PACKAGE__->_new( \( 2 ** $OR_BITS ));
271 # create a two (for _pow)
280 # catch and throw away
283 ##############################################################################
284 # convert back to string and number
288 # (ref to BINT) return num_str
289 # Convert number from internal base 100000 format to string format.
290 # internal format is always normalized (no leading zeros, "-0" => "+0")
294 my $l = scalar @$ar; # number of parts
295 return $nan if $l < 1; # should not happen
297 # handle first one different to strip leading zeros from it (there are no
298 # leading zero parts in internal representation)
299 $l --; $ret .= int($ar->[$l]); $l--;
300 # Interestingly, the pre-padd method uses more time
301 # the old grep variant takes longer (14 to 10 sec)
302 my $z = '0' x ($BASE_LEN-1);
305 $ret .= substr($z.$ar->[$l],-$BASE_LEN); # fastest way I could think of
313 # Make a number (scalar int/float) from a BigInt object
315 return $x->[0] if scalar @$x == 1; # below $BASE
320 $num += $fac*$_; $fac *= $BASE;
325 ##############################################################################
330 # (ref to int_num_array, ref to int_num_array)
331 # routine to add two base 1eX numbers
332 # stolen from Knuth Vol 2 Algorithm A pg 231
333 # there are separate routines to add and sub as per Knuth pg 233
334 # This routine clobbers up array x, but not y.
338 return $x if (@$y == 1) && $y->[0] == 0; # $x + 0 => $x
339 if ((@$x == 1) && $x->[0] == 0) # 0 + $y => $y->copy
341 # twice as slow as $x = [ @$y ], but necc. to retain $x as ref :(
342 @$x = @$y; return $x;
345 # for each in Y, add Y to X and carry. If after that, something is left in
346 # X, foreach in X add carry to X and then return X, carry
347 # Trades one "$j++" for having to shift arrays, $j could be made integer
348 # but this would impose a limit to number-length of 2**32.
349 my $i; my $car = 0; my $j = 0;
352 $x->[$j] -= $BASE if $car = (($x->[$j] += $i + $car) >= $BASE) ? 1 : 0;
357 $x->[$j] -= $BASE if $car = (($x->[$j] += $car) >= $BASE) ? 1 : 0; $j++;
364 # (ref to int_num_array, ref to int_num_array)
365 # routine to add 1 to a base 1eX numbers
366 # This routine clobbers up array x, but not y.
371 return $x if (($i += 1) < $BASE); # early out
372 $i = 0; # overflow, next
374 push @$x,1 if ($x->[-1] == 0); # last overflowed, so extend
380 # (ref to int_num_array, ref to int_num_array)
381 # routine to add 1 to a base 1eX numbers
382 # This routine clobbers up array x, but not y.
385 my $MAX = $BASE-1; # since MAX_VAL based on MBASE
388 last if (($i -= 1) >= 0); # early out
389 $i = $MAX; # overflow, next
391 pop @$x if $x->[-1] == 0 && @$x > 1; # last overflowed (but leave 0)
397 # (ref to int_num_array, ref to int_num_array, swap)
398 # subtract base 1eX numbers -- stolen from Knuth Vol 2 pg 232, $x > $y
399 # subtract Y from X by modifying x in place
400 my ($c,$sx,$sy,$s) = @_;
402 my $car = 0; my $i; my $j = 0;
408 last unless defined $sy->[$j] || $car;
409 $i += $BASE if $car = (($i -= ($sy->[$j] || 0) + $car) < 0); $j++;
411 # might leave leading zeros, so fix that
412 return __strip_zeros($sx);
414 #print "case 1 (swap)\n";
417 # we can't do an early out if $x is < than $y, since we
418 # need to copy the high chunks from $y. Found by Bob Mathews.
419 #last unless defined $sy->[$j] || $car;
421 if $car = (($sy->[$j] = $i-($sy->[$j]||0) - $car) < 0);
424 # might leave leading zeros, so fix that
430 # compute $x ** 2 or $x * $x in-place and return $x
433 # From: Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and
434 # S. Vanstone., Chapter 14
436 #14.16 Algorithm Multiple-precision squaring
437 #INPUT: positive integer x = (xt 1 xt 2 ... x1 x0)b.
438 #OUTPUT: x * x = x ** 2 in radix b representation.
439 #1. For i from 0 to (2t - 1) do: wi <- 0.
440 #2. For i from 0 to (t - 1) do the following:
441 # 2.1 (uv)b w2i + xi * xi, w2i v, c u.
442 # 2.2 For j from (i + 1)to (t - 1) do the following:
443 # (uv)b <- wi+j + 2*xj * xi + c, wi+j <- v, c <- u.
445 #3. Return((w2t-1 w2t-2 ... w1 w0)b).
447 # # Note: That description is crap. Half of the symbols are not explained or
448 # # used with out beeing set.
449 # my $t = scalar @$x; # count
451 # for ($i = 0; $i < $t; $i++)
453 # $x->[$i] = $x->[$i*2] + $x[$i]*$x[$i];
454 # $x->[$i*2] = $x[$i]; $c = $x[$i];
455 # for ($j = $i+1; $j < $t; $j++)
457 # $x->[$i] = $x->[$i+$j] + 2 * $x->[$i] * $x->[$j];
458 # $x->[$i+$j] = $x[$j]; $c = $x[$i];
460 # $x->[$i+$t] = $x[$i];
467 # (ref to int_num_array, ref to int_num_array)
468 # multiply two numbers in internal representation
469 # modifies first arg, second need not be different from first
470 my ($c,$xv,$yv) = @_;
472 # shortcut for two very short numbers (improved by Nathan Zook)
473 # works also if xv and yv are the same reference
474 if ((@$xv == 1) && (@$yv == 1))
476 if (($xv->[0] *= $yv->[0]) >= $MBASE)
478 $xv->[0] = $xv->[0] - ($xv->[1] = int($xv->[0] * $RBASE)) * $MBASE;
482 # shortcut for result == 0
483 if ( ((@$xv == 1) && ($xv->[0] == 0)) ||
484 ((@$yv == 1) && ($yv->[0] == 0)) )
490 # since multiplying $x with $x fails, make copy in this case
491 $yv = [@$xv] if $xv == $yv; # same references?
492 # $yv = [@$xv] if "$xv" eq "$yv"; # same references?
494 # since multiplying $x with $x would fail here, use the faster squaring
495 # return _square($c,$xv) if $xv == $yv; # same reference?
497 if ($LEN_CONVERT != 0)
499 $c->_to_small($xv); $c->_to_small($yv);
502 my @prod = (); my ($prod,$car,$cty,$xi,$yi);
511 # $prod = $xi * $yi + ($prod[$cty] || 0) + $car;
513 # $prod - ($car = int($prod * RBASE)) * $MBASE; # see USE_MUL
515 # $prod[$cty] += $car if $car; # need really to check for 0?
519 # looping through this if $xi == 0 is silly - so optimize it away!
520 $xi = (shift @prod || 0), next if $xi == 0;
523 $prod = $xi * $yi + ($prod[$cty] || 0) + $car;
524 ## this is actually a tad slower
525 ## $prod = $prod[$cty]; $prod += ($car + $xi * $yi); # no ||0 here
527 $prod - ($car = int($prod * $RBASE)) * $MBASE; # see USE_MUL
529 $prod[$cty] += $car if $car; # need really to check for 0?
530 $xi = shift @prod || 0; # || 0 makes v5.005_3 happy
533 if ($LEN_CONVERT != 0)
547 # (ref to int_num_array, ref to int_num_array)
548 # multiply two numbers in internal representation
549 # modifies first arg, second need not be different from first
550 my ($c,$xv,$yv) = @_;
552 # shortcut for two very short numbers (improved by Nathan Zook)
553 # works also if xv and yv are the same reference
554 if ((@$xv == 1) && (@$yv == 1))
556 if (($xv->[0] *= $yv->[0]) >= $MBASE)
559 $xv->[0] - ($xv->[1] = int($xv->[0] / $MBASE)) * $MBASE;
563 # shortcut for result == 0
564 if ( ((@$xv == 1) && ($xv->[0] == 0)) ||
565 ((@$yv == 1) && ($yv->[0] == 0)) )
572 # since multiplying $x with $x fails, make copy in this case
573 $yv = [@$xv] if $xv == $yv; # same references?
574 # $yv = [@$xv] if "$xv" eq "$yv"; # same references?
575 # since multiplying $x with $x would fail here, use the faster squaring
576 # return _square($c,$xv) if $xv == $yv; # same reference?
578 if ($LEN_CONVERT != 0)
580 $c->_to_small($xv); $c->_to_small($yv);
583 my @prod = (); my ($prod,$car,$cty,$xi,$yi);
587 # looping through this if $xi == 0 is silly - so optimize it away!
588 $xi = (shift @prod || 0), next if $xi == 0;
591 $prod = $xi * $yi + ($prod[$cty] || 0) + $car;
593 $prod - ($car = int($prod / $MBASE)) * $MBASE;
595 $prod[$cty] += $car if $car; # need really to check for 0?
596 $xi = shift @prod || 0; # || 0 makes v5.005_3 happy
599 if ($LEN_CONVERT != 0)
613 # ref to array, ref to array, modify first array and return remainder if
615 my ($c,$x,$yorg) = @_;
617 if (@$x == 1 && @$yorg == 1)
619 # shortcut, $yorg and $x are two small numbers
622 my $r = [ $x->[0] % $yorg->[0] ];
623 $x->[0] = int($x->[0] / $yorg->[0]);
628 $x->[0] = int($x->[0] / $yorg->[0]);
635 $rem = _mod($c,[ @$x ],$yorg) if wantarray;
637 # shortcut, $y is < $BASE
638 my $j = scalar @$x; my $r = 0;
639 my $y = $yorg->[0]; my $b;
642 $b = $r * $MBASE + $x->[$j];
643 $x->[$j] = int($b/$y);
646 pop @$x if @$x > 1 && $x->[-1] == 0; # splice up a leading zero
647 return ($x,$rem) if wantarray;
651 my $y = [ @$yorg ]; # always make copy to preserve
652 if ($LEN_CONVERT != 0)
654 $c->_to_small($x); $c->_to_small($y);
657 my ($car,$bar,$prd,$dd,$xi,$yi,@q,$v2,$v1,@d,$tmp,$q,$u2,$u1,$u0);
659 $car = $bar = $prd = 0;
660 if (($dd = int($MBASE/($y->[-1]+1))) != 1)
664 $xi = $xi * $dd + $car;
665 $xi -= ($car = int($xi * $RBASE)) * $MBASE; # see USE_MUL
667 push(@$x, $car); $car = 0;
670 $yi = $yi * $dd + $car;
671 $yi -= ($car = int($yi * $RBASE)) * $MBASE; # see USE_MUL
678 @q = (); ($v2,$v1) = @$y[-2,-1];
682 ($u2,$u1,$u0) = @$x[-3..-1];
684 #warn "oups v1 is 0, u0: $u0 $y->[-2] $y->[-1] l ",scalar @$y,"\n"
686 $q = (($u0 == $v1) ? $MAX_VAL : int(($u0*$MBASE+$u1)/$v1));
687 --$q while ($v2*$q > ($u0*$MBASE+$u1-$q*$v1)*$MBASE+$u2);
690 ($car, $bar) = (0,0);
691 for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
693 $prd = $q * $y->[$yi] + $car;
694 $prd -= ($car = int($prd * $RBASE)) * $MBASE; # see USE_MUL
695 $x->[$xi] += $MBASE if ($bar = (($x->[$xi] -= $prd + $bar) < 0));
697 if ($x->[-1] < $car + $bar)
700 for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
703 if ($car = (($x->[$xi] += $y->[$yi] + $car) > $MBASE));
707 pop(@$x); unshift(@q, $q);
715 for $xi (reverse @$x)
717 $prd = $car * $MBASE + $xi;
718 $car = $prd - ($tmp = int($prd / $dd)) * $dd; # see USE_MUL
728 if ($LEN_CONVERT != 0)
730 $c->_to_large($x); $c->_to_large($d);
740 if ($LEN_CONVERT != 0)
753 # ref to array, ref to array, modify first array and return remainder if
755 my ($c,$x,$yorg) = @_;
757 if (@$x == 1 && @$yorg == 1)
759 # shortcut, $yorg and $x are two small numbers
762 my $r = [ $x->[0] % $yorg->[0] ];
763 $x->[0] = int($x->[0] / $yorg->[0]);
768 $x->[0] = int($x->[0] / $yorg->[0]);
775 $rem = _mod($c,[ @$x ],$yorg) if wantarray;
777 # shortcut, $y is < $BASE
778 my $j = scalar @$x; my $r = 0;
779 my $y = $yorg->[0]; my $b;
782 $b = $r * $MBASE + $x->[$j];
783 $x->[$j] = int($b/$y);
786 pop @$x if @$x > 1 && $x->[-1] == 0; # splice up a leading zero
787 return ($x,$rem) if wantarray;
791 my $y = [ @$yorg ]; # always make copy to preserve
792 if ($LEN_CONVERT != 0)
794 $c->_to_small($x); $c->_to_small($y);
797 my ($car,$bar,$prd,$dd,$xi,$yi,@q,$v2,$v1,@d,$tmp,$q,$u2,$u1,$u0);
799 $car = $bar = $prd = 0;
800 if (($dd = int($MBASE/($y->[-1]+1))) != 1)
804 $xi = $xi * $dd + $car;
805 $xi -= ($car = int($xi / $MBASE)) * $MBASE;
807 push(@$x, $car); $car = 0;
810 $yi = $yi * $dd + $car;
811 $yi -= ($car = int($yi / $MBASE)) * $MBASE;
818 @q = (); ($v2,$v1) = @$y[-2,-1];
822 ($u2,$u1,$u0) = @$x[-3..-1];
824 #warn "oups v1 is 0, u0: $u0 $y->[-2] $y->[-1] l ",scalar @$y,"\n"
826 $q = (($u0 == $v1) ? $MAX_VAL : int(($u0*$MBASE+$u1)/$v1));
827 --$q while ($v2*$q > ($u0*$MBASE+$u1-$q*$v1)*$MBASE+$u2);
830 ($car, $bar) = (0,0);
831 for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
833 $prd = $q * $y->[$yi] + $car;
834 $prd -= ($car = int($prd / $MBASE)) * $MBASE;
835 $x->[$xi] += $MBASE if ($bar = (($x->[$xi] -= $prd + $bar) < 0));
837 if ($x->[-1] < $car + $bar)
840 for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
843 if ($car = (($x->[$xi] += $y->[$yi] + $car) > $MBASE));
847 pop(@$x); unshift(@q, $q);
855 for $xi (reverse @$x)
857 $prd = $car * $MBASE + $xi;
858 $car = $prd - ($tmp = int($prd / $dd)) * $dd;
868 if ($LEN_CONVERT != 0)
870 $c->_to_large($x); $c->_to_large($d);
880 if ($LEN_CONVERT != 0)
891 ##############################################################################
896 # internal absolute post-normalized compare (ignore signs)
897 # ref to array, ref to array, return <0, 0, >0
898 # arrays must have at least one entry; this is not checked for
900 my ($c,$cx,$cy) = @_;
902 # fast comp based on array elements
903 my $lxy = scalar @$cx - scalar @$cy;
904 return -1 if $lxy < 0; # already differs, ret
905 return 1 if $lxy > 0; # ditto
907 # now calculate length based on digits, not parts
908 $lxy = _len($c,$cx) - _len($c,$cy); # difference
909 return -1 if $lxy < 0;
910 return 1 if $lxy > 0;
912 # hm, same lengths, but same contents?
914 # first way takes 5.49 sec instead of 4.87, but has the early out advantage
915 # so grep is slightly faster, but more inflexible. hm. $_ instead of $k
916 # yields 5.6 instead of 5.5 sec huh?
917 # manual way (abort if unequal, good for early ne)
918 my $j = scalar @$cx - 1;
921 last if ($a = $cx->[$j] - $cy->[$j]); $j--;
923 # my $j = scalar @$cx;
926 # last if ($a = $cx->[$j] - $cy->[$j]);
932 # while it early aborts, it is even slower than the manual variant
933 #grep { return $a if ($a = $_ - $cy->[$i++]); } @$cx;
934 # grep way, go trough all (bad for early ne)
935 #grep { $a = $_ - $cy->[$i++]; } @$cx;
941 # compute number of digits in bigint, minus the sign
943 # int() because add/sub sometimes leaves strings (like '00005') instead of
944 # '5' in this place, thus causing length() to report wrong length
947 return (@$cx-1)*$BASE_LEN+length(int($cx->[-1]));
952 # return the nth digit, negative values count backward
953 # zero is rightmost, so _digit(123,0) will give 3
956 my $len = _len('',$x);
958 $n = $len+$n if $n < 0; # -1 last, -2 second-to-last
959 $n = abs($n); # if negative was too big
960 $len--; $n = $len if $n > $len; # n to big?
962 my $elem = int($n / $BASE_LEN); # which array element
963 my $digit = $n % $BASE_LEN; # which digit in this element
964 $elem = '0000'.@$x[$elem]; # get element padded with 0's
965 return substr($elem,-$digit-1,1);
970 # return amount of trailing zeros in decimal
971 # check each array elem in _m for having 0 at end as long as elem == 0
972 # Upon finding a elem != 0, stop
974 my $zeros = 0; my $elem;
979 $elem = "$e"; # preserve x
980 $elem =~ s/.*?(0*$)/$1/; # strip anything not zero
981 $zeros *= $BASE_LEN; # elems * 5
982 $zeros += length($elem); # count trailing zeros
985 $zeros ++; # real else branch: 50% slower!
990 ##############################################################################
995 # return true if arg (BINT or num_str) is zero (array '+', '0')
998 (((scalar @$x == 1) && ($x->[0] == 0))) <=> 0;
1003 # return true if arg (BINT or num_str) is even
1005 (!($x->[0] & 1)) <=> 0;
1010 # return true if arg (BINT or num_str) is even
1013 (($x->[0] & 1)) <=> 0;
1018 # return true if arg (BINT or num_str) is one (array '+', '1')
1021 (scalar @$x == 1) && ($x->[0] == 1) <=> 0;
1026 # internal normalization function that strips leading zeros from the array
1027 # args: ref to array
1030 my $cnt = scalar @$s; # get count of parts
1032 push @$s,0 if $i < 0; # div might return empty results, so fix it
1034 return $s if @$s == 1; # early out
1036 #print "strip: cnt $cnt i $i\n";
1037 # '0', '3', '4', '0', '0',
1042 # => fcnt = cnt - i (5-2 => 3, cnt => 5-1 = 4, throw away from 4th pos)
1043 # >= 1: skip first part (this can be zero)
1044 while ($i > 0) { last if $s->[$i] != 0; $i--; }
1045 $i++; splice @$s,$i if ($i < $cnt); # $i cant be 0
1049 ###############################################################################
1050 # check routine to test internal state of corruptions
1054 # used by the test suite
1057 return "$x is not a reference" if !ref($x);
1059 # are all parts are valid?
1060 my $i = 0; my $j = scalar @$x; my ($e,$try);
1063 $e = $x->[$i]; $e = 'undef' unless defined $e;
1064 $try = '=~ /^[\+]?[0-9]+\$/; '."($x, $e)";
1065 last if $e !~ /^[+]?[0-9]+$/;
1066 $try = '=~ /^[\+]?[0-9]+\$/; '."($x, $e) (stringify)";
1067 last if "$e" !~ /^[+]?[0-9]+$/;
1068 $try = '=~ /^[\+]?[0-9]+\$/; '."($x, $e) (cat-stringify)";
1069 last if '' . "$e" !~ /^[+]?[0-9]+$/;
1070 $try = ' < 0 || >= $BASE; '."($x, $e)";
1071 last if $e <0 || $e >= $BASE;
1072 # this test is disabled, since new/bnorm and certain ops (like early out
1073 # in add/sub) are allowed/expected to leave '00000' in some elements
1074 #$try = '=~ /^00+/; '."($x, $e)";
1075 #last if $e =~ /^00+/;
1078 return "Illegal part '$e' at pos $i (tested: $try)" if $i < $j;
1083 ###############################################################################
1084 ###############################################################################
1085 # some optional routines to make BigInt faster
1089 # if possible, use mod shortcut
1090 my ($c,$x,$yo) = @_;
1092 # slow way since $y to big
1093 if (scalar @$yo > 1)
1095 my ($xo,$rem) = _div($c,$x,$yo);
1099 # both are single element arrays
1100 if (scalar @$x == 1)
1106 # @y is single element, but @x has more than one
1110 # when BASE % Y == 0 then (B * BASE) % Y == 0
1111 # (B * BASE) % $y + A % Y => A % Y
1112 # so need to consider only last element: O(1)
1117 # else need to go trough all elements: O(N), but loop is a bit simplified
1121 $r = ($r + $_) % $y; # not much faster, but heh...
1122 #$r += $_ % $y; $r %= $y;
1129 # else need to go trough all elements: O(N)
1130 my $r = 0; my $bm = 1;
1133 $r = ($_ * $bm + $r) % $y;
1134 $bm = ($bm * $b) % $y;
1136 #$r += ($_ % $y) * $bm;
1148 ##############################################################################
1153 my ($c,$x,$y,$n) = @_;
1157 $n = _new($c,\$n); return _div($c,$x, _pow($c,$n,$y));
1160 # shortcut (faster) for shifting by 10)
1161 # multiples of $BASE_LEN
1162 my $dst = 0; # destination
1163 my $src = _num($c,$y); # as normal int
1164 my $rem = $src % $BASE_LEN; # remainder to shift
1165 $src = int($src / $BASE_LEN); # source
1168 splice (@$x,0,$src); # even faster, 38.4 => 39.3
1172 my $len = scalar @$x - $src; # elems to go
1173 my $vd; my $z = '0'x $BASE_LEN;
1174 $x->[scalar @$x] = 0; # avoid || 0 test inside loop
1177 $vd = $z.$x->[$src];
1178 $vd = substr($vd,-$BASE_LEN,$BASE_LEN-$rem);
1180 $vd = substr($z.$x->[$src],-$rem,$rem) . $vd;
1181 $vd = substr($vd,-$BASE_LEN,$BASE_LEN) if length($vd) > $BASE_LEN;
1182 $x->[$dst] = int($vd);
1185 splice (@$x,$dst) if $dst > 0; # kill left-over array elems
1186 pop @$x if $x->[-1] == 0 && @$x > 1; # kill last element if 0
1193 my ($c,$x,$y,$n) = @_;
1197 $n = _new($c,\$n); return _mul($c,$x, _pow($c,$n,$y));
1200 # shortcut (faster) for shifting by 10) since we are in base 10eX
1201 # multiples of $BASE_LEN:
1202 my $src = scalar @$x; # source
1203 my $len = _num($c,$y); # shift-len as normal int
1204 my $rem = $len % $BASE_LEN; # remainder to shift
1205 my $dst = $src + int($len/$BASE_LEN); # destination
1206 my $vd; # further speedup
1207 $x->[$src] = 0; # avoid first ||0 for speed
1208 my $z = '0' x $BASE_LEN;
1211 $vd = $x->[$src]; $vd = $z.$vd;
1212 $vd = substr($vd,-$BASE_LEN+$rem,$BASE_LEN-$rem);
1213 $vd .= $src > 0 ? substr($z.$x->[$src-1],-$BASE_LEN,$rem) : '0' x $rem;
1214 $vd = substr($vd,-$BASE_LEN,$BASE_LEN) if length($vd) > $BASE_LEN;
1215 $x->[$dst] = int($vd);
1218 # set lowest parts to 0
1219 while ($dst >= 0) { $x->[$dst--] = 0; }
1220 # fix spurios last zero element
1221 splice @$x,-1 if $x->[-1] == 0;
1228 # ref to array, ref to array, return ref to array
1229 my ($c,$cx,$cy) = @_;
1233 my $y1 = _copy($c,$cy);
1234 while (!_is_one($c,$y1))
1236 _mul($c,$pow2,$cx) if _is_odd($c,$y1);
1240 _mul($c,$cx,$pow2) unless _is_one($c,$pow2);
1247 # ref to array, return ref to array
1250 if ((@$cx == 1) && ($cx->[0] <= 2))
1252 $cx->[0] = 1 * ($cx->[0]||1); # 0,1 => 1, 2 => 2
1256 # go forward until $base is exceeded
1257 # limit is either $x or $base (x == 100 means as result too high)
1258 my $steps = 100; $steps = $cx->[0] if @$cx == 1;
1259 my $r = 2; my $cf = 3; my $step = 1; my $last = $r;
1260 while ($r < $BASE && $step < $steps)
1262 $last = $r; $r *= $cf++; $step++;
1264 if ((@$cx == 1) && ($step == $cx->[0]))
1270 my $n = _copy($c,$cx);
1274 while (!(@$n == 1 && $n->[0] == $step))
1276 _mul($c,$cx,$n); _dec($c,$n);
1281 use constant DEBUG => 0;
1285 sub steps { $steps };
1290 # ref to array, return ref to array
1293 if (scalar @$x == 1)
1295 # fit's into one Perl scalar
1296 $x->[0] = int(sqrt($x->[0]));
1299 my $y = _copy($c,$x);
1300 # hopefully _len/2 is < $BASE, the -1 is to always undershot the guess
1301 # since our guess will "grow"
1302 my $l = int((_len($c,$x)-1) / 2);
1304 my $lastelem = $x->[-1]; # for guess
1305 my $elems = scalar @$x - 1;
1306 # not enough digits, but could have more?
1307 if ((length($lastelem) <= 3) && ($elems > 1))
1309 # right-align with zero pad
1310 my $len = length($lastelem) & 1;
1311 print "$lastelem => " if DEBUG;
1312 $lastelem .= substr($x->[-2] . '0' x $BASE_LEN,0,$BASE_LEN);
1313 # former odd => make odd again, or former even to even again
1314 $lastelem = $lastelem / 10 if (length($lastelem) & 1) != $len;
1315 print "$lastelem\n" if DEBUG;
1318 # construct $x (instead of _lsft($c,$x,$l,10)
1319 my $r = $l % $BASE_LEN; # 10000 00000 00000 00000 ($BASE_LEN=5)
1320 $l = int($l / $BASE_LEN);
1321 print "l = $l " if DEBUG;
1323 splice @$x,$l; # keep ref($x), but modify it
1325 # we make the first part of the guess not '1000...0' but int(sqrt($lastelem))
1327 # 14400 00000 => sqrt(14400) => 120
1328 # 144000 000000 => sqrt(144000) => 379
1330 # $x->[$l--] = int('1' . '0' x $r); # old way of guessing
1331 print "$lastelem (elems $elems) => " if DEBUG;
1332 $lastelem = $lastelem / 10 if ($elems & 1 == 1); # odd or even?
1333 my $g = sqrt($lastelem); $g =~ s/\.//; # 2.345 => 2345
1334 $r -= 1 if $elems & 1 == 0; # 70 => 7
1336 # padd with zeros if result is too short
1337 $x->[$l--] = int(substr($g . '0' x $r,0,$r+1));
1338 print "now ",$x->[-1] if DEBUG;
1339 print " would have been ", int('1' . '0' x $r),"\n" if DEBUG;
1341 # If @$x > 1, we could compute the second elem of the guess, too, to create
1342 # an even better guess. Not implemented yet.
1343 $x->[$l--] = 0 while ($l >= 0); # all other digits of guess are zero
1345 print "start x= ",${_str($c,$x)},"\n" if DEBUG;
1348 my $lastlast = _zero();
1349 $steps = 0 if DEBUG;
1350 while (_acmp($c,$last,$x) != 0 && _acmp($c,$lastlast,$x) != 0)
1353 $lastlast = _copy($c,$last);
1354 $last = _copy($c,$x);
1355 _add($c,$x, _div($c,_copy($c,$y),$x));
1357 print " x= ",${_str($c,$x)},"\n" if DEBUG;
1359 print "\nsteps in sqrt: $steps, " if DEBUG;
1360 _dec($c,$x) if _acmp($c,$y,_mul($c,_copy($c,$x),$x)) < 0; # overshot?
1361 print " final ",$x->[-1],"\n" if DEBUG;
1365 ##############################################################################
1372 # the shortcut makes equal, large numbers _really_ fast, and makes only a
1373 # very small performance drop for small numbers (e.g. something with less
1374 # than 32 bit) Since we optimize for large numbers, this is enabled.
1375 return $x if _acmp($c,$x,$y) == 0; # shortcut
1377 my $m = _one(); my ($xr,$yr);
1378 my $mask = $AND_MASK;
1381 my $y1 = _copy($c,$y); # make copy
1385 while (!_is_zero($c,$x1) && !_is_zero($c,$y1))
1387 ($x1, $xr) = _div($c,$x1,$mask);
1388 ($y1, $yr) = _div($c,$y1,$mask);
1390 # make ints() from $xr, $yr
1391 # this is when the AND_BITS are greater tahn $BASE and is slower for
1392 # small (<256 bits) numbers, but faster for large numbers. Disabled
1393 # due to KISS principle
1395 # $b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }
1396 # $b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }
1397 # _add($c,$x, _mul($c, _new( $c, \($xrr & $yrr) ), $m) );
1399 # 0+ due to '&' doesn't work in strings
1400 _add($c,$x, _mul($c, [ 0+$xr->[0] & 0+$yr->[0] ], $m) );
1410 return _zero() if _acmp($c,$x,$y) == 0; # shortcut (see -and)
1412 my $m = _one(); my ($xr,$yr);
1413 my $mask = $XOR_MASK;
1416 my $y1 = _copy($c,$y); # make copy
1420 while (!_is_zero($c,$x1) && !_is_zero($c,$y1))
1422 ($x1, $xr) = _div($c,$x1,$mask);
1423 ($y1, $yr) = _div($c,$y1,$mask);
1424 # make ints() from $xr, $yr (see _and())
1425 #$b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }
1426 #$b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }
1427 #_add($c,$x, _mul($c, _new( $c, \($xrr ^ $yrr) ), $m) );
1429 # 0+ due to '^' doesn't work in strings
1430 _add($c,$x, _mul($c, [ 0+$xr->[0] ^ 0+$yr->[0] ], $m) );
1433 # the loop stops when the shorter of the two numbers is exhausted
1434 # the remainder of the longer one will survive bit-by-bit, so we simple
1435 # multiply-add it in
1436 _add($c,$x, _mul($c, $x1, $m) ) if !_is_zero($c,$x1);
1437 _add($c,$x, _mul($c, $y1, $m) ) if !_is_zero($c,$y1);
1446 return $x if _acmp($c,$x,$y) == 0; # shortcut (see _and)
1448 my $m = _one(); my ($xr,$yr);
1449 my $mask = $OR_MASK;
1452 my $y1 = _copy($c,$y); # make copy
1456 while (!_is_zero($c,$x1) && !_is_zero($c,$y1))
1458 ($x1, $xr) = _div($c,$x1,$mask);
1459 ($y1, $yr) = _div($c,$y1,$mask);
1460 # make ints() from $xr, $yr (see _and())
1461 # $b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }
1462 # $b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }
1463 # _add($c,$x, _mul($c, _new( $c, \($xrr | $yrr) ), $m) );
1465 # 0+ due to '|' doesn't work in strings
1466 _add($c,$x, _mul($c, [ 0+$xr->[0] | 0+$yr->[0] ], $m) );
1469 # the loop stops when the shorter of the two numbers is exhausted
1470 # the remainder of the longer one will survive bit-by-bit, so we simple
1471 # multiply-add it in
1472 _add($c,$x, _mul($c, $x1, $m) ) if !_is_zero($c,$x1);
1473 _add($c,$x, _mul($c, $y1, $m) ) if !_is_zero($c,$y1);
1480 # convert a decimal number to hex (ref to array, return ref to string)
1483 my $x1 = _copy($c,$x);
1487 my $x10000 = [ 0x10000 ];
1488 while (! _is_zero($c,$x1))
1490 ($x1, $xr) = _div($c,$x1,$x10000);
1491 $es .= unpack('h4',pack('v',$xr->[0]));
1494 $es =~ s/^[0]+//; # strip leading zeros
1501 # convert a decimal number to bin (ref to array, return ref to string)
1504 my $x1 = _copy($c,$x);
1508 my $x10000 = [ 0x10000 ];
1509 while (! _is_zero($c,$x1))
1511 ($x1, $xr) = _div($c,$x1,$x10000);
1512 $es .= unpack('b16',pack('v',$xr->[0]));
1515 $es =~ s/^[0]+//; # strip leading zeros
1522 # convert a hex number to decimal (ref to string, return ref to array)
1526 my $m = [ 0x10000 ]; # 16 bit at a time
1529 my $len = length($$hs)-2;
1530 $len = int($len/4); # 4-digit parts, w/o '0x'
1531 my $val; my $i = -4;
1534 $val = substr($$hs,$i,4);
1535 $val =~ s/^[+-]?0x// if $len == 0; # for last part only because
1536 $val = hex($val); # hex does not like wrong chars
1538 _add ($c, $x, _mul ($c, [ $val ], $mul ) ) if $val != 0;
1539 _mul ($c, $mul, $m ) if $len >= 0; # skip last mul
1546 # convert a hex number to decimal (ref to string, return ref to array)
1549 # instead of converting 8 bit at a time, it is faster to convert the
1550 # number to hex, and then call _from_hex.
1553 $hs =~ s/^[+-]?0b//; # remove sign and 0b
1554 my $l = length($hs); # bits
1555 $hs = '0' x (8-($l % 8)) . $hs if ($l % 8) != 0; # padd left side w/ 0
1556 my $h = unpack('H*', pack ('B*', $hs)); # repack as hex
1557 return $c->_from_hex(\('0x'.$h));
1560 my $m = [ 0x100 ]; # 8 bit at a time
1563 my $len = length($$bs)-2;
1564 $len = int($len/8); # 4-digit parts, w/o '0x'
1565 my $val; my $i = -8;
1568 $val = substr($$bs,$i,8);
1569 $val =~ s/^[+-]?0b// if $len == 0; # for last part only
1571 $val = ord(pack('B8',substr('00000000'.$val,-8,8)));
1574 _add ($c, $x, _mul ($c, [ $val ], $mul ) ) if $val != 0;
1575 _mul ($c, $mul, $m ) if $len >= 0; # skip last mul
1580 ##############################################################################
1581 # special modulus functions
1590 # modulus of power ($x ** $y) % $z
1591 my ($c,$num,$exp,$mod) = @_;
1593 # in the trivial case,
1594 if (_is_one($c,$mod))
1596 splice @$num,0,1; $num->[0] = 0;
1599 if ((scalar @$num == 1) && (($num->[0] == 0) || ($num->[0] == 1)))
1605 # $num = _mod($c,$num,$mod);
1607 my $acc = _copy($c,$num); my $t = _one();
1610 my $exp1 = _copy($c,$exp); # keep arguments
1611 while (!_is_zero($c,$exp1))
1613 if (_is_odd($c,$exp1))
1616 $t = _mod($c,$t,$mod);
1619 $acc = _mod($c,$acc,$mod);
1620 _div($c,$exp1,$two);
1621 # print "exp ",${_str($c,$exp1)},"\n";
1622 # print "acc ",${_str($c,$acc)},"\n";
1623 # print "num ",${_str($c,$num)},"\n";
1624 # print "mod ",${_str($c,$mod)},"\n";
1630 ##############################################################################
1631 ##############################################################################
1638 Math::BigInt::Calc - Pure Perl module to support Math::BigInt
1642 Provides support for big integer calculations. Not intended to be used by other
1643 modules (except Math::BigInt::Cached). Other modules which sport the same
1644 functions can also be used to support Math::Bigint, like Math::BigInt::Pari.
1648 In order to allow for multiple big integer libraries, Math::BigInt was
1649 rewritten to use library modules for core math routines. Any module which
1650 follows the same API as this can be used instead by using the following:
1652 use Math::BigInt lib => 'libname';
1654 'libname' is either the long name ('Math::BigInt::Pari'), or only the short
1655 version like 'Pari'.
1659 The following functions MUST be defined in order to support the use by
1662 _new(string) return ref to new object from ref to decimal string
1663 _zero() return a new object with value 0
1664 _one() return a new object with value 1
1666 _str(obj) return ref to a string representing the object
1667 _num(obj) returns a Perl integer/floating point number
1668 NOTE: because of Perl numeric notation defaults,
1669 the _num'ified obj may lose accuracy due to
1670 machine-dependend floating point size limitations
1672 _add(obj,obj) Simple addition of two objects
1673 _mul(obj,obj) Multiplication of two objects
1674 _div(obj,obj) Division of the 1st object by the 2nd
1675 In list context, returns (result,remainder).
1676 NOTE: this is integer math, so no
1677 fractional part will be returned.
1678 _sub(obj,obj) Simple subtraction of 1 object from another
1679 a third, optional parameter indicates that the params
1680 are swapped. In this case, the first param needs to
1681 be preserved, while you can destroy the second.
1682 sub (x,y,1) => return x - y and keep x intact!
1683 _dec(obj) decrement object by one (input is garant. to be > 0)
1684 _inc(obj) increment object by one
1687 _acmp(obj,obj) <=> operator for objects (return -1, 0 or 1)
1689 _len(obj) returns count of the decimal digits of the object
1690 _digit(obj,n) returns the n'th decimal digit of object
1692 _is_one(obj) return true if argument is +1
1693 _is_zero(obj) return true if argument is 0
1694 _is_even(obj) return true if argument is even (0,2,4,6..)
1695 _is_odd(obj) return true if argument is odd (1,3,5,7..)
1697 _copy return a ref to a true copy of the object
1699 _check(obj) check whether internal representation is still intact
1700 return 0 for ok, otherwise error message as string
1702 The following functions are optional, and can be defined if the underlying lib
1703 has a fast way to do them. If undefined, Math::BigInt will use pure Perl (hence
1704 slow) fallback routines to emulate these:
1706 _from_hex(str) return ref to new object from ref to hexadecimal string
1707 _from_bin(str) return ref to new object from ref to binary string
1709 _as_hex(str) return ref to scalar string containing the value as
1710 unsigned hex string, with the '0x' prepended.
1711 Leading zeros must be stripped.
1712 _as_bin(str) Like as_hex, only as binary string containing only
1713 zeros and ones. Leading zeros must be stripped and a
1714 '0b' must be prepended.
1716 _rsft(obj,N,B) shift object in base B by N 'digits' right
1717 For unsupported bases B, return undef to signal failure
1718 _lsft(obj,N,B) shift object in base B by N 'digits' left
1719 For unsupported bases B, return undef to signal failure
1721 _xor(obj1,obj2) XOR (bit-wise) object 1 with object 2
1722 Note: XOR, AND and OR pad with zeros if size mismatches
1723 _and(obj1,obj2) AND (bit-wise) object 1 with object 2
1724 _or(obj1,obj2) OR (bit-wise) object 1 with object 2
1726 _mod(obj,obj) Return remainder of div of the 1st by the 2nd object
1727 _sqrt(obj) return the square root of object (truncate to int)
1728 _fac(obj) return factorial of object 1 (1*2*3*4..)
1729 _pow(obj,obj) return object 1 to the power of object 2
1730 _gcd(obj,obj) return Greatest Common Divisor of two objects
1732 _zeros(obj) return number of trailing decimal zeros
1733 _modinv return inverse modulus
1734 _modpow return modulus of power ($x ** $y) % $z
1736 Input strings come in as unsigned but with prefix (i.e. as '123', '0xabc'
1739 Testing of input parameter validity is done by the caller, so you need not
1740 worry about underflow (f.i. in C<_sub()>, C<_dec()>) nor about division by
1741 zero or similar cases.
1743 The first parameter can be modified, that includes the possibility that you
1744 return a reference to a completely different object instead. Although keeping
1745 the reference and just changing it's contents is prefered over creating and
1746 returning a different reference.
1748 Return values are always references to objects or strings. Exceptions are
1749 C<_lsft()> and C<_rsft()>, which return undef if they can not shift the
1750 argument. This is used to delegate shifting of bases different than the one
1751 you can support back to Math::BigInt, which will use some generic code to
1752 calculate the result.
1754 =head1 WRAP YOUR OWN
1756 If you want to port your own favourite c-lib for big numbers to the
1757 Math::BigInt interface, you can take any of the already existing modules as
1758 a rough guideline. You should really wrap up the latest BigInt and BigFloat
1759 testsuites with your module, and replace in them any of the following:
1765 use Math::BigInt lib => 'yourlib';
1767 This way you ensure that your library really works 100% within Math::BigInt.
1771 This program is free software; you may redistribute it and/or modify it under
1772 the same terms as Perl itself.
1776 Original math code by Mark Biggar, rewritten by Tels L<http://bloodgate.com/>
1778 Seperated from BigInt and shaped API with the help of John Peacock.
1782 L<Math::BigInt>, L<Math::BigFloat>, L<Math::BigInt::BitVect>,
1783 L<Math::BigInt::GMP>, L<Math::BigInt::Cached> and L<Math::BigInt::Pari>.