<?
// Arbitrary Length Integer Arithmetic (String).
// Version: .100  (A quick first hack.)
// 10.16.2008

// StrintegerMath

class StrintegerMath {

  // -----------------------
  // Subtraction (x - y) where x >= y assumed
  // -----------------------

  function minus($x, $y) {

    // Initialize stuff
    $result = "";
    $borrow = '0';

    // Pad shortest string
    if (strlen($x) <= strlen($y))
      $x = str_pad($x, strlen($y), "0", STR_PAD_LEFT);
    else
      $y = str_pad($y, strlen($x), "0", STR_PAD_LEFT);

    // Convert strings to arrays
    $tx = $this->str_to_array($x);
    $ty = $this->str_to_array($y);

    // Main subtraction calculation
    $len_tx = count($tx);

    for ($i = $len_tx - 1; $i >= 0; $i--) {

      $tv = (int)$tx[$i] - (int)$borrow - (int)$ty[$i];

      // Update borrow and correct tv if needed.

      if ($tv < 0) {
        $borrow = '1';
        $tv = $tv + 10;
      } else {
        $borrow = '0';
      }

      // Pack digit into result string.
      $result = "$tv" . "$result";
    }
    return $result;
  }

  // -----------------------
  // Addition (x + y)
  // The same as minus (but with carry instead of borrow).
  // -----------------------

  function add($x, $y) {

    // Initialize stuff
    $result = "";
    $carry  = '0';

    // Pad shortest string
    if (strlen($x) <= strlen($y))
      $x = str_pad($x, strlen($y), "0", STR_PAD_LEFT);
    else
      $y = str_pad($y, strlen($x), "0", STR_PAD_LEFT);

    // Convert strings to arrays
    $tx = $this->str_to_array($x);
    $ty = $this->str_to_array($y);

    // Add the array elements
    $len_tx = count($tx);

    for ($i = $len_tx - 1; $i >= 0; $i--) {
      $tv = (int)$tx[$i] + (int)$ty[$i] + (int)$carry;
      if ($tv > 9) {
        $carry = '1';
        $tv = $tv - 10;
      } else {
        $carry = '0';
      }
      $result = "$tv" . "$result";
    }

    if (strcmp($carry, '1') == 0)
      $result = "1" . $result;

    return $result;
  }


  // -----------------------
  // Multiplication (x * y) Using Karatsuba Method
  // -----------------------

  function multiply($x, $y) {

    // Initialize stuff
    $result = "";
    $n = 0;        // Number of digits in (even length) tx.

    // Pad shortest string
    if (strlen($x) <= strlen($y))
      $x = str_pad($x, strlen($y), "0", STR_PAD_LEFT);
    else
      $y = str_pad($y, strlen($x), "0", STR_PAD_LEFT);

    // Convert strings to arrays
    $tx = $this->str_to_array($x);
    $ty = $this->str_to_array($y);

    // Recursive Base (4 or fewer digits)
    if (count($tx) <= 4) {

      $result = strval(intval($x) * intval($y));
      return $result;

    } else {

      // Number of digits > 4 so recurse.
      if ((count($tx) % 2) == 1) {
        // Pad arrays to an even length by inserting a 0 at the beginning
        $tx = array_pad($tx, -(count($tx) + 1), "0");
        $ty = array_pad($ty, -(count($ty) + 1), "0");
      }

      $n = count($tx);

      // Divide stage

      $a = substr($this->array_to_str($tx), 0, $n/2);
      $b = substr($this->array_to_str($tx), $n/2, $n);
      $c = substr($this->array_to_str($ty), 0, $n/2);
      $d = substr($this->array_to_str($ty), $n/2, $n);

      // Now form the representations for a+b, c+d (arithmetic addition)

      $a_plus_b = $this->add($a, $b);
      $c_plus_d = $this->add($c, $d);

      // Conquer stage

      $u = $this->multiply($a, $c);
      $v = $this->multiply($b, $d);
      $w = $this->multiply($a_plus_b, $c_plus_d);

      // Combine stage

      $u_plus_v = $this->add($u, $v);
      $w_minus_uv = $this->minus($w, $u_plus_v);
      $result1 = $this->shift_n($u, $n);
      $result2 = $this->add($result1, $this->shift_n($w_minus_uv, $n/2));
      $result3 = $this->add($result2, $v);

      return ltrim($result3, "0");
    }
  }


  // -----------------------
  // Division (x / y)
  // -----------------------

