From db2e1fb3c24129b0e583208b5ba375091b9dee6a Mon Sep 17 00:00:00 2001 From: pjacklam Date: Fri, 4 Feb 2011 18:02:51 -0800 Subject: [perl #83406] Library compatibility and API documentation (v1.991). - dist/Math-BigInt/lib/Math/BigFloat.pm: Increment version number. - dist/Math-BigInt/lib/Math/BigInt.pm: Add workaround for library inconsistencies (Math::BigInt::Calc vs. Math::BigInt::GMP). This makes older versions of Math::BigInt::GMP work with latest version of Math::BigInt. - dist/Math-BigInt/lib/Math/BigInt/Calc.pm: Correct and extend API documentation. Increment version number. - dist/Math-BigInt/lib/Math/BigInt/CalcEmu.pm: Increment version number. --- dist/Math-BigInt/lib/Math/BigFloat.pm | 2 +- dist/Math-BigInt/lib/Math/BigInt.pm | 7 +- dist/Math-BigInt/lib/Math/BigInt/Calc.pm | 531 +++++++++++++++++++++------- dist/Math-BigInt/lib/Math/BigInt/CalcEmu.pm | 2 +- 4 files changed, 415 insertions(+), 127 deletions(-) (limited to 'dist/Math-BigInt') diff --git a/dist/Math-BigInt/lib/Math/BigFloat.pm b/dist/Math-BigInt/lib/Math/BigFloat.pm index 83853c286a..20045a6459 100644 --- a/dist/Math-BigInt/lib/Math/BigFloat.pm +++ b/dist/Math-BigInt/lib/Math/BigFloat.pm @@ -12,7 +12,7 @@ package Math::BigFloat; # _a : accuracy # _p : precision -$VERSION = '1.99_04'; +$VERSION = '1.991'; require 5.006002; require Exporter; diff --git a/dist/Math-BigInt/lib/Math/BigInt.pm b/dist/Math-BigInt/lib/Math/BigInt.pm index 177894ab42..9ce39f45e4 100644 --- a/dist/Math-BigInt/lib/Math/BigInt.pm +++ b/dist/Math-BigInt/lib/Math/BigInt.pm @@ -18,7 +18,7 @@ package Math::BigInt; my $class = "Math::BigInt"; use 5.006002; -$VERSION = '1.99_05'; +$VERSION = '1.991'; @ISA = qw(Exporter); @EXPORT_OK = qw(objectify bgcd blcm); @@ -1835,6 +1835,11 @@ sub bmodinv ($x->{value}, $x->{sign}) = $CALC->_modinv($x->{value}, $y->{value}); return $x->bnan() if !defined $x->{value}; + # Library inconsistency workaround: _modinv() in Math::BigInt::GMP versions + # <= 1.32 return undef rather than a "+" for the sign. + + $x->{sign} = '+' unless defined $x->{sign}; + # When one or both arguments are negative, we have the following # relations. If x and y are positive: # diff --git a/dist/Math-BigInt/lib/Math/BigInt/Calc.pm b/dist/Math-BigInt/lib/Math/BigInt/Calc.pm index 2033cef996..e4c3e060d6 100644 --- a/dist/Math-BigInt/lib/Math/BigInt/Calc.pm +++ b/dist/Math-BigInt/lib/Math/BigInt/Calc.pm @@ -4,7 +4,7 @@ use 5.006002; use strict; # use warnings; # dont use warnings for older Perls -our $VERSION = '1.99_04'; +our $VERSION = '1.991'; # Package to store unsigned big integers in decimal and do math with them @@ -299,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) = @_; @@ -2440,148 +2440,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 + +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 is false or omitted, +OBJ1 might be modified. If C 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= 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= 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 +=head3 Signed bitwise operators. -Input strings come in as unsigned but with prefix (i.e. as '123', '0xabc' -or '0b1101'). +Each of these methods may modify the first input argument. -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. +=over 4 -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. +=item I<_signed_or(OBJ1, OBJ2, SIGN1, SIGN2)> -Return values are always references to objects, strings, or true/false for -comparison routines. +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 @@ -2605,12 +2872,28 @@ the same terms as Perl itself. =head1 AUTHORS +=over 4 + +=item * + Original math code by Mark Biggar, rewritten by Tels L in late 2000. + +=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, +Epjacklam@online.noE + +=back + =head1 SEE ALSO L, L, diff --git a/dist/Math-BigInt/lib/Math/BigInt/CalcEmu.pm b/dist/Math-BigInt/lib/Math/BigInt/CalcEmu.pm index cf2a76f029..810665d55f 100644 --- a/dist/Math-BigInt/lib/Math/BigInt/CalcEmu.pm +++ b/dist/Math-BigInt/lib/Math/BigInt/CalcEmu.pm @@ -5,7 +5,7 @@ use strict; # use warnings; # dont use warnings for older Perls use vars qw/$VERSION/; -$VERSION = '1.99_03'; +$VERSION = '1.991'; package Math::BigInt; -- cgit v1.2.1