17157350650

Committed 22 Aug 2025 02:00PM UTC coverage: 99.739% (-0.001%) from 99.74%

Build # 17157350650

Build Type

push

github

Committed by

BenMorel

Commit Message

Refactor BigNumber::sum() using getTypePriority()

Run Details

12 of 12 new or added lines in 4 files covered. (100.0%)

85 existing lines in 3 files now uncovered.

1148 of 1151 relevant lines covered (99.74%)

1145.39 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/src/Internal/Calculator/NativeCalculator.php

<?php

declare(strict_types=1);

namespace Brick\Math\Internal\Calculator;

use Brick\Math\Internal\Calculator;
use Override;

/**
 * Calculator implementation using only native PHP code.
 *
 * @internal
 *
 * @psalm-immutable
 * @psalm-pure
 */
final readonly 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.
     *
     * In 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;

    /**
     * @pure
     * @codeCoverageIgnore
     */
    public function __construct()
    {
        $this->maxDigits = match (PHP_INT_SIZE) {
            4 => 9,
            8 => 18,
        };
    }

    #[Override]
    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;
    }

    #[Override]
    public function sub(string $a, string $b) : string
    {
        return $this->add($a, $this->neg($b));
    }

    #[Override]
    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;
    }

    #[Override]
    public function divQ(string $a, string $b) : string
    {
        return $this->divQR($a, $b)[0];
    }

    #[Override]
    public function divR(string $a, string $b): string
    {
        return $this->divQR($a, $b)[1];
    }

    #[Override]
    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.
                $q = intdiv($na, $nb);
                $r = $na % $nb;

                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];
    }

    #[Override]
    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/
     */
    #[Override]
    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
     */
    #[Override]
    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.
     *
     * @pure
     */
    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.
     *
     * @pure
     */
    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.
     *
     * @pure
     */
    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.
     *
     * @pure
     *
     * @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

        /** @psalm-var numeric-string $b */
        $nb = $b * 1; // cast to number
        // performance optimization in cases where the remainder will never cause int overflow
        if (is_int(($nb - 1) * 10 + 9)) {
            $r = (int) \substr($a, 0, $z - 1);

            for ($i = $z - 1; $i < $x; $i++) {
                $n = $r * 10 + (int) $a[$i];
                /** @psalm-var int $nb */
                $q .= \intdiv($n, $nb);
                $r = $n % $nb;
            }

            return [\ltrim($q, '0') ?: '0', (string) $r];
        }

        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.
     *
     * @pure
     *
     * @return -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.
     *
     * @pure
     *
     * @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];
    }
}

