21606966779

Committed 02 Feb 2026 09:09PM UTC coverage: 99.307% (+0.001%) from 99.306%

Build # 21606966779

Build Type

push

github

Committed by

BenMorel

Commit Message

Harmonize division by zero exception messages

So far, dividing a BigRational by zero did throw a DivisionByZeroException, but with a misleading message "The denominator of a rational number cannot be zero."

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

320 existing lines in 2 files now uncovered.

1290 of 1299 relevant lines covered (99.31%)

1102.37 hits per line

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

98.31

/src/Internal/Calculator/NativeCalculator.php

<?php

declare(strict_types=1);

namespace Brick\Math\Internal\Calculator;

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

use function assert;
use function in_array;
use function intdiv;
use function is_int;
use function ltrim;
use function str_pad;
use function str_repeat;
use function strcmp;
use function strlen;
use function substr;

use const PHP_INT_SIZE;
use const STR_PAD_LEFT;

/**
 * Calculator implementation using only native PHP code.
 *
 * @internal
 */
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
    {
        /**
         * @var numeric-string $a
         * @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
    {
        /**
         * @var numeric-string $a
         * @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'];
        }

        /** @var numeric-string $a */
        $na = $a * 1; // cast to number

        if (is_int($na)) {
            /** @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);

        $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
    {
        // normalize to Euclidean representative so modPow() stays consistent with mod()
        $base = $this->mod($base, $mod);

        // 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;
                $i = 0;
            }

            /** @var numeric-string $blockA */
            $blockA = substr($a, $i, $blockLength);

            /** @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;
                $i = 0;
            }

            /** @var numeric-string $blockA */
            $blockA = substr($a, $i, $blockLength);

            /** @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;
                $i = 0;
            }

            $blockA = (int) substr($a, $i, $blockALength);

            $line = '';
            $carry = 0;

            for ($j = $y - $maxDigits; ; $j -= $maxDigits) {
                $blockBLength = $maxDigits;

                if ($j < 0) {
                    $blockBLength += $j;
                    $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.
     *
     * @return string[] The quotient and remainder.
     *
     * @pure
     */
    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

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

brick / math / 21606966779

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