This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
c42fc4043d640ad90edc53c3f414f30d28654a2d
[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
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