Binary exponentiation

uint256 private constant _MAX_TICK = 8_388_607;
 
/// @notice Compute Q128.128 price from a tick.
/// @param tick_ The log-price in 0.1 bps ticks.
/// @return price The price in Q128.128.
function tickToPrice(int24 tick_) internal pure returns (uint256 price) {
  unchecked {
    // absolute value of tick
    uint256 absTick = (uint256(int256(tick_)) + uint256(int256(tick_) >> 255)) ^ uint256(int256(tick_) >> 255);
 
    /// @solidity memory-safe-assembly
    assembly {
      if gt(absTick, _MAX_TICK) {
        mstore(0x00, 0x4ce861de) // `TickOverflow()`.
        revert(0x1c, 0x04)
      }
    }
 
    if (absTick & 0x1 != 0) price = 0xffff583ac1ac1c114b9160ddeb4791b7;
    else price = 0x100000000000000000000000000000000;
    if (absTick & 0x2 != 0) price = (price * 0xfffeb075f14b276d06cdbc6b138e4c4b) >> 128;
    if (absTick & 0x4 != 0) price = (price * 0xfffd60ed9a60ebcb383de6edb7557ef0) >> 128;
    if (absTick & 0x8 != 0) price = (price * 0xfffac1e213e349a0cf1e3d3ec62bf25b) >> 128;
    if (absTick & 0x10 != 0) price = (price * 0xfff583dfa4044e3dfe90c4057e3e4c27) >> 128;
    if (absTick & 0x20 != 0) price = (price * 0xffeb082d36bf2958d476ee75c4da258a) >> 128;
    if (absTick & 0x40 != 0) price = (price * 0xffd61212165632bd1dda4c1abdf5f9f1) >> 128;
    if (absTick & 0x80 != 0) price = (price * 0xffac2b0240039d9cdadb751e0acc14c4) >> 128;
    if (absTick & 0x100 != 0) price = (price * 0xff5871784dc6fa608dca410bdecb9ff4) >> 128;
    if (absTick & 0x200 != 0) price = (price * 0xfeb1509bdff34ccb280fad9a309403cf) >> 128;
    if (absTick & 0x400 != 0) price = (price * 0xfd6456c5e15445b458f4403d279c1a89) >> 128;
    if (absTick & 0x800 != 0) price = (price * 0xfacf7ad7076227f61d95f764e8d7e35a) >> 128;
    if (absTick & 0x1000 != 0) price = (price * 0xf5b9e413dd1b4e7046f8f721e1f1b295) >> 128;
    if (absTick & 0x2000 != 0) price = (price * 0xebdd5589751f38fd7adce84988dba856) >> 128;
    if (absTick & 0x4000 != 0) price = (price * 0xd9501a6728f01c1f121094aacf4c9475) >> 128;
    if (absTick & 0x8000 != 0) price = (price * 0xb878e5d36699c3a0fd844110d8b9945f) >> 128;
    if (absTick & 0x10000 != 0) price = (price * 0x84ee037828011d8035f12eb571b46c2a) >> 128;
    if (absTick & 0x20000 != 0) price = (price * 0x450650de5cb791d4a002074d7f179cb3) >> 128;
    if (absTick & 0x40000 != 0) price = (price * 0x129c67bfc1f3084f1f52dd418a4a8f6d) >> 128;
    if (absTick & 0x80000 != 0) price = (price * 0x15a5e2593066b11cd1c3ea05eb95f74) >> 128;
    if (absTick & 0x100000 != 0) price = (price * 0x1d4a2a0310ad5f70ad53ef4d3dcf3) >> 128;
    if (absTick & 0x200000 != 0) price = (price * 0x359e3010271ed5cfce08f99aa) >> 128;
    if (absTick & 0x400000 != 0) price = (price * 0xb3ae1a60d291e4871) >> 128;
 
    if (tick_ > 0) {
      /// @solidity memory-safe-assembly
      assembly {
        price := add(div(sub(0, price), price), 1)
      }
    }
  }
}

import math
from decimal import Decimal, localcontext, ROUND_DOWN, ROUND_CEILING, ROUND_FLOOR
 
 
def _to_decimal(base: float | str | Decimal) -> Decimal:
    if isinstance(base, Decimal):
        return base
    if isinstance(base, str):
        return Decimal(base)
    # Fallback for numeric types: go through str to avoid binary float artifacts
    return Decimal(str(base))
 
 
