13537030216

Committed 26 Feb 2025 05:14AM UTC coverage: 99.651% (+0.002%) from 99.649%

Build # 13537030216

Build Type

Pull #87

github

Committed by

web-flow

Commit Message

Merge 803decdf2 into 2a8adbd72

Pull Request Pull Request #87: Optimize NativeCalculator::doDiv()

Run Details

0 of 8 new or added lines in 1 file covered. (0.0%)

96 existing lines in 2 files now uncovered.

1142 of 1146 relevant lines covered (99.65%)

1142.72 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;

/**
 * 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.
     *
     * 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 readonly int $maxDigits;

    /**
     * @codeCoverageIgnore
     */
    public function __construct()
    {
        $this->maxDigits = match (PHP_INT_SIZE) {
            4 => 9,
            8 => 18,
            default => throw new \RuntimeException('The platform is not 32-bit or 64-bit as expected.')
        };
    }

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

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

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

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

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

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

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

brick / math / 13537030216

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