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