diff options
Diffstat (limited to 'vendor/brick/math/src/Internal')
4 files changed, 1662 insertions, 0 deletions
diff --git a/vendor/brick/math/src/Internal/Calculator.php b/vendor/brick/math/src/Internal/Calculator.php new file mode 100644 index 0000000..a6eac79 --- /dev/null +++ b/vendor/brick/math/src/Internal/Calculator.php @@ -0,0 +1,756 @@ +<?php + +declare(strict_types=1); + +namespace Brick\Math\Internal; + +use Brick\Math\Exception\RoundingNecessaryException; +use Brick\Math\RoundingMode; + +/** + * Performs basic operations on arbitrary size integers. + * + * Unless otherwise specified, all parameters must be validated as non-empty strings of digits, + * without leading zero, and with an optional leading minus sign if the number is not zero. + * + * Any other parameter format will lead to undefined behaviour. + * All methods must return strings respecting this format, unless specified otherwise. + * + * @internal + * + * @psalm-immutable + */ +abstract class Calculator +{ + /** + * The maximum exponent value allowed for the pow() method. + */ + public const MAX_POWER = 1000000; + + /** + * The alphabet for converting from and to base 2 to 36, lowercase. + */ + public const ALPHABET = '0123456789abcdefghijklmnopqrstuvwxyz'; + + /** + * The Calculator instance in use. + * + * @var Calculator|null + */ + private static $instance; + + /** + * Sets the Calculator instance to use. + * + * An instance is typically set only in unit tests: the autodetect is usually the best option. + * + * @param Calculator|null $calculator The calculator instance, or NULL to revert to autodetect. + * + * @return void + */ + final public static function set(?Calculator $calculator) : void + { + self::$instance = $calculator; + } + + /** + * Returns the Calculator instance to use. + * + * If none has been explicitly set, the fastest available implementation will be returned. + * + * @return Calculator + * + * @psalm-pure + * @psalm-suppress ImpureStaticProperty + */ + final public static function get() : Calculator + { + if (self::$instance === null) { + /** @psalm-suppress ImpureMethodCall */ + self::$instance = self::detect(); + } + + return self::$instance; + } + + /** + * Returns the fastest available Calculator implementation. + * + * @codeCoverageIgnore + * + * @return Calculator + */ + private static function detect() : Calculator + { + if (\extension_loaded('gmp')) { + return new Calculator\GmpCalculator(); + } + + if (\extension_loaded('bcmath')) { + return new Calculator\BcMathCalculator(); + } + + return new Calculator\NativeCalculator(); + } + + /** + * Extracts the sign & digits of the operands. + * + * @param string $a The first operand. + * @param string $b The second operand. + * + * @return array{bool, bool, string, string} Whether $a and $b are negative, followed by their digits. + */ + final protected function init(string $a, string $b) : array + { + return [ + $aNeg = ($a[0] === '-'), + $bNeg = ($b[0] === '-'), + + $aNeg ? \substr($a, 1) : $a, + $bNeg ? \substr($b, 1) : $b, + ]; + } + + /** + * Returns the absolute value of a number. + * + * @param string $n The number. + * + * @return string The absolute value. + */ + final public function abs(string $n) : string + { + return ($n[0] === '-') ? \substr($n, 1) : $n; + } + + /** + * Negates a number. + * + * @param string $n The number. + * + * @return string The negated value. + */ + final public function neg(string $n) : string + { + if ($n === '0') { + return '0'; + } + + if ($n[0] === '-') { + return \substr($n, 1); + } + + return '-' . $n; + } + + /** + * Compares two numbers. + * + * @param string $a The first number. + * @param string $b The second number. + * + * @return int [-1, 0, 1] If the first number is less than, equal to, or greater than the second number. + */ + final public function cmp(string $a, string $b) : int + { + [$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b); + + if ($aNeg && ! $bNeg) { + return -1; + } + + if ($bNeg && ! $aNeg) { + return 1; + } + + $aLen = \strlen($aDig); + $bLen = \strlen($bDig); + + if ($aLen < $bLen) { + $result = -1; + } elseif ($aLen > $bLen) { + $result = 1; + } else { + $result = $aDig <=> $bDig; + } + + return $aNeg ? -$result : $result; + } + + /** + * Adds two numbers. + * + * @param string $a The augend. + * @param string $b The addend. + * + * @return string The sum. + */ + abstract public function add(string $a, string $b) : string; + + /** + * Subtracts two numbers. + * + * @param string $a The minuend. + * @param string $b The subtrahend. + * + * @return string The difference. + */ + abstract public function sub(string $a, string $b) : string; + + /** + * Multiplies two numbers. + * + * @param string $a The multiplicand. + * @param string $b The multiplier. + * + * @return string The product. + */ + abstract public function mul(string $a, string $b) : string; + + /** + * Returns the quotient of the division of two numbers. + * + * @param string $a The dividend. + * @param string $b The divisor, must not be zero. + * + * @return string The quotient. + */ + abstract public function divQ(string $a, string $b) : string; + + /** + * Returns the remainder of the division of two numbers. + * + * @param string $a The dividend. + * @param string $b The divisor, must not be zero. + * + * @return string The remainder. + */ + abstract public function divR(string $a, string $b) : string; + + /** + * Returns the quotient and remainder of the division of two numbers. + * + * @param string $a The dividend. + * @param string $b The divisor, must not be zero. + * + * @return string[] An array containing the quotient and remainder. + */ + abstract public function divQR(string $a, string $b) : array; + + /** + * Exponentiates a number. + * + * @param string $a The base number. + * @param int $e The exponent, validated as an integer between 0 and MAX_POWER. + * + * @return string The power. + */ + abstract public function pow(string $a, int $e) : string; + + /** + * @param string $a + * @param string $b The modulus; must not be zero. + * + * @return string + */ + public function mod(string $a, string $b) : string + { + return $this->divR($this->add($this->divR($a, $b), $b), $b); + } + + /** + * Returns the modular multiplicative inverse of $x modulo $m. + * + * If $x has no multiplicative inverse mod m, this method must return null. + * + * This method can be overridden by the concrete implementation if the underlying library has built-in support. + * + * @param string $x + * @param string $m The modulus; must not be negative or zero. + * + * @return string|null + */ + public function modInverse(string $x, string $m) : ?string + { + if ($m === '1') { + return '0'; + } + + $modVal = $x; + + if ($x[0] === '-' || ($this->cmp($this->abs($x), $m) >= 0)) { + $modVal = $this->mod($x, $m); + } + + $x = '0'; + $y = '0'; + $g = $this->gcdExtended($modVal, $m, $x, $y); + + if ($g !== '1') { + return null; + } + + return $this->mod($this->add($this->mod($x, $m), $m), $m); + } + + /** + * Raises a number into power with modulo. + * + * @param string $base The base number; must be positive or zero. + * @param string $exp The exponent; must be positive or zero. + * @param string $mod The modulus; must be strictly positive. + * + * @return string The power. + */ + abstract public function modPow(string $base, string $exp, string $mod) : string; + + /** + * Returns the greatest common divisor of the two numbers. + * + * This method can be overridden by the concrete implementation if the underlying library + * has built-in support for GCD calculations. + * + * @param string $a The first number. + * @param string $b The second number. + * + * @return string The GCD, always positive, or zero if both arguments are zero. + */ + public function gcd(string $a, string $b) : string + { + if ($a === '0') { + return $this->abs($b); + } + + if ($b === '0') { + return $this->abs($a); + } + + return $this->gcd($b, $this->divR($a, $b)); + } + + private function gcdExtended(string $a, string $b, string &$x, string &$y) : string + { + if ($a === '0') { + $x = '0'; + $y = '1'; + + return $b; + } + + $x1 = '0'; + $y1 = '0'; + + $gcd = $this->gcdExtended($this->mod($b, $a), $a, $x1, $y1); + + $x = $this->sub($y1, $this->mul($this->divQ($b, $a), $x1)); + $y = $x1; + + return $gcd; + } + + /** + * Returns the square root of the given number, rounded down. + * + * The result is the largest x such that x² ≤ n. + * The input MUST NOT be negative. + * + * @param string $n The number. + * + * @return string The square root. + */ + abstract public function sqrt(string $n) : string; + + /** + * Converts a number from an arbitrary base. + * + * This method can be overridden by the concrete implementation if the underlying library + * has built-in support for base conversion. + * + * @param string $number The number, positive or zero, non-empty, case-insensitively validated for the given base. + * @param int $base The base of the number, validated from 2 to 36. + * + * @return string The converted number, following the Calculator conventions. + */ + public function fromBase(string $number, int $base) : string + { + return $this->fromArbitraryBase(\strtolower($number), self::ALPHABET, $base); + } + + /** + * Converts a number to an arbitrary base. + * + * This method can be overridden by the concrete implementation if the underlying library + * has built-in support for base conversion. + * + * @param string $number The number to convert, following the Calculator conventions. + * @param int $base The base to convert to, validated from 2 to 36. + * + * @return string The converted number, lowercase. + */ + public function toBase(string $number, int $base) : string + { + $negative = ($number[0] === '-'); + + if ($negative) { + $number = \substr($number, 1); + } + + $number = $this->toArbitraryBase($number, self::ALPHABET, $base); + + if ($negative) { + return '-' . $number; + } + + return $number; + } + + /** + * Converts a non-negative number in an arbitrary base using a custom alphabet, to base 10. + * + * @param string $number The number to convert, validated as a non-empty string, + * containing only chars in the given alphabet/base. + * @param string $alphabet The alphabet that contains every digit, validated as 2 chars minimum. + * @param int $base The base of the number, validated from 2 to alphabet length. + * + * @return string The number in base 10, following the Calculator conventions. + */ + final public function fromArbitraryBase(string $number, string $alphabet, int $base) : string + { + // remove leading "zeros" + $number = \ltrim($number, $alphabet[0]); + + if ($number === '') { + return '0'; + } + + // optimize for "one" + if ($number === $alphabet[1]) { + return '1'; + } + + $result = '0'; + $power = '1'; + + $base = (string) $base; + + for ($i = \strlen($number) - 1; $i >= 0; $i--) { + $index = \strpos($alphabet, $number[$i]); + + if ($index !== 0) { + $result = $this->add($result, ($index === 1) + ? $power + : $this->mul($power, (string) $index) + ); + } + + if ($i !== 0) { + $power = $this->mul($power, $base); + } + } + + return $result; + } + + /** + * Converts a non-negative number to an arbitrary base using a custom alphabet. + * + * @param string $number The number to convert, positive or zero, following the Calculator conventions. + * @param string $alphabet The alphabet that contains every digit, validated as 2 chars minimum. + * @param int $base The base to convert to, validated from 2 to alphabet length. + * + * @return string The converted number in the given alphabet. + */ + final public function toArbitraryBase(string $number, string $alphabet, int $base) : string + { + if ($number === '0') { + return $alphabet[0]; + } + + $base = (string) $base; + $result = ''; + + while ($number !== '0') { + [$number, $remainder] = $this->divQR($number, $base); + $remainder = (int) $remainder; + + $result .= $alphabet[$remainder]; + } + + return \strrev($result); + } + + /** + * Performs a rounded division. + * + * Rounding is performed when the remainder of the division is not zero. + * + * @param string $a The dividend. + * @param string $b The divisor, must not be zero. + * @param int $roundingMode The rounding mode. + * + * @return string + * + * @throws \InvalidArgumentException If the rounding mode is invalid. + * @throws RoundingNecessaryException If RoundingMode::UNNECESSARY is provided but rounding is necessary. + */ + final public function divRound(string $a, string $b, int $roundingMode) : string + { + [$quotient, $remainder] = $this->divQR($a, $b); + + $hasDiscardedFraction = ($remainder !== '0'); + $isPositiveOrZero = ($a[0] === '-') === ($b[0] === '-'); + + $discardedFractionSign = function() use ($remainder, $b) : int { + $r = $this->abs($this->mul($remainder, '2')); + $b = $this->abs($b); + + return $this->cmp($r, $b); + }; + + $increment = false; + + switch ($roundingMode) { + case RoundingMode::UNNECESSARY: + if ($hasDiscardedFraction) { + throw RoundingNecessaryException::roundingNecessary(); + } + break; + + case RoundingMode::UP: + $increment = $hasDiscardedFraction; + break; + + case RoundingMode::DOWN: + break; + + case RoundingMode::CEILING: + $increment = $hasDiscardedFraction && $isPositiveOrZero; + break; + + case RoundingMode::FLOOR: + $increment = $hasDiscardedFraction && ! $isPositiveOrZero; + break; + + case RoundingMode::HALF_UP: + $increment = $discardedFractionSign() >= 0; + break; + + case RoundingMode::HALF_DOWN: + $increment = $discardedFractionSign() > 0; + break; + + case RoundingMode::HALF_CEILING: + $increment = $isPositiveOrZero ? $discardedFractionSign() >= 0 : $discardedFractionSign() > 0; + break; + + case RoundingMode::HALF_FLOOR: + $increment = $isPositiveOrZero ? $discardedFractionSign() > 0 : $discardedFractionSign() >= 0; + break; + + case RoundingMode::HALF_EVEN: + $lastDigit = (int) $quotient[-1]; + $lastDigitIsEven = ($lastDigit % 2 === 0); + $increment = $lastDigitIsEven ? $discardedFractionSign() > 0 : $discardedFractionSign() >= 0; + break; + + default: + throw new \InvalidArgumentException('Invalid rounding mode.'); + } + + if ($increment) { + return $this->add($quotient, $isPositiveOrZero ? '1' : '-1'); + } + + return $quotient; + } + + /** + * Calculates bitwise AND of two numbers. + * + * This method can be overridden by the concrete implementation if the underlying library + * has built-in support for bitwise operations. + * + * @param string $a + * @param string $b + * + * @return string + */ + public function and(string $a, string $b) : string + { + return $this->bitwise('and', $a, $b); + } + + /** + * Calculates bitwise OR of two numbers. + * + * This method can be overridden by the concrete implementation if the underlying library + * has built-in support for bitwise operations. + * + * @param string $a + * @param string $b + * + * @return string + */ + public function or(string $a, string $b) : string + { + return $this->bitwise('or', $a, $b); + } + + /** + * Calculates bitwise XOR of two numbers. + * + * This method can be overridden by the concrete implementation if the underlying library + * has built-in support for bitwise operations. + * + * @param string $a + * @param string $b + * + * @return string + */ + public function xor(string $a, string $b) : string + { + return $this->bitwise('xor', $a, $b); + } + + /** + * Performs a bitwise operation on a decimal number. + * + * @param string $operator The operator to use, must be "and", "or" or "xor". + * @param string $a The left operand. + * @param string $b The right operand. + * + * @return string + */ + private function bitwise(string $operator, string $a, string $b) : string + { + [$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b); + + $aBin = $this->toBinary($aDig); + $bBin = $this->toBinary($bDig); + + $aLen = \strlen($aBin); + $bLen = \strlen($bBin); + + if ($aLen > $bLen) { + $bBin = \str_repeat("\x00", $aLen - $bLen) . $bBin; + } elseif ($bLen > $aLen) { + $aBin = \str_repeat("\x00", $bLen - $aLen) . $aBin; + } + + if ($aNeg) { + $aBin = $this->twosComplement($aBin); + } + if ($bNeg) { + $bBin = $this->twosComplement($bBin); + } + + switch ($operator) { + case 'and': + $value = $aBin & $bBin; + $negative = ($aNeg and $bNeg); + break; + + case 'or': + $value = $aBin | $bBin; + $negative = ($aNeg or $bNeg); + break; + + case 'xor': + $value = $aBin ^ $bBin; + $negative = ($aNeg xor $bNeg); + break; + + // @codeCoverageIgnoreStart + default: + throw new \InvalidArgumentException('Invalid bitwise operator.'); + // @codeCoverageIgnoreEnd + } + + if ($negative) { + $value = $this->twosComplement($value); + } + + $result = $this->toDecimal($value); + + return $negative ? $this->neg($result) : $result; + } + + /** + * @param string $number A positive, binary number. + * + * @return string + */ + private function twosComplement(string $number) : string + { + $xor = \str_repeat("\xff", \strlen($number)); + + $number ^= $xor; + + for ($i = \strlen($number) - 1; $i >= 0; $i--) { + $byte = \ord($number[$i]); + + if (++$byte !== 256) { + $number[$i] = \chr($byte); + break; + } + + $number[$i] = "\x00"; + + if ($i === 0) { + $number = "\x01" . $number; + } + } + + return $number; + } + + /** + * Converts a decimal number to a binary string. + * + * @param string $number The number to convert, positive or zero, only digits. + * + * @return string + */ + private function toBinary(string $number) : string + { + $result = ''; + + while ($number !== '0') { + [$number, $remainder] = $this->divQR($number, '256'); + $result .= \chr((int) $remainder); + } + + return \strrev($result); + } + + /** + * Returns the positive decimal representation of a binary number. + * + * @param string $bytes The bytes representing the number. + * + * @return string + */ + private function toDecimal(string $bytes) : string + { + $result = '0'; + $power = '1'; + + for ($i = \strlen($bytes) - 1; $i >= 0; $i--) { + $index = \ord($bytes[$i]); + + if ($index !== 0) { + $result = $this->add($result, ($index === 1) + ? $power + : $this->mul($power, (string) $index) + ); + } + + if ($i !== 0) { + $power = $this->mul($power, '256'); + } + } + + return $result; + } +} diff --git a/vendor/brick/math/src/Internal/Calculator/BcMathCalculator.php b/vendor/brick/math/src/Internal/Calculator/BcMathCalculator.php new file mode 100644 index 0000000..6632b37 --- /dev/null +++ b/vendor/brick/math/src/Internal/Calculator/BcMathCalculator.php @@ -0,0 +1,116 @@ +<?php + +declare(strict_types=1); + +namespace Brick\Math\Internal\Calculator; + +use Brick\Math\Internal\Calculator; + +/** + * Calculator implementation built around the bcmath library. + * + * @internal + * + * @psalm-immutable + */ +class BcMathCalculator extends Calculator +{ + /** + * {@inheritdoc} + */ + public function add(string $a, string $b) : string + { + return \bcadd($a, $b, 0); + } + + /** + * {@inheritdoc} + */ + public function sub(string $a, string $b) : string + { + return \bcsub($a, $b, 0); + } + + /** + * {@inheritdoc} + */ + public function mul(string $a, string $b) : string + { + return \bcmul($a, $b, 0); + } + + /** + * {@inheritdoc} + * + * @psalm-suppress InvalidNullableReturnType + * @psalm-suppress NullableReturnStatement + */ + public function divQ(string $a, string $b) : string + { + return \bcdiv($a, $b, 0); + } + + /** + * {@inheritdoc} + * + * @psalm-suppress InvalidNullableReturnType + * @psalm-suppress NullableReturnStatement + */ + public function divR(string $a, string $b) : string + { + if (version_compare(PHP_VERSION, '7.2') >= 0) { + return \bcmod($a, $b, 0); + } + + return \bcmod($a, $b); + } + + /** + * {@inheritdoc} + */ + public function divQR(string $a, string $b) : array + { + $q = \bcdiv($a, $b, 0); + + if (version_compare(PHP_VERSION, '7.2') >= 0) { + $r = \bcmod($a, $b, 0); + } else { + $r = \bcmod($a, $b); + } + + assert($q !== null); + assert($r !== null); + + return [$q, $r]; + } + + /** + * {@inheritdoc} + */ + public function pow(string $a, int $e) : string + { + return \bcpow($a, (string) $e, 0); + } + + /** + * {@inheritdoc} + * + * @psalm-suppress InvalidNullableReturnType + * @psalm-suppress NullableReturnStatement + */ + public function modPow(string $base, string $exp, string $mod) : string + { + return \bcpowmod($base, $exp, $mod, 0); + } + + /** + * {@inheritDoc} + * + * @psalm-suppress NullableReturnStatement + * @psalm-suppress InvalidNullableReturnType + */ + public function sqrt(string $n) : string + { + return \bcsqrt($n, 0); + } +} diff --git a/vendor/brick/math/src/Internal/Calculator/GmpCalculator.php b/vendor/brick/math/src/Internal/Calculator/GmpCalculator.php new file mode 100644 index 0000000..52d1880 --- /dev/null +++ b/vendor/brick/math/src/Internal/Calculator/GmpCalculator.php @@ -0,0 +1,156 @@ +<?php + +declare(strict_types=1); + +namespace Brick\Math\Internal\Calculator; + +use Brick\Math\Internal\Calculator; + +/** + * Calculator implementation built around the GMP library. + * + * @internal + * + * @psalm-immutable + */ +class GmpCalculator extends Calculator +{ + /** + * {@inheritdoc} + */ + public function add(string $a, string $b) : string + { + return \gmp_strval(\gmp_add($a, $b)); + } + + /** + * {@inheritdoc} + */ + public function sub(string $a, string $b) : string + { + return \gmp_strval(\gmp_sub($a, $b)); + } + + /** + * {@inheritdoc} + */ + public function mul(string $a, string $b) : string + { + return \gmp_strval(\gmp_mul($a, $b)); + } + + /** + * {@inheritdoc} + */ + public function divQ(string $a, string $b) : string + { + return \gmp_strval(\gmp_div_q($a, $b)); + } + + /** + * {@inheritdoc} + */ + public function divR(string $a, string $b) : string + { + return \gmp_strval(\gmp_div_r($a, $b)); + } + + /** + * {@inheritdoc} + */ + public function divQR(string $a, string $b) : array + { + [$q, $r] = \gmp_div_qr($a, $b); + + return [ + \gmp_strval($q), + \gmp_strval($r) + ]; + } + + /** + * {@inheritdoc} + */ + public function pow(string $a, int $e) : string + { + return \gmp_strval(\gmp_pow($a, $e)); + } + + /** + * {@inheritdoc} + */ + public function modInverse(string $x, string $m) : ?string + { + $result = \gmp_invert($x, $m); + + if ($result === false) { + return null; + } + + return \gmp_strval($result); + } + + /** + * {@inheritdoc} + */ + public function modPow(string $base, string $exp, string $mod) : string + { + return \gmp_strval(\gmp_powm($base, $exp, $mod)); + } + + /** + * {@inheritdoc} + */ + public function gcd(string $a, string $b) : string + { + return \gmp_strval(\gmp_gcd($a, $b)); + } + + /** + * {@inheritdoc} + */ + public function fromBase(string $number, int $base) : string + { + return \gmp_strval(\gmp_init($number, $base)); + } + + /** + * {@inheritdoc} + */ + public function toBase(string $number, int $base) : string + { + return \gmp_strval($number, $base); + } + + /** + * {@inheritdoc} + */ + public function and(string $a, string $b) : string + { + return \gmp_strval(\gmp_and($a, $b)); + } + + /** + * {@inheritdoc} + */ + public function or(string $a, string $b) : string + { + return \gmp_strval(\gmp_or($a, $b)); + } + + /** + * {@inheritdoc} + */ + public function xor(string $a, string $b) : string + { + return \gmp_strval(\gmp_xor($a, $b)); + } + + /** + * {@inheritDoc} + */ + public function sqrt(string $n) : string + { + return \gmp_strval(\gmp_sqrt($n)); + } +} diff --git a/vendor/brick/math/src/Internal/Calculator/NativeCalculator.php b/vendor/brick/math/src/Internal/Calculator/NativeCalculator.php new file mode 100644 index 0000000..020a633 --- /dev/null +++ b/vendor/brick/math/src/Internal/Calculator/NativeCalculator.php @@ -0,0 +1,634 @@ +<?php + +declare(strict_types=1); + +namespace Brick\Math\Internal\Calculator; + +use Brick\Math\Internal\Calculator; + +/** + * Calculator implementation using only native PHP code. + * + * @internal + * + * @psalm-immutable + */ +class NativeCalculator extends Calculator +{ + /** + * The max number of digits the platform can natively add, subtract, multiply or divide without overflow. + * For multiplication, this represents the max sum of the lengths of both operands. + * + * For addition, it is assumed that an extra digit can hold a carry (1) without overflowing. + * Example: 32-bit: max number 1,999,999,999 (9 digits + carry) + * 64-bit: max number 1,999,999,999,999,999,999 (18 digits + carry) + * + * @var int + */ + private $maxDigits; + + /** + * Class constructor. + * + * @codeCoverageIgnore + */ + public function __construct() + { + switch (PHP_INT_SIZE) { + case 4: + $this->maxDigits = 9; + break; + + case 8: + $this->maxDigits = 18; + break; + + default: + throw new \RuntimeException('The platform is not 32-bit or 64-bit as expected.'); + } + } + + /** + * {@inheritdoc} + */ + public function add(string $a, string $b) : string + { + /** + * @psalm-var numeric-string $a + * @psalm-var numeric-string $b + */ + $result = $a + $b; + + if (is_int($result)) { + return (string) $result; + } + + if ($a === '0') { + return $b; + } + + if ($b === '0') { + return $a; + } + + [$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b); + + $result = $aNeg === $bNeg ? $this->doAdd($aDig, $bDig) : $this->doSub($aDig, $bDig); + + if ($aNeg) { + $result = $this->neg($result); + } + + return $result; + } + + /** + * {@inheritdoc} + */ + public function sub(string $a, string $b) : string + { + return $this->add($a, $this->neg($b)); + } + + /** + * {@inheritdoc} + */ + public function mul(string $a, string $b) : string + { + /** + * @psalm-var numeric-string $a + * @psalm-var numeric-string $b + */ + $result = $a * $b; + + if (is_int($result)) { + return (string) $result; + } + + if ($a === '0' || $b === '0') { + return '0'; + } + + if ($a === '1') { + return $b; + } + + if ($b === '1') { + return $a; + } + + if ($a === '-1') { + return $this->neg($b); + } + + if ($b === '-1') { + return $this->neg($a); + } + + [$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b); + + $result = $this->doMul($aDig, $bDig); + + if ($aNeg !== $bNeg) { + $result = $this->neg($result); + } + + return $result; + } + + /** + * {@inheritdoc} + */ + public function divQ(string $a, string $b) : string + { + return $this->divQR($a, $b)[0]; + } + + /** + * {@inheritdoc} + */ + public function divR(string $a, string $b): string + { + return $this->divQR($a, $b)[1]; + } + + /** + * {@inheritdoc} + */ + public function divQR(string $a, string $b) : array + { + if ($a === '0') { + return ['0', '0']; + } + + if ($a === $b) { + return ['1', '0']; + } + + if ($b === '1') { + return [$a, '0']; + } + + if ($b === '-1') { + return [$this->neg($a), '0']; + } + + /** @psalm-var numeric-string $a */ + $na = $a * 1; // cast to number + + if (is_int($na)) { + /** @psalm-var numeric-string $b */ + $nb = $b * 1; + + if (is_int($nb)) { + // the only division that may overflow is PHP_INT_MIN / -1, + // which cannot happen here as we've already handled a divisor of -1 above. + $r = $na % $nb; + $q = ($na - $r) / $nb; + + assert(is_int($q)); + + return [ + (string) $q, + (string) $r + ]; + } + } + + [$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b); + + [$q, $r] = $this->doDiv($aDig, $bDig); + + if ($aNeg !== $bNeg) { + $q = $this->neg($q); + } + + if ($aNeg) { + $r = $this->neg($r); + } + + return [$q, $r]; + } + + /** + * {@inheritdoc} + */ + public function pow(string $a, int $e) : string + { + if ($e === 0) { + return '1'; + } + + if ($e === 1) { + return $a; + } + + $odd = $e % 2; + $e -= $odd; + + $aa = $this->mul($a, $a); + + /** @psalm-suppress PossiblyInvalidArgument We're sure that $e / 2 is an int now */ + $result = $this->pow($aa, $e / 2); + + if ($odd === 1) { + $result = $this->mul($result, $a); + } + + return $result; + } + + /** + * Algorithm from: https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/ + * + * {@inheritdoc} + */ + public function modPow(string $base, string $exp, string $mod) : string + { + // special case: the algorithm below fails with 0 power 0 mod 1 (returns 1 instead of 0) + if ($base === '0' && $exp === '0' && $mod === '1') { + return '0'; + } + + // special case: the algorithm below fails with power 0 mod 1 (returns 1 instead of 0) + if ($exp === '0' && $mod === '1') { + return '0'; + } + + $x = $base; + + $res = '1'; + + // numbers are positive, so we can use remainder instead of modulo + $x = $this->divR($x, $mod); + + while ($exp !== '0') { + if (in_array($exp[-1], ['1', '3', '5', '7', '9'])) { // odd + $res = $this->divR($this->mul($res, $x), $mod); + } + + $exp = $this->divQ($exp, '2'); + $x = $this->divR($this->mul($x, $x), $mod); + } + + return $res; + } + + /** + * Adapted from https://cp-algorithms.com/num_methods/roots_newton.html + * + * {@inheritDoc} + */ + public function sqrt(string $n) : string + { + if ($n === '0') { + return '0'; + } + + // initial approximation + $x = \str_repeat('9', \intdiv(\strlen($n), 2) ?: 1); + + $decreased = false; + + for (;;) { + $nx = $this->divQ($this->add($x, $this->divQ($n, $x)), '2'); + + if ($x === $nx || $this->cmp($nx, $x) > 0 && $decreased) { + break; + } + + $decreased = $this->cmp($nx, $x) < 0; + $x = $nx; + } + + return $x; + } + + /** + * Performs the addition of two non-signed large integers. + * + * @param string $a The first operand. + * @param string $b The second operand. + * + * @return string + */ + private function doAdd(string $a, string $b) : string + { + [$a, $b, $length] = $this->pad($a, $b); + + $carry = 0; + $result = ''; + + for ($i = $length - $this->maxDigits;; $i -= $this->maxDigits) { + $blockLength = $this->maxDigits; + + if ($i < 0) { + $blockLength += $i; + /** @psalm-suppress LoopInvalidation */ + $i = 0; + } + + /** @psalm-var numeric-string $blockA */ + $blockA = \substr($a, $i, $blockLength); + + /** @psalm-var numeric-string $blockB */ + $blockB = \substr($b, $i, $blockLength); + + $sum = (string) ($blockA + $blockB + $carry); + $sumLength = \strlen($sum); + + if ($sumLength > $blockLength) { + $sum = \substr($sum, 1); + $carry = 1; + } else { + if ($sumLength < $blockLength) { + $sum = \str_repeat('0', $blockLength - $sumLength) . $sum; + } + $carry = 0; + } + + $result = $sum . $result; + + if ($i === 0) { + break; + } + } + + if ($carry === 1) { + $result = '1' . $result; + } + + return $result; + } + + /** + * Performs the subtraction of two non-signed large integers. + * + * @param string $a The first operand. + * @param string $b The second operand. + * + * @return string + */ + private function doSub(string $a, string $b) : string + { + if ($a === $b) { + return '0'; + } + + // Ensure that we always subtract to a positive result: biggest minus smallest. + $cmp = $this->doCmp($a, $b); + + $invert = ($cmp === -1); + + if ($invert) { + $c = $a; + $a = $b; + $b = $c; + } + + [$a, $b, $length] = $this->pad($a, $b); + + $carry = 0; + $result = ''; + + $complement = 10 ** $this->maxDigits; + + for ($i = $length - $this->maxDigits;; $i -= $this->maxDigits) { + $blockLength = $this->maxDigits; + + if ($i < 0) { + $blockLength += $i; + /** @psalm-suppress LoopInvalidation */ + $i = 0; + } + + /** @psalm-var numeric-string $blockA */ + $blockA = \substr($a, $i, $blockLength); + + /** @psalm-var numeric-string $blockB */ + $blockB = \substr($b, $i, $blockLength); + + $sum = $blockA - $blockB - $carry; + + if ($sum < 0) { + $sum += $complement; + $carry = 1; + } else { + $carry = 0; + } + + $sum = (string) $sum; + $sumLength = \strlen($sum); + + if ($sumLength < $blockLength) { + $sum = \str_repeat('0', $blockLength - $sumLength) . $sum; + } + + $result = $sum . $result; + + if ($i === 0) { + break; + } + } + + // Carry cannot be 1 when the loop ends, as a > b + assert($carry === 0); + + $result = \ltrim($result, '0'); + + if ($invert) { + $result = $this->neg($result); + } + + return $result; + } + + /** + * Performs the multiplication of two non-signed large integers. + * + * @param string $a The first operand. + * @param string $b The second operand. + * + * @return string + */ + private function doMul(string $a, string $b) : string + { + $x = \strlen($a); + $y = \strlen($b); + + $maxDigits = \intdiv($this->maxDigits, 2); + $complement = 10 ** $maxDigits; + + $result = '0'; + + for ($i = $x - $maxDigits;; $i -= $maxDigits) { + $blockALength = $maxDigits; + + if ($i < 0) { + $blockALength += $i; + /** @psalm-suppress LoopInvalidation */ + $i = 0; + } + + $blockA = (int) \substr($a, $i, $blockALength); + + $line = ''; + $carry = 0; + + for ($j = $y - $maxDigits;; $j -= $maxDigits) { + $blockBLength = $maxDigits; + + if ($j < 0) { + $blockBLength += $j; + /** @psalm-suppress LoopInvalidation */ + $j = 0; + } + + $blockB = (int) \substr($b, $j, $blockBLength); + + $mul = $blockA * $blockB + $carry; + $value = $mul % $complement; + $carry = ($mul - $value) / $complement; + + $value = (string) $value; + $value = \str_pad($value, $maxDigits, '0', STR_PAD_LEFT); + + $line = $value . $line; + + if ($j === 0) { + break; + } + } + + if ($carry !== 0) { + $line = $carry . $line; + } + + $line = \ltrim($line, '0'); + + if ($line !== '') { + $line .= \str_repeat('0', $x - $blockALength - $i); + $result = $this->add($result, $line); + } + + if ($i === 0) { + break; + } + } + + return $result; + } + + /** + * Performs the division of two non-signed large integers. + * + * @param string $a The first operand. + * @param string $b The second operand. + * + * @return string[] The quotient and remainder. + */ + private function doDiv(string $a, string $b) : array + { + $cmp = $this->doCmp($a, $b); + + if ($cmp === -1) { + return ['0', $a]; + } + + $x = \strlen($a); + $y = \strlen($b); + + // we now know that a >= b && x >= y + + $q = '0'; // quotient + $r = $a; // remainder + $z = $y; // focus length, always $y or $y+1 + + for (;;) { + $focus = \substr($a, 0, $z); + + $cmp = $this->doCmp($focus, $b); + + if ($cmp === -1) { + if ($z === $x) { // remainder < dividend + break; + } + + $z++; + } + + $zeros = \str_repeat('0', $x - $z); + + $q = $this->add($q, '1' . $zeros); + $a = $this->sub($a, $b . $zeros); + + $r = $a; + + if ($r === '0') { // remainder == 0 + break; + } + + $x = \strlen($a); + + if ($x < $y) { // remainder < dividend + break; + } + + $z = $y; + } + + return [$q, $r]; + } + + /** + * Compares two non-signed large numbers. + * + * @param string $a The first operand. + * @param string $b The second operand. + * + * @return int [-1, 0, 1] + */ + private function doCmp(string $a, string $b) : int + { + $x = \strlen($a); + $y = \strlen($b); + + $cmp = $x <=> $y; + + if ($cmp !== 0) { + return $cmp; + } + + return \strcmp($a, $b) <=> 0; // enforce [-1, 0, 1] + } + + /** + * Pads the left of one of the given numbers with zeros if necessary to make both numbers the same length. + * + * The numbers must only consist of digits, without leading minus sign. + * + * @param string $a The first operand. + * @param string $b The second operand. + * + * @return array{string, string, int} + */ + private function pad(string $a, string $b) : array + { + $x = \strlen($a); + $y = \strlen($b); + + if ($x > $y) { + $b = \str_repeat('0', $x - $y) . $b; + + return [$a, $b, $x]; + } + + if ($x < $y) { + $a = \str_repeat('0', $y - $x) . $a; + + return [$a, $b, $y]; + } + + return [$a, $b, $x]; + } +} |