diff options
author | Karl Berry <karl@freefriends.org> | 2012-05-21 00:15:27 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2012-05-21 00:15:27 +0000 |
commit | a4c42bfb2337d37da89d789cb8cc226367994e32 (patch) | |
tree | c3eabdef5d565a4e515d2be0d9d4d0540bde0250 /Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm | |
parent | 8274475057f024d35332ac47c2e2f23ea156e6ed (diff) |
perl 5.14.2 from siep
git-svn-id: svn://tug.org/texlive/trunk@26525 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm')
-rw-r--r-- | Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm | 822 |
1 files changed, 590 insertions, 232 deletions
diff --git a/Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm b/Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm index 52e33d232ae..25f9a3b99d9 100644 --- a/Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm +++ b/Master/tlpkg/tlperl/lib/Math/BigInt/Calc.pm @@ -1,10 +1,10 @@ package Math::BigInt::Calc; -use 5.006; +use 5.006002; use strict; # use warnings; # dont use warnings for older Perls -our $VERSION = '0.52'; +our $VERSION = '1.993'; # Package to store unsigned big integers in decimal and do math with them @@ -60,7 +60,7 @@ sub _base_len $BASE = int("1e".$BASE_LEN); $MAX_VAL = $BASE-1; return $BASE_LEN unless wantarray; - return ($BASE_LEN, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN, $MAX_VAL, $BASE); + return ($BASE_LEN, $BASE, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN, $MAX_VAL,); } # find whether we can use mul or div in mul()/div() @@ -95,7 +95,7 @@ sub _base_len } } return $BASE_LEN unless wantarray; - return ($BASE_LEN, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN, $MAX_VAL, $BASE); + return ($BASE_LEN, $BASE, $AND_BITS, $XOR_BITS, $OR_BITS, $BASE_LEN, $MAX_VAL); } sub _new @@ -189,7 +189,7 @@ BEGIN $XOR_MASK = __PACKAGE__->_new( ( 2 ** $XOR_BITS )); $OR_MASK = __PACKAGE__->_new( ( 2 ** $OR_BITS )); - # We can compute the approximate lenght no faster than the real length: + # We can compute the approximate length no faster than the real length: *_alen = \&_len; } @@ -272,17 +272,22 @@ sub _str sub _num { - # Make a number (scalar int/float) from a BigInt object - my $x = $_[1]; + # Make a Perl scalar number (int/float) from a BigInt object. + my $x = $_[1]; - return 0+$x->[0] if scalar @$x == 1; # below $BASE - my $fac = 1; - my $num = 0; - foreach (@$x) - { - $num += $fac*$_; $fac *= $BASE; + return 0 + $x->[0] if scalar @$x == 1; # below $BASE + + # Start with the most significant element and work towards the least + # significant element. Avoid multiplying "inf" (which happens if the number + # overflows) with "0" (if there are zero elements in $x) since this gives + # "nan" which propagates to the output. + + my $num = 0; + for (my $i = $#$x ; $i >= 0 ; --$i) { + $num *= $BASE; + $num += $x -> [$i]; } - $num; + return $num; } ############################################################################## @@ -294,7 +299,7 @@ sub _add # routine to add two base 1eX numbers # stolen from Knuth Vol 2 Algorithm A pg 231 # there are separate routines to add and sub as per Knuth pg 233 - # This routine clobbers up array x, but not y. + # This routine modifies array x, but not y. my ($c,$x,$y) = @_; @@ -595,7 +600,7 @@ sub _div_use_mul my ($c,$x,$yorg) = @_; - # the general div algorithmn here is about O(N*N) and thus quite slow, so + # the general div algorithm here is about O(N*N) and thus quite slow, so # we first check for some special cases and use shortcuts to handle them. # This works, because we store the numbers in a chunked format where each @@ -785,7 +790,7 @@ sub _div_use_div_64 my ($c,$x,$yorg) = @_; use integer; - # the general div algorithmn here is about O(N*N) and thus quite slow, so + # the general div algorithm here is about O(N*N) and thus quite slow, so # we first check for some special cases and use shortcuts to handle them. # This works, because we store the numbers in a chunked format where each @@ -976,7 +981,7 @@ sub _div_use_div # in list context my ($c,$x,$yorg) = @_; - # the general div algorithmn here is about O(N*N) and thus quite slow, so + # the general div algorithm here is about O(N*N) and thus quite slow, so # we first check for some special cases and use shortcuts to handle them. # This works, because we store the numbers in a chunked format where each @@ -1206,20 +1211,18 @@ sub _len sub _digit { - # return the nth digit, negative values count backward - # zero is rightmost, so _digit(123,0) will give 3 + # Return the nth digit. Zero is rightmost, so _digit(123,0) gives 3. + # Negative values count from the left, so _digit(123, -1) gives 1. my ($c,$x,$n) = @_; my $len = _len('',$x); - $n = $len+$n if $n < 0; # -1 last, -2 second-to-last - $n = abs($n); # if negative was too big - $len--; $n = $len if $n > $len; # n to big? - - my $elem = int($n / $BASE_LEN); # which array element - my $digit = $n % $BASE_LEN; # which digit in this element - $elem = '0' x $BASE_LEN . @$x[$elem]; # get element padded with 0's - substr($elem,-$digit-1,1); + $n += $len if $n < 0; # -1 last, -2 second-to-last + return "0" if $n < 0 || $n >= $len; # return 0 for digits out of range + + my $elem = int($n / $BASE_LEN); # which array element + my $digit = $n % $BASE_LEN; # which digit in this element + substr("$x->[$elem]", -$digit-1, 1); } sub _zeros @@ -1264,8 +1267,8 @@ sub _is_even sub _is_odd { - # return true if arg is even - (($_[1]->[0] & 1)) <=> 0; + # return true if arg is odd + (($_[1]->[0] & 1)) <=> 0; } sub _is_one @@ -1352,22 +1355,24 @@ sub _mod # if possible, use mod shortcut my ($c,$x,$yo) = @_; - # slow way since $y to big + # slow way since $y too big if (scalar @$yo > 1) { my ($xo,$rem) = _div($c,$x,$yo); - return $rem; + @$x = @$rem; + return $x; } my $y = $yo->[0]; - # both are single element arrays + + # if both are single element arrays if (scalar @$x == 1) { $x->[0] %= $y; return $x; } - # @y is a single element, but @x has more than one element + # if @$x has more than one element, but @$y is a single element my $b = $BASE % $y; if ($b == 0) { @@ -1378,7 +1383,8 @@ sub _mod } elsif ($b == 1) { - # else need to go through all elements: O(N), but loop is a bit simplified + # else need to go through all elements in @$x: O(N), but loop is a bit + # simplified my $r = 0; foreach (@$x) { @@ -1390,8 +1396,9 @@ sub _mod } else { - # else need to go through all elements: O(N) - my $r = 0; my $bm = 1; + # else need to go through all elements in @$x: O(N) + my $r = 0; + my $bm = 1; foreach (@$x) { $r = ($_ * $bm + $r) % $y; @@ -1405,8 +1412,8 @@ sub _mod $r = 0 if $r == $y; $x->[0] = $r; } - splice (@$x,1); # keep one element of $x - $x; + @$x = $x->[0]; # keep one element of @$x + return $x; } ############################################################################## @@ -1489,7 +1496,7 @@ sub _lsft } # set lowest parts to 0 while ($dst >= 0) { $x->[$dst--] = 0; } - # fix spurios last zero element + # fix spurious last zero element splice @$x,-1 if $x->[-1] == 0; $x; } @@ -1530,40 +1537,68 @@ sub _pow $cx; } -sub _nok - { - # n over k - # ref to array, return ref to array - my ($c,$n,$k) = @_; +sub _nok { + # Return binomial coefficient (n over k). + # Given refs to arrays, return ref to array. + # First input argument is modified. - # ( 7 ) 7! 7*6*5 * 4*3*2*1 7 * 6 * 5 - # ( - ) = --------- = --------------- = --------- - # ( 3 ) 3! (7-3)! 3*2*1 * 4*3*2*1 3 * 2 * 1 + my ($c, $n, $k) = @_; - # compute n - k + 2 (so we start with 5 in the example above) - my $x = _copy($c,$n); + # If k > n/2, or, equivalently, 2*k > n, compute nok(n, k) as + # nok(n, n-k), to minimize the number if iterations in the loop. - _sub($c,$n,$k); - if (!_is_one($c,$n)) { - _inc($c,$n); - my $f = _copy($c,$n); _inc($c,$f); # n = 5, f = 6, d = 2 - my $d = _two($c); - while (_acmp($c,$f,$x) <= 0) # f < n ? - { - # n = (n * f / d) == 5 * 6 / 2 => n == 3 - $n = _mul($c,$n,$f); $n = _div($c,$n,$d); - # f = 7, d = 3 - _inc($c,$f); _inc($c,$d); - } + my $twok = _mul($c, _two($c), _copy($c, $k)); # 2 * k + if (_acmp($c, $twok, $n) > 0) { # if 2*k > n + $k = _sub($c, _copy($c, $n), $k); # k = n - k + } } - else - { - # keep ref to $n and set it to 1 - splice (@$n,1); $n->[0] = 1; + + # Example: + # + # / 7 \ 7! 1*2*3*4 * 5*6*7 5 * 6 * 7 6 7 + # | | = --------- = --------------- = --------- = 5 * - * - + # \ 3 / (7-3)! 3! 1*2*3*4 * 1*2*3 1 * 2 * 3 2 3 + + if (_is_zero($c, $k)) { + @$n = 1; } - $n; - } + + else { + + # Make a copy of the original n, since we'll be modifing n in-place. + + my $n_orig = _copy($c, $n); + + # n = 5, f = 6, d = 2 (cf. example above) + + _sub($c, $n, $k); + _inc($c, $n); + + my $f = _copy($c, $n); + _inc($c, $f); + + my $d = _two($c); + + # while f <= n (the original n, that is) ... + + while (_acmp($c, $f, $n_orig) <= 0) { + + # n = (n * f / d) == 5 * 6 / 2 (cf. example above) + + _mul($c, $n, $f); + _div($c, $n, $d); + + # f = 7, d = 3 (cf. example above) + + _inc($c, $f); + _inc($c, $d); + } + + } + + return $n; +} my @factorials = ( 1, @@ -2030,7 +2065,7 @@ sub _root # reset step to 2 $step = _two(); # add two, because $trial cannot be exactly the result (otherwise we would - # alrady have found it) + # already have found it) _add($c, $trial, $step); # and now add more and more (2,4,6,8,10 etc) @@ -2348,32 +2383,45 @@ sub _from_bin sub _modinv { - # modular inverse + # modular multiplicative inverse my ($c,$x,$y) = @_; - my $u = _zero($c); my $u1 = _one($c); - my $a = _copy($c,$y); my $b = _copy($c,$x); + # modulo zero + if (_is_zero($c, $y)) { + return (undef, undef); + } + + # modulo one + if (_is_one($c, $y)) { + return (_zero($c), '+'); + } + + my $u = _zero($c); + my $v = _one($c); + my $a = _copy($c,$y); + my $b = _copy($c,$x); - # Euclid's Algorithm for bgcd(), only that we calc bgcd() ($a) and the - # result ($u) at the same time. See comments in BigInt for why this works. + # Euclid's Algorithm for bgcd(), only that we calc bgcd() ($a) and the result + # ($u) at the same time. See comments in BigInt for why this works. my $q; - ($a, $q, $b) = ($b, _div($c,$a,$b)); # step 1 my $sign = 1; - while (!_is_zero($c,$b)) - { - my $t = _add($c, # step 2: - _mul($c,_copy($c,$u1), $q) , # t = u1 * q - $u ); # + u - $u = $u1; # u = u1, u1 = t - $u1 = $t; - $sign = -$sign; - ($a, $q, $b) = ($b, _div($c,$a,$b)); # step 1 - } + { + ($a, $q, $b) = ($b, _div($c, $a, $b)); # step 1 + last if _is_zero($c, $b); + + my $t = _add($c, # step 2: + _mul($c, _copy($c, $v), $q) , # t = v * q + $u ); # + u + $u = $v; # u = v + $v = $t; # v = t + $sign = -$sign; + redo; + } # if the gcd is not 1, then return NaN - return (undef,undef) unless _is_one($c,$a); - - ($u1, $sign == 1 ? '+' : '-'); + return (undef, undef) unless _is_one($c, $a); + + ($v, $sign == 1 ? '+' : '-'); } sub _modpow @@ -2381,18 +2429,24 @@ sub _modpow # modulus of power ($x ** $y) % $z my ($c,$num,$exp,$mod) = @_; - # in the trivial case, + # a^b (mod 1) = 0 for all a and b if (_is_one($c,$mod)) { - splice @$num,0,1; $num->[0] = 0; - return $num; - } - if ((scalar @$num == 1) && (($num->[0] == 0) || ($num->[0] == 1))) - { - $num->[0] = 1; - return $num; + @$num = 0; + return $num; } + # 0^a (mod m) = 0 if m != 0, a != 0 + # 0^0 (mod m) = 1 if m != 0 + if (_is_zero($c, $num)) { + if (_is_zero($c, $exp)) { + @$num = 1; + } else { + @$num = 0; + } + return $num; + } + # $num = _mod($c,$num,$mod); # this does not make it faster my $acc = _copy($c,$num); my $t = _one(); @@ -2413,19 +2467,40 @@ sub _modpow $num; } -sub _gcd - { - # greatest common divisor - my ($c,$x,$y) = @_; +sub _gcd { + # Greatest common divisor. - while ( (scalar @$y != 1) || ($y->[0] != 0) ) # while ($y != 0) - { - my $t = _copy($c,$y); - $y = _mod($c, $x, $y); - $x = $t; + my ($c, $x, $y) = @_; + + # gcd(0,0) = 0 + # gcd(0,a) = a, if a != 0 + + if (@$x == 1 && $x->[0] == 0) { + if (@$y == 1 && $y->[0] == 0) { + @$x = 0; + } else { + @$x = @$y; + } + return $x; } - $x; - } + + # Until $y is zero ... + + until (@$y == 1 && $y->[0] == 0) { + + # Compute remainder. + + _mod($c, $x, $y); + + # Swap $x and $y. + + my $tmp = [ @$x ]; + @$x = @$y; + $y = $tmp; # no deref here; that would modify input $y + } + + return $x; +} ############################################################################## ############################################################################## @@ -2433,148 +2508,415 @@ sub _gcd 1; __END__ +=pod + =head1 NAME Math::BigInt::Calc - Pure Perl module to support Math::BigInt =head1 SYNOPSIS -Provides support for big integer calculations. Not intended to be used by other -modules. Other modules which sport the same functions can also be used to support -Math::BigInt, like Math::BigInt::GMP or Math::BigInt::Pari. +This library provides support for big integer calculations. It is not +intended to be used by other modules. Other modules which support the same +API (see below) can also be used to support Math::BigInt, like +Math::BigInt::GMP and Math::BigInt::Pari. =head1 DESCRIPTION +In this library, the numbers are represented in base B = 10**N, where N is +the largest possible value that does not cause overflow in the intermediate +computations. The base B elements are stored in an array, with the least +significant element stored in array element zero. There are no leading zero +elements, except a single zero element when the number is zero. + +For instance, if B = 10000, the number 1234567890 is represented internally +as [3456, 7890, 12]. + +=head1 THE Math::BigInt API + In order to allow for multiple big integer libraries, Math::BigInt was -rewritten to use library modules for core math routines. Any module which -follows the same API as this can be used instead by using the following: +rewritten to use a plug-in library for core math routines. Any module which +conforms to the API can be used by Math::BigInt by using this in your program: use Math::BigInt lib => 'libname'; -'libname' is either the long name ('Math::BigInt::Pari'), or only the short -version like 'Pari'. - -=head1 STORAGE - -=head1 METHODS - -The following functions MUST be defined in order to support the use by -Math::BigInt v1.70 or later: - - api_version() return API version, 1 for v1.70, 2 for v1.83 - _new(string) return ref to new object from ref to decimal string - _zero() return a new object with value 0 - _one() return a new object with value 1 - _two() return a new object with value 2 - _ten() return a new object with value 10 - - _str(obj) return ref to a string representing the object - _num(obj) returns a Perl integer/floating point number - NOTE: because of Perl numeric notation defaults, - the _num'ified obj may lose accuracy due to - machine-dependent floating point size limitations - - _add(obj,obj) Simple addition of two objects - _mul(obj,obj) Multiplication of two objects - _div(obj,obj) Division of the 1st object by the 2nd - In list context, returns (result,remainder). - NOTE: this is integer math, so no - fractional part will be returned. - The second operand will be not be 0, so no need to - check for that. - _sub(obj,obj) Simple subtraction of 1 object from another - a third, optional parameter indicates that the params - are swapped. In this case, the first param needs to - be preserved, while you can destroy the second. - sub (x,y,1) => return x - y and keep x intact! - _dec(obj) decrement object by one (input is guaranteed to be > 0) - _inc(obj) increment object by one - - - _acmp(obj,obj) <=> operator for objects (return -1, 0 or 1) - - _len(obj) returns count of the decimal digits of the object - _digit(obj,n) returns the n'th decimal digit of object - - _is_one(obj) return true if argument is 1 - _is_two(obj) return true if argument is 2 - _is_ten(obj) return true if argument is 10 - _is_zero(obj) return true if argument is 0 - _is_even(obj) return true if argument is even (0,2,4,6..) - _is_odd(obj) return true if argument is odd (1,3,5,7..) - - _copy return a ref to a true copy of the object - - _check(obj) check whether internal representation is still intact - return 0 for ok, otherwise error message as string - - _from_hex(str) return new object from a hexadecimal string - _from_bin(str) return new object from a binary string - _from_oct(str) return new object from an octal string - - _as_hex(str) return string containing the value as - unsigned hex string, with the '0x' prepended. - Leading zeros must be stripped. - _as_bin(str) Like as_hex, only as binary string containing only - zeros and ones. Leading zeros must be stripped and a - '0b' must be prepended. - - _rsft(obj,N,B) shift object in base B by N 'digits' right - _lsft(obj,N,B) shift object in base B by N 'digits' left - - _xor(obj1,obj2) XOR (bit-wise) object 1 with object 2 - Note: XOR, AND and OR pad with zeros if size mismatches - _and(obj1,obj2) AND (bit-wise) object 1 with object 2 - _or(obj1,obj2) OR (bit-wise) object 1 with object 2 - - _mod(obj1,obj2) Return remainder of div of the 1st by the 2nd object - _sqrt(obj) return the square root of object (truncated to int) - _root(obj) return the n'th (n >= 3) root of obj (truncated to int) - _fac(obj) return factorial of object 1 (1*2*3*4..) - _pow(obj1,obj2) return object 1 to the power of object 2 - return undef for NaN - _zeros(obj) return number of trailing decimal zeros - _modinv return inverse modulus - _modpow return modulus of power ($x ** $y) % $z - _log_int(X,N) calculate integer log() of X in base N - X >= 0, N >= 0 (return undef for NaN) - returns (RESULT, EXACT) where EXACT is: - 1 : result is exactly RESULT - 0 : result was truncated to RESULT - undef : unknown whether result is exactly RESULT - _gcd(obj,obj) return Greatest Common Divisor of two objects - -The following functions are REQUIRED for an api_version of 2 or greater: - - _1ex($x) create the number 1Ex where x >= 0 - _alen(obj) returns approximate count of the decimal digits of the - object. This estimate MUST always be greater or equal - to what _len() returns. - _nok(n,k) calculate n over k (binomial coefficient) - -The following functions are optional, and can be defined if the underlying lib +'libname' is either the long name, like 'Math::BigInt::Pari', or only the short +version, like 'Pari'. + +=head2 General Notes + +A library only needs to deal with unsigned big integers. Testing of input +parameter validity is done by the caller, so there is no need to worry about +underflow (e.g., in C<_sub()> and C<_dec()>) nor about division by zero (e.g., +in C<_div()>) or similar cases. + +For some methods, the first parameter can be modified. That includes the +possibility that you return a reference to a completely different object +instead. Although keeping the reference and just changing its contents is +preferred over creating and returning a different reference. + +Return values are always objects, strings, Perl scalars, or true/false for +comparison routines. + +=head2 API version 1 + +The following methods must be defined in order to support the use by +Math::BigInt v1.70 or later. + +=head3 API version + +=over 4 + +=item I<api_version()> + +Return API version as a Perl scalar, 1 for Math::BigInt v1.70, 2 for +Math::BigInt v1.83. + +=back + +=head3 Constructors + +=over 4 + +=item I<_new(STR)> + +Convert a string representing an unsigned decimal number to an object +representing the same number. The input is normalize, i.e., it matches +C<^(0|[1-9]\d*)$>. + +=item I<_zero()> + +Return an object representing the number zero. + +=item I<_one()> + +Return an object representing the number one. + +=item I<_two()> + +Return an object representing the number two. + +=item I<_ten()> + +Return an object representing the number ten. + +=item I<_from_bin(STR)> + +Return an object given a string representing a binary number. The input has a +'0b' prefix and matches the regular expression C<^0[bB](0|1[01]*)$>. + +=item I<_from_oct(STR)> + +Return an object given a string representing an octal number. The input has a +'0' prefix and matches the regular expression C<^0[1-7]*$>. + +=item I<_from_hex(STR)> + +Return an object given a string representing a hexadecimal number. The input +has a '0x' prefix and matches the regular expression +C<^0x(0|[1-9a-fA-F][\da-fA-F]*)$>. + +=back + +=head3 Mathematical functions + +Each of these methods may modify the first input argument, except I<_bgcd()>, +which shall not modify any input argument, and I<_sub()> which may modify the +second input argument. + +=over 4 + +=item I<_add(OBJ1, OBJ2)> + +Returns the result of adding OBJ2 to OBJ1. + +=item I<_mul(OBJ1, OBJ2)> + +Returns the result of multiplying OBJ2 and OBJ1. + +=item I<_div(OBJ1, OBJ2)> + +Returns the result of dividing OBJ1 by OBJ2 and truncating the result to an +integer. + +=item I<_sub(OBJ1, OBJ2, FLAG)> + +=item I<_sub(OBJ1, OBJ2)> + +Returns the result of subtracting OBJ2 by OBJ1. If C<flag> is false or omitted, +OBJ1 might be modified. If C<flag> is true, OBJ2 might be modified. + +=item I<_dec(OBJ)> + +Decrement OBJ by one. + +=item I<_inc(OBJ)> + +Increment OBJ by one. + +=item I<_mod(OBJ1, OBJ2)> + +Return OBJ1 modulo OBJ2, i.e., the remainder after dividing OBJ1 by OBJ2. + +=item I<_sqrt(OBJ)> + +Return the square root of the object, truncated to integer. + +=item I<_root(OBJ, N)> + +Return Nth root of the object, truncated to int. N is E<gt>= 3. + +=item I<_fac(OBJ)> + +Return factorial of object (1*2*3*4*...). + +=item I<_pow(OBJ1, OBJ2)> + +Return OBJ1 to the power of OBJ2. By convention, 0**0 = 1. + +=item I<_modinv(OBJ1, OBJ2)> + +Return modular multiplicative inverse, i.e., return OBJ3 so that + + (OBJ3 * OBJ1) % OBJ2 = 1 % OBJ2 + +The result is returned as two arguments. If the modular multiplicative +inverse does not exist, both arguments are undefined. Otherwise, the +arguments are a number (object) and its sign ("+" or "-"). + +The output value, with its sign, must either be a positive value in the +range 1,2,...,OBJ2-1 or the same value subtracted OBJ2. For instance, if the +input arguments are objects representing the numbers 7 and 5, the method +must either return an object representing the number 3 and a "+" sign, since +(3*7) % 5 = 1 % 5, or an object representing the number 2 and "-" sign, +since (-2*7) % 5 = 1 % 5. + +=item I<_modpow(OBJ1, OBJ2, OBJ3)> + +Return modular exponentiation, (OBJ1 ** OBJ2) % OBJ3. + +=item I<_rsft(OBJ, N, B)> + +Shift object N digits right in base B and return the resulting object. This is +equivalent to performing integer division by B**N and discarding the remainder, +except that it might be much faster, depending on how the number is represented +internally. + +For instance, if the object $obj represents the hexadecimal number 0xabcde, +then C<_rsft($obj, 2, 16)> returns an object representing the number 0xabc. The +"remainer", 0xde, is discarded and not returned. + +=item I<_lsft(OBJ, N, B)> + +Shift the object N digits left in base B. This is equivalent to multiplying by +B**N, except that it might be much faster, depending on how the number is +represented internally. + +=item I<_log_int(OBJ, B)> + +Return integer log of OBJ to base BASE. This method has two output arguments, +the OBJECT and a STATUS. The STATUS is Perl scalar; it is 1 if OBJ is the exact +result, 0 if the result was truncted to give OBJ, and undef if it is unknown +whether OBJ is the exact result. + +=item I<_gcd(OBJ1, OBJ2)> + +Return the greatest common divisor of OBJ1 and OBJ2. + +=back + +=head3 Bitwise operators + +Each of these methods may modify the first input argument. + +=over 4 + +=item I<_and(OBJ1, OBJ2)> + +Return bitwise and. If necessary, the smallest number is padded with leading +zeros. + +=item I<_or(OBJ1, OBJ2)> + +Return bitwise or. If necessary, the smallest number is padded with leading +zeros. + +=item I<_xor(OBJ1, OBJ2)> + +Return bitwise exclusive or. If necessary, the smallest number is padded +with leading zeros. + +=back + +=head3 Boolean operators + +=over 4 + +=item I<_is_zero(OBJ)> + +Returns a true value if OBJ is zero, and false value otherwise. + +=item I<_is_one(OBJ)> + +Returns a true value if OBJ is one, and false value otherwise. + +=item I<_is_two(OBJ)> + +Returns a true value if OBJ is two, and false value otherwise. + +=item I<_is_ten(OBJ)> + +Returns a true value if OBJ is ten, and false value otherwise. + +=item I<_is_even(OBJ)> + +Return a true value if OBJ is an even integer, and a false value otherwise. + +=item I<_is_odd(OBJ)> + +Return a true value if OBJ is an even integer, and a false value otherwise. + +=item I<_acmp(OBJ1, OBJ2)> + +Compare OBJ1 and OBJ2 and return -1, 0, or 1, if OBJ1 is less than, equal +to, or larger than OBJ2, respectively. + +=back + +=head3 String conversion + +=over 4 + +=item I<_str(OBJ)> + +Return a string representing the object. The returned string should have no +leading zeros, i.e., it should match C<^(0|[1-9]\d*)$>. + +=item I<_as_bin(OBJ)> + +Return the binary string representation of the number. The string must have a +'0b' prefix. + +=item I<_as_oct(OBJ)> + +Return the octal string representation of the number. The string must have +a '0x' prefix. + +Note: This method was required from Math::BigInt version 1.78, but the required +API version number was not incremented, so there are older libraries that +support API version 1, but do not support C<_as_oct()>. + +=item I<_as_hex(OBJ)> + +Return the hexadecimal string representation of the number. The string must +have a '0x' prefix. + +=back + +=head3 Numeric conversion + +=over 4 + +=item I<_num(OBJ)> + +Given an object, return a Perl scalar number (int/float) representing this +number. + +=back + +=head3 Miscellaneous + +=over 4 + +=item I<_copy(OBJ)> + +Return a true copy of the object. + +=item I<_len(OBJ)> + +Returns the number of the decimal digits in the number. The output is a +Perl scalar. + +=item I<_zeros(OBJ)> + +Return the number of trailing decimal zeros. The output is a Perl scalar. + +=item I<_digit(OBJ, N)> + +Return the Nth digit as a Perl scalar. N is a Perl scalar, where zero refers to +the rightmost (least significant) digit, and negative values count from the +left (most significant digit). If $obj represents the number 123, then +I<_digit($obj, 0)> is 3 and I<_digit(123, -1)> is 1. + +=item I<_check(OBJ)> + +Return a true value if the object is OK, and a false value otherwise. This is a +check routine to test the internal state of the object for corruption. + +=back + +=head2 API version 2 + +The following methods are required for an API version of 2 or greater. + +=head3 Constructors + +=over 4 + +=item I<_1ex(N)> + +Return an object representing the number 10**N where N E<gt>= 0 is a Perl +scalar. + +=back + +=head3 Mathematical functions + +=over 4 + +=item I<_nok(OBJ1, OBJ2)> + +Return the binomial coefficient OBJ1 over OBJ1. + +=back + +=head3 Miscellaneous + +=over 4 + +=item I<_alen(OBJ)> + +Return the approximate number of decimal digits of the object. The +output is one Perl scalar. This estimate must be greater than or equal +to what C<_len()> returns. + +=back + +=head2 API optional methods + +The following methods are optional, and can be defined if the underlying lib has a fast way to do them. If undefined, Math::BigInt will use pure Perl (hence slow) fallback routines to emulate these: - - _signed_or - _signed_and - _signed_xor -Input strings come in as unsigned but with prefix (i.e. as '123', '0xabc' -or '0b1101'). +=head3 Signed bitwise operators. -So the library needs only to deal with unsigned big integers. Testing of input -parameter validity is done by the caller, so you need not worry about -underflow (f.i. in C<_sub()>, C<_dec()>) nor about division by zero or similar -cases. +Each of these methods may modify the first input argument. -The first parameter can be modified, that includes the possibility that you -return a reference to a completely different object instead. Although keeping -the reference and just changing its contents is preferred over creating and -returning a different reference. +=over 4 -Return values are always references to objects, strings, or true/false for -comparison routines. +=item I<_signed_or(OBJ1, OBJ2, SIGN1, SIGN2)> + +Return the signed bitwise or. + +=item I<_signed_and(OBJ1, OBJ2, SIGN1, SIGN2)> + +Return the signed bitwise and. + +=item I<_signed_xor(OBJ1, OBJ2, SIGN1, SIGN2)> + +Return the signed bitwise exclusive or. + +=back =head1 WRAP YOUR OWN @@ -2592,18 +2934,34 @@ by this: This way you ensure that your library really works 100% within Math::BigInt. =head1 LICENSE - + This program is free software; you may redistribute it and/or modify it under the same terms as Perl itself. =head1 AUTHORS +=over 4 + +=item * + Original math code by Mark Biggar, rewritten by Tels L<http://bloodgate.com/> in late 2000. -Seperated from BigInt and shaped API with the help of John Peacock. + +=item * + +Separated from BigInt and shaped API with the help of John Peacock. + +=item * Fixed, speed-up, streamlined and enhanced by Tels 2001 - 2007. +=item * + +API documentation corrected and extended by Peter John Acklam, +E<lt>pjacklam@online.noE<gt> + +=back + =head1 SEE ALSO L<Math::BigInt>, L<Math::BigFloat>, |