1	<?php
2
3	declare(strict_types=1);
4
5	namespace Brick\Math\Internal\Calculator;
6
7	use Brick\Math\Internal\Calculator;
8	use Override;
9
10	/**
11	* Calculator implementation using only native PHP code.
12	*
13	* @internal
14	*
15	* @psalm-immutable
16	* @psalm-pure
17	*/
18	final readonly class NativeCalculator extends Calculator
19	{
20	/**
21	* The max number of digits the platform can natively add, subtract, multiply or divide without overflow.
22	* For multiplication, this represents the max sum of the lengths of both operands.
23	*
24	* In addition, it is assumed that an extra digit can hold a carry (1) without overflowing.
25	* Example: 32-bit: max number 1,999,999,999 (9 digits + carry)
26	* 64-bit: max number 1,999,999,999,999,999,999 (18 digits + carry)
27	*/
28	private int $maxDigits;
29
30	/**
31	* @pure
32	* @codeCoverageIgnore
33	*/
34	public function __construct()
35	{
36	$this->maxDigits = match (PHP_INT_SIZE) {
37	4 => 9,
38	8 => 18,
39	};
40	}
41
42	#[Override]
43	public function add(string $a, string $b) : string
44	{
45	/**
46	* @psalm-var numeric-string $a
47	* @psalm-var numeric-string $b
48	*/
49	$result = $a + $b;	2,727✔
50
51	if (is_int($result)) {	2,727✔
UNCOV 52	return (string) $result;	2,131✔
53	}
54
55	if ($a === '0') {	1,534✔
56	return $b;	500✔
57	}
58
59	if ($b === '0') {	1,528✔
60	return $a;	3✔
61	}
62
63	[$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b);	1,525✔
64
65	$result = $aNeg === $bNeg ? $this->doAdd($aDig, $bDig) : $this->doSub($aDig, $bDig);	1,525✔
66
67	if ($aNeg) {	1,525✔
68	$result = $this->neg($result);	121✔
69	}
70
71	return $result;	1,525✔
72	}
73
74	#[Override]
75	public function sub(string $a, string $b) : string
76	{
UNCOV 77	return $this->add($a, $this->neg($b));	828✔
78	}
79
80	#[Override]
81	public function mul(string $a, string $b) : string
82	{
83	/**
84	* @psalm-var numeric-string $a
85	* @psalm-var numeric-string $b
86	*/
87	$result = $a * $b;	2,221✔
88
89	if (is_int($result)) {	2,221✔
90	return (string) $result;	2,105✔
91	}
92
93	if ($a === '0' \|\| $b === '0') {	939✔
94	return '0';	11✔
95	}
96
97	if ($a === '1') {	930✔
98	return $b;	6✔
99	}
100
101	if ($b === '1') {	927✔
102	return $a;	3✔
103	}
104
105	if ($a === '-1') {	924✔
UNCOV 106	return $this->neg($b);	6✔
107	}
108
109	if ($b === '-1') {	918✔
UNCOV 110	return $this->neg($a);	1✔
111	}
112
113	[$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b);	917✔
114
115	$result = $this->doMul($aDig, $bDig);	917✔
116
117	if ($aNeg !== $bNeg) {	917✔
118	$result = $this->neg($result);	110✔
119	}
120
121	return $result;	917✔
122	}
123
124	#[Override]
125	public function divQ(string $a, string $b) : string
126	{
UNCOV 127	return $this->divQR($a, $b)[0];	989✔
128	}
129
130	#[Override]
131	public function divR(string $a, string $b): string
132	{
UNCOV 133	return $this->divQR($a, $b)[1];	1,219✔
134	}
135
136	#[Override]
137	public function divQR(string $a, string $b) : array
138	{
139	if ($a === '0') {	3,965✔
UNCOV 140	return ['0', '0'];	42✔
141	}
142
143	if ($a === $b) {	3,932✔
UNCOV 144	return ['1', '0'];	254✔
145	}
146
147	if ($b === '1') {	3,904✔
UNCOV 148	return [$a, '0'];	158✔
149	}
150
151	if ($b === '-1') {	3,881✔
UNCOV 152	return [$this->neg($a), '0'];	130✔
153	}
154
155	/** @psalm-var numeric-string $a */
UNCOV 156	$na = $a * 1; // cast to number	3,861✔
157
UNCOV 158	if (is_int($na)) {	3,861✔
159	/** @psalm-var numeric-string $b */
UNCOV 160	$nb = $b * 1;	3,022✔
161
UNCOV 162	if (is_int($nb)) {	3,022✔
163	// the only division that may overflow is PHP_INT_MIN / -1,
164	// which cannot happen here as we've already handled a divisor of -1 above.
165	$q = intdiv($na, $nb);	2,938✔
UNCOV 166	$r = $na % $nb;	2,938✔
167
168	return [	2,938✔
169	(string) $q,	2,938✔
170	(string) $r	2,938✔
UNCOV 171	];	2,938✔
172	}
173	}
174
UNCOV 175	[$aNeg, $bNeg, $aDig, $bDig] = $this->init($a, $b);	2,197✔
176
UNCOV 177	[$q, $r] = $this->doDiv($aDig, $bDig);	2,197✔
178
179	if ($aNeg !== $bNeg) {	2,197✔
UNCOV 180	$q = $this->neg($q);	680✔
181	}
182
183	if ($aNeg) {	2,197✔
UNCOV 184	$r = $this->neg($r);	797✔
185	}
186
UNCOV 187	return [$q, $r];	2,197✔
188	}
189
190	#[Override]
191	public function pow(string $a, int $e) : string
192	{
193	if ($e === 0) {	574✔
194	return '1';	6✔
195	}
196
197	if ($e === 1) {	571✔
198	return $a;	568✔
199	}
200
201	$odd = $e % 2;	568✔
202	$e -= $odd;	568✔
203
204	$aa = $this->mul($a, $a);	568✔
205
206	/** @psalm-suppress PossiblyInvalidArgument We're sure that $e / 2 is an int now */
207	$result = $this->pow($aa, $e / 2);	568✔
208
209	if ($odd === 1) {	568✔
210	$result = $this->mul($result, $a);	450✔
211	}
212
213	return $result;	568✔
214	}
215
216	/**
217	* Algorithm from: https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/
218	*/
219	#[Override]
220	public function modPow(string $base, string $exp, string $mod) : string
221	{
222	// special case: the algorithm below fails with 0 power 0 mod 1 (returns 1 instead of 0)
223	if ($base === '0' && $exp === '0' && $mod === '1') {	11✔
UNCOV 224	return '0';	1✔
225	}
226
227	// special case: the algorithm below fails with power 0 mod 1 (returns 1 instead of 0)
228	if ($exp === '0' && $mod === '1') {	10✔
UNCOV 229	return '0';	1✔
230	}
231
UNCOV 232	$x = $base;	9✔
233
UNCOV 234	$res = '1';	9✔
235
236	// numbers are positive, so we can use remainder instead of modulo
UNCOV 237	$x = $this->divR($x, $mod);	9✔
238
239	while ($exp !== '0') {	9✔
240	if (in_array($exp[-1], ['1', '3', '5', '7', '9'])) { // odd	9✔
UNCOV 241	$res = $this->divR($this->mul($res, $x), $mod);	9✔
242	}
243
244	$exp = $this->divQ($exp, '2');	9✔
UNCOV 245	$x = $this->divR($this->mul($x, $x), $mod);	9✔
246	}
247
UNCOV 248	return $res;	9✔
249	}
250
251	/**
252	* Adapted from https://cp-algorithms.com/num_methods/roots_newton.html
253	*/
254	#[Override]
255	public function sqrt(string $n) : string
256	{
257	if ($n === '0') {	486✔
UNCOV 258	return '0';	1✔
259	}
260
261	// initial approximation
UNCOV 262	$x = \str_repeat('9', \intdiv(\strlen($n), 2) ?: 1);	485✔
263
UNCOV 264	$decreased = false;	485✔
265
266	for (;;) {
UNCOV 267	$nx = $this->divQ($this->add($x, $this->divQ($n, $x)), '2');	485✔
268
269	if ($x === $nx \|\| $this->cmp($nx, $x) > 0 && $decreased) {	485✔
UNCOV 270	break;	485✔
271	}
272
273	$decreased = $this->cmp($nx, $x) < 0;	481✔
UNCOV 274	$x = $nx;	485✔
275	}
276
UNCOV 277	return $x;	485✔
278	}
279
280	/**
281	* Performs the addition of two non-signed large integers.
282	*
283	* @pure
284	*/
285	private function doAdd(string $a, string $b) : string
286	{
287	[$a, $b, $length] = $this->pad($a, $b);	1,382✔
288
289	$carry = 0;	1,382✔
290	$result = '';	1,382✔
291
292	for ($i = $length - $this->maxDigits;; $i -= $this->maxDigits) {	1,382✔
293	$blockLength = $this->maxDigits;	1,382✔
294
295	if ($i < 0) {	1,382✔
296	$blockLength += $i;	1,364✔
297	/** @psalm-suppress LoopInvalidation */
298	$i = 0;	1,364✔
299	}
300
301	/** @psalm-var numeric-string $blockA */
302	$blockA = \substr($a, $i, $blockLength);	1,382✔
303
304	/** @psalm-var numeric-string $blockB */
305	$blockB = \substr($b, $i, $blockLength);	1,382✔
306
307	$sum = (string) ($blockA + $blockB + $carry);	1,382✔
308	$sumLength = \strlen($sum);	1,382✔
309
310	if ($sumLength > $blockLength) {	1,382✔
311	$sum = \substr($sum, 1);	1,078✔
312	$carry = 1;	1,078✔
313	} else {
314	if ($sumLength < $blockLength) {	1,382✔
UNCOV 315	$sum = \str_repeat('0', $blockLength - $sumLength) . $sum;	987✔
316	}
317	$carry = 0;	1,382✔
318	}
319
320	$result = $sum . $result;	1,382✔
321
322	if ($i === 0) {	1,382✔
323	break;	1,382✔
324	}
325	}
326
327	if ($carry === 1) {	1,382✔
UNCOV 328	$result = '1' . $result;	567✔
329	}
330
331	return $result;	1,382✔
332	}
333
334	/**
335	* Performs the subtraction of two non-signed large integers.
336	*
337	* @pure
338	*/
339	private function doSub(string $a, string $b) : string
340	{
341	if ($a === $b) {	599✔
342	return '0';	358✔
343	}
344
345	// Ensure that we always subtract to a positive result: biggest minus smallest.
346	$cmp = $this->doCmp($a, $b);	576✔
347
348	$invert = ($cmp === -1);	576✔
349
UNCOV 350	if ($invert) {	576✔
351	$c = $a;	40✔
UNCOV 352	$a = $b;	40✔
353	$b = $c;	40✔
354	}
355
356	[$a, $b, $length] = $this->pad($a, $b);	576✔
357
358	$carry = 0;	576✔
359	$result = '';	576✔
360
361	$complement = 10 ** $this->maxDigits;	576✔
362
UNCOV 363	for ($i = $length - $this->maxDigits;; $i -= $this->maxDigits) {	576✔
364	$blockLength = $this->maxDigits;	576✔
365
UNCOV 366	if ($i < 0) {	576✔
UNCOV 367	$blockLength += $i;	575✔
368	/** @psalm-suppress LoopInvalidation */
UNCOV 369	$i = 0;	575✔
370	}
371
372	/** @psalm-var numeric-string $blockA */
373	$blockA = \substr($a, $i, $blockLength);	576✔
374
375	/** @psalm-var numeric-string $blockB */
376	$blockB = \substr($b, $i, $blockLength);	576✔
377
UNCOV 378	$sum = $blockA - $blockB - $carry;	576✔
379
UNCOV 380	if ($sum < 0) {	576✔
UNCOV 381	$sum += $complement;	509✔
382	$carry = 1;	509✔
383	} else {
UNCOV 384	$carry = 0;	576✔
385	}
386
UNCOV 387	$sum = (string) $sum;	576✔
UNCOV 388	$sumLength = \strlen($sum);	576✔
389
UNCOV 390	if ($sumLength < $blockLength) {	576✔
391	$sum = \str_repeat('0', $blockLength - $sumLength) . $sum;	539✔
392	}
393
UNCOV 394	$result = $sum . $result;	576✔
395
UNCOV 396	if ($i === 0) {	576✔
UNCOV 397	break;	576✔
398	}
399	}
400
401	// Carry cannot be 1 when the loop ends, as a > b
402	assert($carry === 0);
403
UNCOV 404	$result = \ltrim($result, '0');	576✔
405
UNCOV 406	if ($invert) {	576✔
UNCOV 407	$result = $this->neg($result);	40✔
408	}
409
UNCOV 410	return $result;	576✔
411	}
412
413	/**
414	* Performs the multiplication of two non-signed large integers.
415	*
416	* @pure
417	*/
418	private function doMul(string $a, string $b) : string
419	{
420	$x = \strlen($a);	917✔
421	$y = \strlen($b);	917✔
422
423	$maxDigits = \intdiv($this->maxDigits, 2);	917✔
424	$complement = 10 ** $maxDigits;	917✔
425
426	$result = '0';	917✔
427
428	for ($i = $x - $maxDigits;; $i -= $maxDigits) {	917✔
429	$blockALength = $maxDigits;	917✔
430
431	if ($i < 0) {	917✔
432	$blockALength += $i;	910✔
433	/** @psalm-suppress LoopInvalidation */
434	$i = 0;	910✔
435	}
436
437	$blockA = (int) \substr($a, $i, $blockALength);	917✔
438
439	$line = '';	917✔
440	$carry = 0;	917✔
441
442	for ($j = $y - $maxDigits;; $j -= $maxDigits) {	917✔
443	$blockBLength = $maxDigits;	917✔
444
445	if ($j < 0) {	917✔
446	$blockBLength += $j;	903✔
447	/** @psalm-suppress LoopInvalidation */
448	$j = 0;	903✔
449	}
450
451	$blockB = (int) \substr($b, $j, $blockBLength);	917✔
452
453	$mul = $blockA * $blockB + $carry;	917✔
454	$value = $mul % $complement;	917✔
455	$carry = ($mul - $value) / $complement;	917✔
456
457	$value = (string) $value;	917✔
458	$value = \str_pad($value, $maxDigits, '0', STR_PAD_LEFT);	917✔
459
460	$line = $value . $line;	917✔
461
462	if ($j === 0) {	917✔
463	break;	917✔
464	}
465	}
466
467	if ($carry !== 0) {	917✔
468	$line = $carry . $line;	912✔
469	}
470
471	$line = \ltrim($line, '0');	917✔
472
473	if ($line !== '') {	917✔
474	$line .= \str_repeat('0', $x - $blockALength - $i);	917✔
475	$result = $this->add($result, $line);	917✔
476	}
477
478	if ($i === 0) {	917✔
479	break;	917✔
480	}
481	}
482
483	return $result;	917✔
484	}
485
486	/**
487	* Performs the division of two non-signed large integers.
488	*
489	* @pure
490	*
491	* @return string[] The quotient and remainder.
492	*/
493	private function doDiv(string $a, string $b) : array
494	{
UNCOV 495	$cmp = $this->doCmp($a, $b);	2,197✔
496
497	if ($cmp === -1) {	2,197✔
498	return ['0', $a];	529✔
499	}
500
UNCOV 501	$x = \strlen($a);	2,157✔
502	$y = \strlen($b);	2,157✔
503
504	// we now know that a >= b && x >= y
505
UNCOV 506	$q = '0'; // quotient	2,157✔
507	$r = $a; // remainder	2,157✔
508	$z = $y; // focus length, always $y or $y+1	2,157✔
509
510	/** @psalm-var numeric-string $b */
511	$nb = $b * 1; // cast to number	2,157✔
512	// performance optimization in cases where the remainder will never cause int overflow
UNCOV 513	if (is_int(($nb - 1) * 10 + 9)) {	2,157✔
514	$r = (int) \substr($a, 0, $z - 1);	2,066✔
515
UNCOV 516	for ($i = $z - 1; $i < $x; $i++) {	2,066✔
UNCOV 517	$n = $r * 10 + (int) $a[$i];	2,066✔
518	/** @psalm-var int $nb */
UNCOV 519	$q .= \intdiv($n, $nb);	2,066✔
520	$r = $n % $nb;	2,066✔
521	}
522
523	return [\ltrim($q, '0') ?: '0', (string) $r];	2,066✔
524	}
525
526	for (;;) {
527	$focus = \substr($a, 0, $z);	482✔
528
UNCOV 529	$cmp = $this->doCmp($focus, $b);	482✔
530
UNCOV 531	if ($cmp === -1) {	482✔
532	if ($z === $x) { // remainder < dividend	470✔
533	break;	432✔
534	}
535
UNCOV 536	$z++;	466✔
537	}
538
UNCOV 539	$zeros = \str_repeat('0', $x - $z);	482✔
540
541	$q = $this->add($q, '1' . $zeros);	482✔
UNCOV 542	$a = $this->sub($a, $b . $zeros);	482✔
543
544	$r = $a;	482✔
545
UNCOV 546	if ($r === '0') { // remainder == 0	482✔
547	break;	338✔
548	}
549
550	$x = \strlen($a);	479✔
551
UNCOV 552	if ($x < $y) { // remainder < dividend	479✔
UNCOV 553	break;	395✔
554	}
555
UNCOV 556	$z = $y;	482✔
557	}
558
UNCOV 559	return [$q, $r];	482✔
560	}
561
562	/**
563	* Compares two non-signed large numbers.
564	*
565	* @pure
566	*
567	* @return -1\|0\|1
568	*/
569	private function doCmp(string $a, string $b) : int
570	{
UNCOV 571	$x = \strlen($a);	2,276✔
UNCOV 572	$y = \strlen($b);	2,276✔
573
UNCOV 574	$cmp = $x <=> $y;	2,276✔
575
UNCOV 576	if ($cmp !== 0) {	2,276✔
UNCOV 577	return $cmp;	2,219✔
578	}
579
UNCOV 580	return \strcmp($a, $b) <=> 0; // enforce -1\|0\|1	536✔
581	}
582
583	/**
584	* Pads the left of one of the given numbers with zeros if necessary to make both numbers the same length.
585	*
586	* The numbers must only consist of digits, without leading minus sign.
587	*
588	* @pure
589	*
590	* @return array{string, string, int}
591	*/
592	private function pad(string $a, string $b) : array
593	{
594	$x = \strlen($a);	1,514✔
595	$y = \strlen($b);	1,514✔
596
597	if ($x > $y) {	1,514✔
UNCOV 598	$b = \str_repeat('0', $x - $y) . $b;	958✔
599
UNCOV 600	return [$a, $b, $x];	958✔
601	}
602
603	if ($x < $y) {	1,343✔
604	$a = \str_repeat('0', $y - $x) . $a;	1,023✔
605
606	return [$a, $b, $y];	1,023✔
607	}
608
609	return [$a, $b, $x];	972✔
610	}
611	}

brick / math / 17157350650

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous