Subversion-Projekte lars-tiefland.laravel_shop

<?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)

     */

    private int $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];

    }

}