impl/python.py

import re

from .math_big_integer_types import BigIntegerOp

_INTEGER = re.compile(r"^-?(0|[1-9][0-9]*)$")

#: The largest result, in bits, that power will build: about 19,700 decimal digits.
MAX_POWER_BITS = 65536


def parse_big_integer(text: str) -> int:
    """Parse the registry's decimal integer form. "-0", "+1", "01" and " 1" are refused."""
    if not isinstance(text, str) or not _INTEGER.fullmatch(text) or text == "-0":
        raise ValueError('not a whole number in decimal: "%s"' % (text,))
    return int(text)


def _trunc_div(x: int, y: int) -> int:
    q = abs(x) // abs(y)
    return -q if (x < 0) != (y < 0) else q


def power_big_integer(base: int, exponent: int) -> int:
    """Raise to a power, refusing results beyond MAX_POWER_BITS before building them."""
    if exponent < 0:
        raise ValueError("exponent must not be negative")
    magnitude = abs(base)
    if magnitude >= 2 and magnitude.bit_length() * exponent > MAX_POWER_BITS:
        raise ValueError("result too large: power is limited to %d bits" % (MAX_POWER_BITS,))
    if magnitude <= 1:
        if exponent == 0:
            return 1
        if base == -1:
            return 1 if exponent % 2 == 0 else -1
        return base
    return base ** exponent


def calculate_big_integer(a: str, op: BigIntegerOp, b: str) -> str:
    """Exact integer arithmetic on decimal strings.

    Division truncates towards zero and the remainder takes the sign of the
    dividend, as in TypeScript and Rust. Python's own // floors, so it is not
    used directly on signed values.
    """
    x = parse_big_integer(a)
    y = parse_big_integer(b)
    if op == "add":
        return str(x + y)
    if op == "subtract":
        return str(x - y)
    if op == "multiply":
        return str(x * y)
    if op == "divide":
        if y == 0:
            raise ZeroDivisionError("division by zero")
        return str(_trunc_div(x, y))
    if op == "remainder":
        if y == 0:
            raise ZeroDivisionError("division by zero")
        return str(x - y * _trunc_div(x, y))
    if op == "power":
        return str(power_big_integer(x, y))
    raise ValueError('unknown operation "%s"' % (op,))