[Summary view] [Print] [Text view]

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