<?php
/* vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4: */
/**
* Pure-PHP arbitrary precision integer arithmetic library.
*
* Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available,
* and an internal implementation, otherwise.
*
* PHP versions 4 and 5
*
* {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
* {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
*
* Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
* base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible
* value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
* point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
* used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
* which only supports integers. Although this fact will slow this library down, the fact that such a high
* base is being used should more than compensate.
*
* When PHP version 6 is officially released, we'll be able to use 64-bit integers. This should, once again,
* allow bitwise operators, and will increase the maximum possible base to 2**31 (or 2**62 for addition /
* subtraction).
*
* Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie.
* (new Math_BigInteger(pow(2, 26)))->value = array(0, 1)
*
* Useful resources are as follows:
*
* - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
* - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
* - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
*
* Here's an example of how to use this library:
* <code>
* <?php
* include('Math/BigInteger.php');
*
* $a = new Math_BigInteger(2);
* $b = new Math_BigInteger(3);
*
* $c = $a->add($b);
*
* echo $c->toString(); // outputs 5
* ?>
* </code>
*
* LICENSE: This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston,
* MA 02111-1307 USA
*
* @category Math
* @package Math_BigInteger
* @author Jim Wigginton <terrafrost@php.net>
* @copyright MMVI Jim Wigginton
* @license http://www.gnu.org/licenses/lgpl.txt
* @version $Id: BigInteger.php,v 1.33 2010/03/22 22:32:03 terrafrost Exp $
* @link http://pear.php.net/package/Math_BigInteger
*/
/**#@+
* Reduction constants
*
* @access private
* @see Math_BigInteger::_reduce()
*/
/**
* @see Math_BigInteger::_montgomery()
* @see Math_BigInteger::_prepMontgomery()
*/
define('MATH_BIGINTEGER_MONTGOMERY', 0);
/**
* @see Math_BigInteger::_barrett()
*/
define('MATH_BIGINTEGER_BARRETT', 1);
/**
* @see Math_BigInteger::_mod2()
*/
define('MATH_BIGINTEGER_POWEROF2', 2);
/**
* @see Math_BigInteger::_remainder()
*/
define('MATH_BIGINTEGER_CLASSIC', 3);
/**
* @see Math_BigInteger::__clone()
*/
define('MATH_BIGINTEGER_NONE', 4);
/**#@-*/
/**#@+
* Array constants
*
* Rather than create a thousands and thousands of new Math_BigInteger objects in repeated function calls to add() and
* multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
*
* @access private
*/
/**
* $result[MATH_BIGINTEGER_VALUE] contains the value.
*/
define('MATH_BIGINTEGER_VALUE', 0);
/**
* $result[MATH_BIGINTEGER_SIGN] contains the sign.
*/
define('MATH_BIGINTEGER_SIGN', 1);
/**#@-*/
/**#@+
* @access private
* @see Math_BigInteger::_montgomery()
* @see Math_BigInteger::_barrett()
*/
/**
* Cache constants
*
* $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
*/
define('MATH_BIGINTEGER_VARIABLE', 0);
/**
* $cache[MATH_BIGINTEGER_DATA] contains the cached data.
*/
define('MATH_BIGINTEGER_DATA', 1);
/**#@-*/
/**#@+
* Mode constants.
*
* @access private
* @see Math_BigInteger::Math_BigInteger()
*/
/**
* To use the pure-PHP implementation
*/
define('MATH_BIGINTEGER_MODE_INTERNAL', 1);
/**
* To use the BCMath library
*
* (if enabled; otherwise, the internal implementation will be used)
*/
define('MATH_BIGINTEGER_MODE_BCMATH', 2);
/**
* To use the GMP library
*
* (if present; otherwise, either the BCMath or the internal implementation will be used)
*/
define('MATH_BIGINTEGER_MODE_GMP', 3);
/**#@-*/
/**
* The largest digit that may be used in addition / subtraction
*
* (we do pow(2, 52) instead of using 4503599627370496, directly, because some PHP installations
* will truncate 4503599627370496)
*
* @access private
*/
define('MATH_BIGINTEGER_MAX_DIGIT52', pow(2, 52));
/**
* Karatsuba Cutoff
*
* At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
*
* @access private
*/
define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 25);
/**
* Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
* numbers.
*
* @author Jim Wigginton <terrafrost@php.net>
* @version 1.0.0RC4
* @access public
* @package Math_BigInteger
*/
class Math_BigInteger {
/**
* Holds the BigInteger's value.
*
* @var Array
* @access private
*/
var $value;
/**
* Holds the BigInteger's magnitude.
*
* @var Boolean
* @access private
*/
var $is_negative = false;
/**
* Random number generator function
*
* @see setRandomGenerator()
* @access private
*/
var $generator = 'mt_rand';
/**
* Precision
*
* @see setPrecision()
* @access private
*/
var $precision = -1;
/**
* Precision Bitmask
*
* @see setPrecision()
* @access private
*/
var $bitmask = false;
/**
* Mode independant value used for serialization.
*
* If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
* a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value,
* however, $this->hex is only calculated when $this->__sleep() is called.
*
* @see __sleep()
* @see __wakeup()
* @var String
* @access private
*/
var $hex;
/**
* Converts base-2, base-10, base-16, and binary strings (eg. base-256) to BigIntegers.
*
* If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
* two's compliment. The sole exception to this is -10, which is treated the same as 10 is.
*
* Here's an example:
* <code>
* <?php
* include('Math/BigInteger.php');
*
* $a = new Math_BigInteger('0x32', 16); // 50 in base-16
*
* echo $a->toString(); // outputs 50
* ?>
* </code>
*
* @param optional $x base-1