def _inverse_power_by_squaring(
    base_dec: Decimal, i: int, precision_digits: int, rounding: str
) -> Decimal:
    """
    Compute base^(-2^i) as a Decimal using i squarings of base^{-1} under the given rounding mode
    and precision. Rounding is applied at each operation per Decimal context.
    """
    if i < 0:
        raise ValueError("i must be non-negative")
    if base_dec <= 0:
        raise ValueError("base must be positive")
 
    with localcontext() as ctx:
        ctx.prec = precision_digits
        ctx.rounding = rounding
 
        inv = Decimal(1) / base_dec  # rounded per context
        # Each squaring doubles the exponent: inv^(2^k)
        for _ in range(i):
            inv = inv * inv  # rounded per context
        return inv
 
 
def _required_decimal_digits(shift_bits: int, i: int) -> int:
    """
    Heuristic for the number of decimal digits needed to safely determine floor(2^shift * value).
    We start with enough digits to represent shift_bits plus margin and grow with i to account for
    error accumulation across i squarings.
    """
    # Bits to decimal digits conversion: digits = bits * log10(2)
    base_digits = math.ceil(shift_bits * math.log10(2))
    # Add generous safety margin and some per-squaring buffer
    return base_digits + 40 + max(0, i) * 3
 
 
def exponent_for(
    base: float | str | Decimal, i: int, shift: int = 128, max_iter: int = 10
) -> int:
    """
    Compute floor(2^shift * base^(-2^i)) as an integer with guaranteed correctness.
 
    Parameters:
    - base: numeric or string convertible to Decimal. Example: "1.00001"
    - i: non-negative integer, exponent index (computes 2^i)
    - shift: number of bits for the scaling factor (2^shift). Typical: 128 or 256
    - max_iter: maximum precision refinement iterations
    """
    base_dec = _to_decimal(base)
    if base_dec <= 0:
        raise ValueError("base must be positive")
    if i < 0:
        raise ValueError("i must be non-negative")
    if shift < 1:
        raise ValueError("shift must be >= 1")
 
    scale = 1 << shift
 
    # Iteratively refine precision until the floored values from lower and upper bounds converge
    precision_digits = _required_decimal_digits(shift, i)
    for _ in range(max_iter):
        # Lower bound using downward rounding at every step
        lb = _inverse_power_by_squaring(base_dec, i, precision_digits, ROUND_DOWN)
        # Upper bound using upward rounding at every step
        ub = _inverse_power_by_squaring(base_dec, i, precision_digits, ROUND_CEILING)
 
        with localcontext() as ctx_lb:
            ctx_lb.prec = precision_digits
            ctx_lb.rounding = ROUND_FLOOR
            a = int((lb * Decimal(scale)).to_integral_value(rounding=ROUND_FLOOR))
 
        with localcontext() as ctx_ub:
            ctx_ub.prec = precision_digits
            ctx_ub.rounding = ROUND_FLOOR
            c = int((ub * Decimal(scale)).to_integral_value(rounding=ROUND_FLOOR))
 
        if c == a:
            return a
        if c == a + 1:
            # Decide boundary precisely using the lower bound
            # If lb >= (a+1)/scale then the true value >= threshold, so floor is a+1
            with localcontext() as ctx_chk:
                ctx_chk.prec = precision_digits
                ctx_chk.rounding = ROUND_DOWN
                threshold = Decimal(a + 1) / Decimal(scale)
                if lb >= threshold:
                    return a + 1
                return a
 
        # Ambiguity larger than 1 ULP: increase precision and try again
        precision_digits = int(precision_digits * 1.6) + 10
 
    # Fallback: compute with high precision and return the floor using downward rounding
    precision_digits = precision_digits + 80
    lb = _inverse_power_by_squaring(base_dec, i, precision_digits, ROUND_DOWN)
    with localcontext() as ctx:
        ctx.prec = precision_digits
        ctx.rounding = ROUND_FLOOR
        return int((lb * Decimal(scale)).to_integral_value(rounding=ROUND_FLOOR))