lib/Math/BigInt/Calc.pm

   1 package Math::BigInt::Calc;
   2
   3 use 5.005;
   4 use strict;
   5 # use warnings; # dont use warnings for older Perls
   6
   7 require Exporter;
   8
   9 use vars qw/ @ISA @EXPORT $VERSION/;
  10 @ISA = qw(Exporter);
  11
  12 @EXPORT = qw(
  13         _add _mul _div _mod _sub
  14         _new
  15         _str _num _acmp _len
  16         _digit
  17         _is_zero _is_one
  18         _is_even _is_odd
  19         _check _zero _one _copy _zeros
  20         _rsft _lsft
  21 );
  22 $VERSION = '0.09';
  23
  24 # Package to store unsigned big integers in decimal and do math with them
  25
  26 # Internally the numbers are stored in an array with at least 1 element, no
  27 # leading zero parts (except the first) and in base 100000
  28
  29 # todo:
  30 # - fully remove funky $# stuff (maybe)
  31 # - use integer; vs 1e7 as base
  32
  33 # USE_MUL: due to problems on certain os (os390, posix-bc) "* 1e-5" is used
  34 # instead of "/ 1e5" at some places, (marked with USE_MUL). But instead of
  35 # using the reverse only on problematic machines, I used it everytime to avoid
  36 # the costly comparisons. This _should_ work everywhere. Thanx Peter Prymmer
  37
  38 ##############################################################################
  39 # global constants, flags and accessory
  40
  41 # constants for easier life
  42 my $nan = 'NaN';
  43
  44 my $BASE_LEN = 7;
  45 my $BASE = int("1e".$BASE_LEN);         # var for trying to change it to 1e7
  46 my $RBASE = abs('1e-'.$BASE_LEN);       # see USE_MUL
  47
  48 BEGIN
  49   {
  50   # Daniel Pfeiffer: determine largest group of digits that is precisely
  51   # multipliable with itself plus carry
  52   my ($e, $num) = 4;
  53   do {
  54      $num = ('9' x ++$e) + 0;
  55     $num *= $num + 1;
  56   } until ($num == $num - 1 or $num - 1 == $num - 2);
  57   $BASE_LEN = $e-1;
  58   $BASE = int("1e".$BASE_LEN);
  59   $RBASE = abs('1e-'.$BASE_LEN);        # see USE_MUL
  60   }
  61
  62 # for quering and setting, to debug/benchmark things
  63 sub _base_len
  64   {
  65   my $b = shift;
  66   if (defined $b)
  67     {
  68     $BASE_LEN = $b;
  69     $BASE = int("1e".$BASE_LEN);
  70     $RBASE = abs('1e-'.$BASE_LEN);      # see USE_MUL
  71     }
  72   $BASE_LEN;
  73   }
  74
  75 ##############################################################################
  76 # create objects from various representations
  77
  78 sub _new
  79   {
  80   # (string) return ref to num_array
  81   # Convert a number from string format to internal base 100000 format.
  82   # Assumes normalized value as input.
  83   my $d = $_[1];
  84   # print "_new $d $$d\n";
  85   my $il = CORE::length($$d)-1;
  86   # these leaves '00000' instead of int 0 and will be corrected after any op
  87   return [ reverse(unpack("a" . ($il % $BASE_LEN+1)
  88     . ("a$BASE_LEN" x ($il / $BASE_LEN)), $$d)) ];
  89   }
  90
  91 sub _zero
  92   {
  93   # create a zero
  94   return [ 0 ];
  95   }
  96
  97 sub _one
  98   {
  99   # create a one
 100   return [ 1 ];
 101   }
 102
 103 sub _copy
 104   {
 105   return [ @{$_[1]} ];
 106   }
 107
 108 ##############################################################################
 109 # convert back to string and number
 110
 111 sub _str
 112   {
 113   # (ref to BINT) return num_str
 114   # Convert number from internal base 100000 format to string format.
 115   # internal format is always normalized (no leading zeros, "-0" => "+0")
 116   my $ar = $_[1];
 117   my $ret = "";
 118   my $l = scalar @$ar;         # number of parts
 119   return $nan if $l < 1;       # should not happen
 120   # handle first one different to strip leading zeros from it (there are no
 121   # leading zero parts in internal representation)
 122   $l --; $ret .= $ar->[$l]; $l--;
 123   # Interestingly, the pre-padd method uses more time
 124   # the old grep variant takes longer (14 to 10 sec)
 125   my $z = '0' x ($BASE_LEN-1);
 126   while ($l >= 0)
 127     {
 128     $ret .= substr($z.$ar->[$l],-$BASE_LEN); # fastest way I could think of
 129     $l--;
 130     }
 131   return \$ret;
 132   }
 133
 134 sub _num
 135   {
 136   # Make a number (scalar int/float) from a BigInt object
 137   my $x = $_[1];
 138   return $x->[0] if scalar @$x == 1;  # below $BASE
 139   my $fac = 1;
 140   my $num = 0;
 141   foreach (@$x)
 142     {
 143     $num += $fac*$_; $fac *= $BASE;
 144     }
 145   return $num;
 146   }
 147
 148 ##############################################################################
 149 # actual math code
 150
 151 sub _add
 152   {
 153   # (ref to int_num_array, ref to int_num_array)
 154   # routine to add two base 1eX numbers
 155   # stolen from Knuth Vol 2 Algorithm A pg 231
 156   # there are separate routines to add and sub as per Knuth pg 233
 157   # This routine clobbers up array x, but not y.
 158
 159   my ($c,$x,$y) = @_;
 160
 161   # for each in Y, add Y to X and carry. If after that, something is left in
 162   # X, foreach in X add carry to X and then return X, carry
 163   # Trades one "$j++" for having to shift arrays, $j could be made integer
 164   # but this would impose a limit to number-length of 2**32.
 165   my $i; my $car = 0; my $j = 0;
 166   for $i (@$y)
 167     {
 168     $x->[$j] -= $BASE
 169       if $car = (($x->[$j] += $i + $car) >= $BASE) ? 1 : 0;
 170     $j++;
 171     }
 172   while ($car != 0)
 173     {
 174     $x->[$j] -= $BASE if $car = (($x->[$j] += $car) >= $BASE) ? 1 : 0; $j++;
 175     }
 176     return $x;
 177   }
 178
 179 sub _sub
 180   {
 181   # (ref to int_num_array, ref to int_num_array)
 182   # subtract base 1eX numbers -- stolen from Knuth Vol 2 pg 232, $x > $y
 183   # subtract Y from X (X is always greater/equal!) by modifying x in place
 184   my ($c,$sx,$sy,$s) = @_;
 185
 186   my $car = 0; my $i; my $j = 0;
 187   if (!$s)
 188     {
 189     #print "case 2\n";
 190     for $i (@$sx)
 191       {
 192       last unless defined $sy->[$j] || $car;
 193       #print "x: $i y: $sy->[$j] c: $car\n";
 194       $i += $BASE if $car = (($i -= ($sy->[$j] || 0) + $car) < 0); $j++;
 195       #print "x: $i y: $sy->[$j-1] c: $car\n";
 196       }
 197     # might leave leading zeros, so fix that
 198     __strip_zeros($sx);
 199     return $sx;
 200     }
 201   else
 202     {
 203     #print "case 1 (swap)\n";
 204     for $i (@$sx)
 205       {
 206       last unless defined $sy->[$j] || $car;
 207       #print "$sy->[$j] $i $car => $sx->[$j]\n";
 208       $sy->[$j] += $BASE
 209        if $car = (($sy->[$j] = $i-($sy->[$j]||0) - $car) < 0);
 210       #print "$sy->[$j] $i $car => $sy->[$j]\n";
 211       $j++;
 212       }
 213     # might leave leading zeros, so fix that
 214     __strip_zeros($sy);
 215     return $sy;
 216     }
 217   }
 218
 219 sub _mul
 220   {
 221   # (BINT, BINT) return nothing
 222   # multiply two numbers in internal representation
 223   # modifies first arg, second need not be different from first
 224   my ($c,$xv,$yv) = @_;
 225
 226   my @prod = (); my ($prod,$car,$cty,$xi,$yi);
 227   # since multiplying $x with $x fails, make copy in this case
 228   $yv = [@$xv] if "$xv" eq "$yv";       # same references?
 229   for $xi (@$xv)
 230     {
 231     $car = 0; $cty = 0;
 232
 233     # slow variant
 234 #    for $yi (@$yv)
 235 #      {
 236 #      $prod = $xi * $yi + ($prod[$cty] || 0) + $car;
 237 #      $prod[$cty++] =
 238 #       $prod - ($car = int($prod * RBASE)) * $BASE;  # see USE_MUL
 239 #      }
 240 #    $prod[$cty] += $car if $car; # need really to check for 0?
 241 #    $xi = shift @prod;
 242
 243     # faster variant
 244     # looping through this if $xi == 0 is silly - so optimize it away!
 245     $xi = (shift @prod || 0), next if $xi == 0;
 246     for $yi (@$yv)
 247       {
 248       $prod = $xi * $yi + ($prod[$cty] || 0) + $car;
 249 ##     this is actually a tad slower
 250 ##        $prod = $prod[$cty]; $prod += ($car + $xi * $yi);     # no ||0 here
 251       $prod[$cty++] =
 252        $prod - ($car = int($prod * $RBASE)) * $BASE;  # see USE_MUL
 253       }
 254     $prod[$cty] += $car if $car; # need really to check for 0?
 255     $xi = shift @prod;
 256     }
 257   push @$xv, @prod;
 258   __strip_zeros($xv);
 259   # normalize (handled last to save check for $y->is_zero()
 260   return $xv;
 261   }
 262
 263 sub _div
 264   {
 265   # ref to array, ref to array, modify first array and return remainder if
 266   # in list context
 267   # no longer handles sign
 268   my ($c,$x,$yorg) = @_;
 269   my ($car,$bar,$prd,$dd,$xi,$yi,@q,$v2,$v1);
 270
 271   my (@d,$tmp,$q,$u2,$u1,$u0);
 272
 273   $car = $bar = $prd = 0;
 274
 275   my $y = [ @$yorg ];
 276   if (($dd = int($BASE/($y->[-1]+1))) != 1)
 277     {
 278     for $xi (@$x)
 279       {
 280       $xi = $xi * $dd + $car;
 281       $xi -= ($car = int($xi * $RBASE)) * $BASE;        # see USE_MUL
 282       }
 283     push(@$x, $car); $car = 0;
 284     for $yi (@$y)
 285       {
 286       $yi = $yi * $dd + $car;
 287       $yi -= ($car = int($yi * $RBASE)) * $BASE;        # see USE_MUL
 288       }
 289     }
 290   else
 291     {
 292     push(@$x, 0);
 293     }
 294   @q = (); ($v2,$v1) = @$y[-2,-1];
 295   $v2 = 0 unless $v2;
 296   while ($#$x > $#$y)
 297     {
 298     ($u2,$u1,$u0) = @$x[-3..-1];
 299     $u2 = 0 unless $u2;
 300     #warn "oups v1 is 0, u0: $u0 $y->[-2] $y->[-1] l ",scalar @$y,"\n"
 301     # if $v1 == 0;
 302     $q = (($u0 == $v1) ? 99999 : int(($u0*$BASE+$u1)/$v1));
 303     --$q while ($v2*$q > ($u0*$BASE+$u1-$q*$v1)*$BASE+$u2);
 304     if ($q)
 305       {
 306       ($car, $bar) = (0,0);
 307       for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
 308         {
 309         $prd = $q * $y->[$yi] + $car;
 310         $prd -= ($car = int($prd * $RBASE)) * $BASE;    # see USE_MUL
 311         $x->[$xi] += $BASE if ($bar = (($x->[$xi] -= $prd + $bar) < 0));
 312         }
 313       if ($x->[-1] < $car + $bar)
 314         {
 315         $car = 0; --$q;
 316         for ($yi = 0, $xi = $#$x-$#$y-1; $yi <= $#$y; ++$yi,++$xi)
 317           {
 318           $x->[$xi] -= $BASE
 319            if ($car = (($x->[$xi] += $y->[$yi] + $car) > $BASE));
 320           }
 321         }
 322       }
 323       pop(@$x); unshift(@q, $q);
 324     }
 325   if (wantarray)
 326     {
 327     @d = ();
 328     if ($dd != 1)
 329       {
 330       $car = 0;
 331       for $xi (reverse @$x)
 332         {
 333         $prd = $car * $BASE + $xi;
 334         $car = $prd - ($tmp = int($prd / $dd)) * $dd; # see USE_MUL
 335         unshift(@d, $tmp);
 336         }
 337       }
 338     else
 339       {
 340       @d = @$x;
 341       }
 342     @$x = @q;
 343     __strip_zeros($x);
 344     __strip_zeros(\@d);
 345     return ($x,\@d);
 346     }
 347   @$x = @q;
 348   __strip_zeros($x);
 349   return $x;
 350   }
 351
 352 ##############################################################################
 353 # shifts
 354
 355 sub _rsft
 356   {
 357   my ($c,$x,$y,$n) = @_;
 358
 359   if ($n != 10)
 360     {
 361     return;     # we cant do this here, due to now _pow, so signal failure
 362     }
 363   else
 364     {
 365     # shortcut (faster) for shifting by 10)
 366     # multiples of $BASE_LEN
 367     my $dst = 0;                                # destination
 368     my $src = _num($c,$y);                      # as normal int
 369     my $rem = $src % $BASE_LEN;                 # reminder to shift
 370     $src = int($src / $BASE_LEN);               # source
 371     if ($rem == 0)
 372       {
 373       splice (@$x,0,$src);                      # even faster, 38.4 => 39.3
 374       }
 375     else
 376       {
 377       my $len = scalar @$x - $src;              # elems to go
 378       my $vd; my $z = '0'x $BASE_LEN;
 379       $x->[scalar @$x] = 0;                     # avoid || 0 test inside loop
 380       while ($dst < $len)
 381         {
 382         $vd = $z.$x->[$src];
 383         #print "$dst $src '$vd' ";
 384         $vd = substr($vd,-$BASE_LEN,$BASE_LEN-$rem);
 385         #print "'$vd' ";
 386         $src++;
 387         $vd = substr($z.$x->[$src],-$rem,$rem) . $vd;
 388         #print "'$vd1' ";
 389         #print "'$vd'\n";
 390         $vd = substr($vd,-$BASE_LEN,$BASE_LEN) if length($vd) > $BASE_LEN;
 391         $x->[$dst] = int($vd);
 392         $dst++;
 393         }
 394       splice (@$x,$dst) if $dst > 0;            # kill left-over array elems
 395       pop @$x if $x->[-1] == 0;                 # kill last element if 0
 396       } # else rem == 0
 397     }
 398   $x;
 399   }
 400
 401 sub _lsft
 402   {
 403   my ($c,$x,$y,$n) = @_;
 404
 405   if ($n != 10)
 406     {
 407     return;     # we cant do this here, due to now _pow, so signal failure
 408     }
 409   else
 410     {
 411     # shortcut (faster) for shifting by 10) since we are in base 10eX
 412     # multiples of $BASE_LEN:
 413     my $src = scalar @$x;                       # source
 414     my $len = _num($c,$y);                      # shift-len as normal int
 415     my $rem = $len % $BASE_LEN;                 # reminder to shift
 416     my $dst = $src + int($len/$BASE_LEN);       # destination
 417     my $vd;                                     # further speedup
 418     #print "src $src:",$x->[$src]||0," dst $dst:",$v->[$dst]||0," rem $rem\n";
 419     $x->[$src] = 0;                             # avoid first ||0 for speed
 420     my $z = '0' x $BASE_LEN;
 421     while ($src >= 0)
 422       {
 423       $vd = $x->[$src]; $vd = $z.$vd;
 424       #print "s $src d $dst '$vd' ";
 425       $vd = substr($vd,-$BASE_LEN+$rem,$BASE_LEN-$rem);
 426       #print "'$vd' ";
 427       $vd .= $src > 0 ? substr($z.$x->[$src-1],-$BASE_LEN,$rem) : '0' x $rem;
 428       #print "'$vd' ";
 429       $vd = substr($vd,-$BASE_LEN,$BASE_LEN) if length($vd) > $BASE_LEN;
 430       #print "'$vd'\n";
 431       $x->[$dst] = int($vd);
 432       $dst--; $src--;
 433       }
 434     # set lowest parts to 0
 435     while ($dst >= 0) { $x->[$dst--] = 0; }
 436     # fix spurios last zero element
 437     splice @$x,-1 if $x->[-1] == 0;
 438     #print "elems: "; my $i = 0;
 439     #foreach (reverse @$v) { print "$i $_ "; $i++; } print "\n";
 440     }
 441   $x;
 442   }
 443
 444 ##############################################################################
 445 # testing
 446
 447 sub _acmp
 448   {
 449   # internal absolute post-normalized compare (ignore signs)
 450   # ref to array, ref to array, return <0, 0, >0
 451   # arrays must have at least one entry; this is not checked for
 452
 453   my ($c,$cx, $cy) = @_;
 454
 455   #print "$cx $cy\n";
 456   my ($i,$a,$x,$y,$k);
 457   # calculate length based on digits, not parts
 458   $x = _len('',$cx); $y = _len('',$cy);
 459   # print "length: ",($x-$y),"\n";
 460   my $lxy = $x - $y;                            # if different in length
 461   return -1 if $lxy < 0;
 462   return 1 if $lxy > 0;
 463   #print "full compare\n";
 464   $i = 0; $a = 0;
 465   # first way takes 5.49 sec instead of 4.87, but has the early out advantage
 466   # so grep is slightly faster, but more inflexible. hm. $_ instead of $k
 467   # yields 5.6 instead of 5.5 sec huh?
 468   # manual way (abort if unequal, good for early ne)
 469   my $j = scalar @$cx - 1;
 470   while ($j >= 0)
 471    {
 472    # print "$cx->[$j] $cy->[$j] $a",$cx->[$j]-$cy->[$j],"\n";
 473    last if ($a = $cx->[$j] - $cy->[$j]); $j--;
 474    }
 475   return 1 if $a > 0;
 476   return -1 if $a < 0;
 477   return 0;                                     # equal
 478   # while it early aborts, it is even slower than the manual variant
 479   #grep { return $a if ($a = $_ - $cy->[$i++]); } @$cx;
 480   # grep way, go trough all (bad for early ne)
 481   #grep { $a = $_ - $cy->[$i++]; } @$cx;
 482   #return $a;
 483   }
 484
 485 sub _len
 486   {
 487   # computer number of digits in bigint, minus the sign
 488   # int() because add/sub sometimes leaves strings (like '00005') instead of
 489   # int ('5') in this place, causing length to fail
 490   my $cx = $_[1];
 491
 492   return (@$cx-1)*$BASE_LEN+length(int($cx->[-1]));
 493   }
 494
 495 sub _digit
 496   {
 497   # return the nth digit, negative values count backward
 498   # zero is rightmost, so _digit(123,0) will give 3
 499   my ($c,$x,$n) = @_;
 500
 501   my $len = _len('',$x);
 502
 503   $n = $len+$n if $n < 0;               # -1 last, -2 second-to-last
 504   $n = abs($n);                         # if negative was too big
 505   $len--; $n = $len if $n > $len;       # n to big?
 506
 507   my $elem = int($n / $BASE_LEN);       # which array element
 508   my $digit = $n % $BASE_LEN;           # which digit in this element
 509   $elem = '0000'.@$x[$elem];            # get element padded with 0's
 510   return substr($elem,-$digit-1,1);
 511   }
 512
 513 sub _zeros
 514   {
 515   # return amount of trailing zeros in decimal
 516   # check each array elem in _m for having 0 at end as long as elem == 0
 517   # Upon finding a elem != 0, stop
 518   my $x = $_[1];
 519   my $zeros = 0; my $elem;
 520   foreach my $e (@$x)
 521     {
 522     if ($e != 0)
 523       {
 524       $elem = "$e";                             # preserve x
 525       $elem =~ s/.*?(0*$)/$1/;                  # strip anything not zero
 526       $zeros *= $BASE_LEN;                      # elems * 5
 527       $zeros += CORE::length($elem);            # count trailing zeros
 528       last;                                     # early out
 529       }
 530     $zeros ++;                                  # real else branch: 50% slower!
 531     }
 532   return $zeros;
 533   }
 534
 535 ##############################################################################
 536 # _is_* routines
 537
 538 sub _is_zero
 539   {
 540   # return true if arg (BINT or num_str) is zero (array '+', '0')
 541   my $x = $_[1];
 542   return (((scalar @$x == 1) && ($x->[0] == 0))) <=> 0;
 543   }
 544
 545 sub _is_even
 546   {
 547   # return true if arg (BINT or num_str) is even
 548   my $x = $_[1];
 549   return (!($x->[0] & 1)) <=> 0;
 550   }
 551
 552 sub _is_odd
 553   {
 554   # return true if arg (BINT or num_str) is even
 555   my $x = $_[1];
 556   return (($x->[0] & 1)) <=> 0;
 557   }
 558
 559 sub _is_one
 560   {
 561   # return true if arg (BINT or num_str) is one (array '+', '1')
 562   my $x = $_[1];
 563   return (scalar @$x == 1) && ($x->[0] == 1) <=> 0;
 564   }
 565
 566 sub __strip_zeros
 567   {
 568   # internal normalization function that strips leading zeros from the array
 569   # args: ref to array
 570   my $s = shift;
 571
 572   my $cnt = scalar @$s; # get count of parts
 573   my $i = $cnt-1;
 574   #print "strip: cnt $cnt i $i\n";
 575   # '0', '3', '4', '0', '0',
 576   #  0    1    2    3    4
 577   # cnt = 5, i = 4
 578   # i = 4
 579   # i = 3
 580   # => fcnt = cnt - i (5-2 => 3, cnt => 5-1 = 4, throw away from 4th pos)
 581   # >= 1: skip first part (this can be zero)
 582   while ($i > 0) { last if $s->[$i] != 0; $i--; }
 583   $i++; splice @$s,$i if ($i < $cnt); # $i cant be 0
 584   return $s;
 585   }
 586
 587 ###############################################################################
 588 # check routine to test internal state of corruptions
 589
 590 sub _check
 591   {
 592   # no checks yet, pull it out from the test suite
 593   my $x = $_[1];
 594
 595   return "$x is not a reference" if !ref($x);
 596
 597   # are all parts are valid?
 598   my $i = 0; my $j = scalar @$x; my ($e,$try);
 599   while ($i < $j)
 600     {
 601     $e = $x->[$i]; $e = 'undef' unless defined $e;
 602     $try = '=~ /^[\+]?[0-9]+\$/; '."($x, $e)";
 603     last if $e !~ /^[+]?[0-9]+$/;
 604     $try = ' < 0 || >= $BASE; '."($x, $e)";
 605     last if $e <0 || $e >= $BASE;
 606     # this test is disabled, since new/bnorm and certain ops (like early out
 607     # in add/sub) are allowed/expected to leave '00000' in some elements
 608     #$try = '=~ /^00+/; '."($x, $e)";
 609     #last if $e =~ /^00+/;
 610     $i++;
 611     }
 612   return "Illegal part '$e' at pos $i (tested: $try)" if $i < $j;
 613   return 0;
 614   }
 615
 616 1;
 617 __END__
 618
 619 =head1 NAME
 620
 621 Math::BigInt::Calc - Pure Perl module to support Math::BigInt
 622
 623 =head1 SYNOPSIS
 624
 625 Provides support for big integer calculations. Not intended
 626 to be used by other modules. Other modules which export the
 627 same functions can also be used to support Math::Bigint
 628
 629 =head1 DESCRIPTION
 630
 631 In order to allow for multiple big integer libraries, Math::BigInt
 632 was rewritten to use library modules for core math routines. Any
 633 module which follows the same API as this can be used instead by
 634 using the following call:
 635
 636         use Math::BigInt lib => BigNum;
 637
 638 =head1 EXPORT
 639
 640 The following functions MUST be exported in order to support
 641 the use by Math::BigInt:
 642
 643         _new(string)    return ref to new object from ref to decimal string
 644         _zero()         return a new object with value 0
 645         _one()          return a new object with value 1
 646
 647         _str(obj)       return ref to a string representing the object
 648         _num(obj)       returns a Perl integer/floating point number
 649                         NOTE: because of Perl numeric notation defaults,
 650                         the _num'ified obj may lose accuracy due to
 651                         machine-dependend floating point size limitations
 652
 653         _add(obj,obj)   Simple addition of two objects
 654         _mul(obj,obj)   Multiplication of two objects
 655         _div(obj,obj)   Division of the 1st object by the 2nd
 656                         In list context, returns (result,remainder).
 657                         NOTE: this is integer math, so no
 658                         fractional part will be returned.
 659         _sub(obj,obj)   Simple subtraction of 1 object from another
 660                         a third, optional parameter indicates that the params
 661                         are swapped. In this case, the first param needs to
 662                         be preserved, while you can destroy the second.
 663                         sub (x,y,1) => return x - y and keep x intact!
 664
 665         _acmp(obj,obj)  <=> operator for objects (return -1, 0 or 1)
 666
 667         _len(obj)       returns count of the decimal digits of the object
 668         _digit(obj,n)   returns the n'th decimal digit of object
 669
 670         _is_one(obj)    return true if argument is +1
 671         _is_zero(obj)   return true if argument is 0
 672         _is_even(obj)   return true if argument is even (0,2,4,6..)
 673         _is_odd(obj)    return true if argument is odd (1,3,5,7..)
 674
 675         _copy           return a ref to a true copy of the object
 676
 677         _check(obj)     check whether internal representation is still intact
 678                         return 0 for ok, otherwise error message as string
 679
 680 The following functions are optional, and can be exported if the underlying lib
 681 has a fast way to do them. If not defined, Math::BigInt will use a pure, but
 682 slow, Perl function as fallback to emulate these:
 683
 684         _from_hex(str)  return ref to new object from ref to hexadecimal string
 685         _from_bin(str)  return ref to new object from ref to binary string
 686
 687         _rsft(obj,N,B)  shift object in base B by N 'digits' right
 688         _lsft(obj,N,B)  shift object in base B by N 'digits' left
 689
 690         _xor(obj1,obj2) XOR (bit-wise) object 1 with object 2
 691                         Mote: XOR, AND and OR pad with zeros if size mismatches
 692         _and(obj1,obj2) AND (bit-wise) object 1 with object 2
 693         _or(obj1,obj2)  OR (bit-wise) object 1 with object 2
 694
 695         _sqrt(obj)      return the square root of object
 696         _pow(obj,obj)   return object 1 to the power of object 2
 697         _gcd(obj,obj)   return Greatest Common Divisor of two objects
 698
 699         _zeros(obj)     return number of trailing decimal zeros
 700
 701         _dec(obj)       decrement object by one (input is >= 1)
 702         _inc(obj)       increment object by one
 703
 704 Input strings come in as unsigned but with prefix (i.e. as '123', '0xabc'
 705 or '0b1101').
 706
 707 Testing of input parameter validity is done by the caller, so you need not
 708 worry about underflow (f.i. in C<_sub()>, C<_dec()>) nor about division by
 709 zero or similar cases.
 710
 711 The first parameter can be modified, that includes the possibility that you
 712 return a reference to a completely different object instead. Although keeping
 713 the reference the same is prefered.
 714
 715 Return values are always references to objects or strings. Exceptions are
 716 C<_lsft()> and C<_rsft()>, which return undef if they can not shift the
 717 argument. This is used to delegate shifting of bases different than 10 back
 718 to BigInt, which will use some generic code to calculate the result.
 719
 720 =head1 WRAP YOUR OWN
 721
 722 If you want to port your own favourite c-lib for big numbers to the
 723 Math::BigInt interface, you can take any of the already existing modules as
 724 a rough guideline. You should really wrap up the latest BigInt and BigFloat
 725 testsuites with your module, and replace the following line:
 726
 727         use Math::BigInt;
 728
 729 by
 730
 731         use Math::BigInt lib => 'yourlib';
 732
 733 This way you ensure that your library really works 100% within Math::BigInt.
 734
 735 =head1 LICENSE
 736
 737 This program is free software; you may redistribute it and/or modify it under
 738 the same terms as Perl itself.
 739
 740 =head1 AUTHORS
 741
 742 Original math code by Mark Biggar, rewritten by Tels L<http://bloodgate.com/>
 743 in late 2000, 2001.
 744 Seperated from BigInt and shaped API with the help of John Peacock.
 745
 746 =head1 SEE ALSO
 747
 748 L<Math::BigInt>, L<Math::BigFloat>, L<Math::BigInt::BitVect> and
 749 L<Math::BigInt::Pari>.
 750
 751 =cut