  function divide($x, $y) {

    if ($this->equal($x, $y)) {
      $q = "1";
    } else if ($this->less_than($x, $y)) {
      $q = "0";
    } else {

      // Initialize more stuff
      $qa = array();
      $x = ltrim($x, "0");
      $len_x = strlen($x);
      $y = ltrim($y, "0");

      for ($i = 0; $i < $len_x; $i++) {

        $working .= $x[$i];

        if ($this->less_than($y, $working)||$this->equal($y, $working)) {

          // find largest multiple of $y < $working
          $accumulator = $y;
          for ($j = 1; $j < 10; $j++ ) {
            $tmp = $this->add($accumulator, $y);
            if ($this->greater_than($tmp, $working)) {
              array_push($qa, $j);
              break;
            }
            $accumulator = $tmp;
          }
          $working = ltrim($this->minus($working, $accumulator), "0");
        } else {
          array_push($qa, 0);
        }
      }
      $q = ltrim($this->array_to_str($qa), "0");
    }
    return $q;
  }


  // -----------------------
  // Mod (x % y)
  // -----------------------

  function mod($x, $y) {

    if ($this->equal($x, $y)) {
      $q = "1";
      $working = "0";
    } else if ($this->less_than($x, $y)) {
      $q = "0";
      $working = $x;
    } else {

      // Initialize more stuff
      // $qa = array();
      $x = ltrim($x, "0");
      $len_x = strlen($x);
      $y = ltrim($y, "0");

      for ($i = 0; $i < $len_x; $i++) {

        $working .= $x[$i];
        if ($this->less_than($y, $working) || $this->equal($y, $working)) {
          // find largest multiple of $y < $working
          $accumulator = $y;
          for ($j = 1; $j < 10; $j++ ) {
            $tmp = $this->add($accumulator, $y);
            if ($this->greater_than($tmp, $working)) {
              // array_push($qa, $j);
              break;
            }
            $accumulator = $tmp;
          }
          $working = $this->minus($working, $accumulator);
        } else {
          // array_push($qa, 0);
        }
      }
      // $q = ltrim($this->array_to_str($qa), "0");
    }
    if ($this->equal($working, "0"))
      if(strlen($working) >= 1)
        return "0";
    return ltrim($working, "0");
  }


  // -----------------------
  // is_even (x)
  // -----------------------

  function is_even($x) {

    if (in_array($x[strlen($x)], array("0", "2", "4", "6", "8")))
      return TRUE;
    return FALSE;

  }


  // -----------------------
  // equal (x = y)
  // -----------------------

  function equal($x, $y) {

    // Pad shortest string
    if (strlen($x) <= strlen($y))
      $x = str_pad($x, strlen($y), "0", STR_PAD_LEFT);
    else
      $y = str_pad($y, strlen($x), "0", STR_PAD_LEFT);

    if (strcmp($x, $y) == 0)
      return TRUE;
    return FALSE;

  }


  // -----------------------
  // less_than (x < y)
  // -----------------------

  function less_than($x, $y) {

    // Initialize stuff
    $trimed_x = ltrim($x, "0");
    $trimed_y = ltrim($y, "0");

    if (strlen($trimed_x) < strlen($trimed_y)) {
      return TRUE;
    } elseif (strlen($trimed_x) > strlen($trimed_y)) {
      return FALSE;
    } else {
      // Iteratively compare digits from right to left to determine truth of x < y
      $len_x = strlen($trimed_x);

      for ($i = 0; $i < $len_x; $i++) {
        if((intval($trimed_x[$i]) < intval($trimed_y[$i])))
          return TRUE;
        if((intval($trimed_x[$i]) > intval($trimed_y[$i])))
          return FALSE;
      }
      return FALSE;
    }
  }


  // -----------------------
  // greater_than (x > y)
  // -----------------------

  function greater_than($x, $y) {

    // Initialize stuff
    $trimed_x = ltrim($x, "0");
    $trimed_y = ltrim($y, "0");

    if (strlen($trimed_x) > strlen($trimed_y)) {
      return TRUE;
    } elseif (strlen($trimed_x) < strlen($trimed_y)) {
      return FALSE;
    } else {
      // Iteratively compare digits from right to left to determine truth of x < y
      $len_x = strlen($trimed_x);

      for ($i = 0; $i < $len_x; $i++) {
        if(intval($trimed_x[$i]) > intval($trimed_y[$i]))
          return TRUE;
        if((intval($trimed_x[$i]) < intval($trimed_y[$i])))
          return FALSE;
      }
      return FALSE;
    }
  }


  // -----------------------
  // Convert string to char array
  // -----------------------

  function str_to_array($string) {

    // Initialize stuff
    $temp_array = array();
    $len_string = strlen($string);

    for ($i = 0; $i < $len_string; $i++)
      array_push($temp_array, $string[$i]);
    return $temp_array;
  }


  // -----------------------
  // Convert char array to string
  // -----------------------

  function array_to_str($the_array) {

    // Initialize stuff
    $result = "";
    $len_array = count($the_array);

    for ($i = 0; $i < $len_array; $i++)
      $result .= $the_array[$i];
    return $result;
  }


  // -----------------------
  // Shift by n (i.e. Multiply by 10^n)
  // -----------------------

  function shift_n ($x, $n) {

    return str_pad($x, strlen($x) + $n, "0", STR_PAD_RIGHT);

  }

}