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