contract DSMath {
  function add(uint x, uint y) internal pure returns (uint z) {
    require((z = x + y) >= x, "ds-math-add-overflow");
  }

  function sub(uint x, uint y) internal pure returns (uint z) {
    require((z = x - y) <= x, "ds-math-sub-underflow");
  }

  function mul(uint x, uint y) internal pure returns (uint z) {
    require(y == 0 || (z = x * y) / y == x, "ds-math-mul-overflow");
  }

  function min(uint x, uint y) internal pure returns (uint z) {
    return x <= y ? x : y;
  }

  function max(uint x, uint y) internal pure returns (uint z) {
    return x >= y ? x : y;
  }

  function imin(int x, int y) internal pure returns (int z) {
    return x <= y ? x : y;
  }

  function imax(int x, int y) internal pure returns (int z) {
    return x >= y ? x : y;
  }

  uint internal constant WAD = 10**18;
  uint internal constant RAY = 10**27;

  //rounds to zero if x*y < WAD / 2
  function wmul(uint x, uint y) internal pure returns (uint z) {
    z = add(mul(x, y), WAD / 2) / WAD;
  }

  //rounds to zero if x*y < WAD / 2
  function rmul(uint x, uint y) internal pure returns (uint z) {
    z = add(mul(x, y), RAY / 2) / RAY;
  }

  //rounds to zero if x*y < WAD / 2
  function wdiv(uint x, uint y) internal pure returns (uint z) {
    z = add(mul(x, WAD), y / 2) / y;
  }

  //rounds to zero if x*y < RAY / 2
  function rdiv(uint x, uint y) internal pure returns (uint z) {
    z = add(mul(x, RAY), y / 2) / y;
  }

  // This famous algorithm is called "exponentiation by squaring"
  // and calculates x^n with x as fixed-point and n as regular unsigned.
  //
  // It's O(log n), instead of O(n) for naive repeated multiplication.
  //
  // These facts are why it works:
  //
  //  If n is even, then x^n = (x^2)^(n/2).
  //  If n is odd,  then x^n = x * x^(n-1),
  //   and applying the equation for even x gives
  //    x^n = x * (x^2)^((n-1) / 2).
  //
  //  Also, EVM division is flooring and
  //    floor[(n-1) / 2] = floor[n / 2].
  //
  function rpow(uint x, uint n) internal pure returns (uint z) {
    z = n % 2 != 0 ? x : RAY;

    for (n /= 2; n != 0; n /= 2) {
      x = rmul(x, x);

      if (n % 2 != 0) {
        z = rmul(z, x);
      }
    }
  }

  // MATH Exponentiation
  // x ^ n using base b
  // EX: rpow(1.1 ether, 30e6, 1 ether) = (1.1 ^ 30e6) ether
  function rpow(
    uint x,
    uint n,
    uint b
  ) internal pure returns (uint z) {
    // solhint-disable no-inline-assembly
    assembly {
      switch x
      case 0 {
        switch n
        case 0 {
          z := b
        }
        default {
          z := 0
        }
      }
      default {
        switch mod(n, 2)
        case 0 {
          z := b
        }
        default {
          z := x
        }
        let half := div(b, 2) // for rounding.
        for {
          n := div(n, 2)
        } n {
          n := div(n, 2)
        } {
          let xx := mul(x, x)
          if iszero(eq(div(xx, x), x)) {
            revert(0, 0)
          }
          let xxRound := add(xx, half)
          if lt(xxRound, xx) {
            revert(0, 0)
          }
          x := div(xxRound, b)
          if mod(n, 2) {
            let zx := mul(z, x)
            if and(iszero(iszero(x)), iszero(eq(div(zx, x), z))) {
              revert(0, 0)
            }
            let zxRound := add(zx, half)
            if lt(zxRound, zx) {
              revert(0, 0)
            }
            z := div(zxRound, b)
          }
        }
      }
    }
  }
}
function rpow(
  uint x,
  uint n,
  uint b
) internal pure returns (uint z) {
  // solhint-disable no-inline-assembly
  assembly {
    switch x
    case 0 {
      switch n
      case 0 {
        z := b
      }
      default {
        z := 0
      }
    }
    default {
      switch mod(n, 2)
      case 0 {
        z := b
      }
      default {
        z := x
      }
      let half := div(b, 2) // for rounding.
      for {
        n := div(n, 2)
      } n {
        n := div(n, 2)
      } {
        let xx := mul(x, x)
        if iszero(eq(div(xx, x), x)) {
          revert(0, 0)
        }
        let xxRound := add(xx, half)
        if lt(xxRound, xx) {
          revert(0, 0)
        }
        x := div(xxRound, b)
        if mod(n, 2) {
          let zx := mul(z, x)
          if and(iszero(iszero(x)), iszero(eq(div(zx, x), z))) {
            revert(0, 0)
          }
          let zxRound := add(zx, half)
          if lt(zxRound, zx) {
            revert(0, 0)
          }
          z := div(zxRound, b)
        }
      }
    }
  }
}

// MATH Exponentiation
// x ^ n using base b
// EX: rpow(1.1 ether, 30e6, 1 ether) = (1.1 ^ 30e6) ether