Module loda.runtime.operations

Evaluate operations.

Functions

def add(a, b)

Expand source code

def add(a, b):
    """Addition."""
    if a == None or b == None:
        return None
    return a + b

Addition.

def ban(a, b)

Expand source code

def ban(a, b):
    """Bitwise AND."""
    if a is None or b is None:
        return None
    return a & b

Bitwise AND.

def bin(n, k)

Expand source code

def bin(n, k):
    """Binomial Coefficient."""
    if n == None or k == None:
        return None
    # check for negative arguments: https://arxiv.org/pdf/1105.3689.pdf
    sign = 1
    if n < 0:  # Theorem 2.1
        if k >= 0:
            sign = 1 if mod(k, 2) == 0 else -1
            n = sub(k, add(n, 1))
        elif n >= k:
            sign = 1 if mod(sub(n, k), 2) == 0 else -1
            m = n
            n = sub(0, add(k, 1))
            k = sub(m, k)
        else:
            return 0
    if k < 0 or n < k:  # 1.2
        return 0
    if n < mul(k, 2):
        k = sub(n, k)
    # main calculation
    r = 1
    for i in range(k):
        r = mul(r, sub(n, i))
        r = div(r, add(i, 1))
        if r == None:
            break
    return mul(sign, r)

Binomial Coefficient.

def bor(a, b)

Expand source code

def bor(a, b):
    """Bitwise OR."""
    if a is None or b is None:
        return None
    return a | b

Bitwise OR.

def bxo(a, b)

Expand source code

def bxo(a, b):
    """Bitwise XOR."""
    if a is None or b is None:
        return None
    return a ^ b

Bitwise XOR.

def clr(mem, start, length)

Expand source code

def clr(mem, start, length):
    """Clear memory range. Sets memory cells in the range to 0."""
    first, second = get_range(start, length)
    keys_to_delete = [k for k in mem.keys() if first <= k < second]
    for k in keys_to_delete:
        del mem[k]

Clear memory range. Sets memory cells in the range to 0.

def dgr(a, b)

Expand source code

def dgr(a, b):
    """Digital root in base b."""
    if a is None or b is None or b < 2:
        return None
    if a == 0:
        return 0
    sign = -1 if a < 0 else 1
    aa = abs(a)
    return sign * (1 + ((aa - 1) % (b - 1)))

Digital root in base b.

def dgs(a, b)

Expand source code

def dgs(a, b):
    """Digit sum in base b."""
    if a is None or b is None or b < 2:
        return None
    sign = -1 if a < 0 else 1
    aa = abs(a)
    r = 0
    while aa > 0:
        r += aa % b
        aa //= b
    return sign * r

Digit sum in base b.

def dif(a, b)

Expand source code

def dif(a, b):
    """Conditional Division."""
    if a == None or b == None:
        return None
    if b == 0:
        return a
    d = div(a, b)
    return d if a == mul(b, d) else a

Conditional Division.

def dir(a, b)

Expand source code

def dir(a, b):
    """Repeated conditional division."""
    if a is None or b is None:
        return None
    aa = a
    while True:
        r = dif(aa, b)
        if abs(r) == abs(aa):
            break
        aa = r
    return aa

Repeated conditional division.

def div(a, b)

Expand source code

def div(a, b):
    """Division."""
    if a == None or b == None or b == 0:
        return None
    s = 1 if (a < 0) == (b < 0) else -1
    return s * (abs(a) // abs(b))

Division.

def equ(a, b)

Expand source code

def equ(a, b):
    """Equality."""
    if a == None or b == None:
        return None
    return 1 if a == b else 0

Equality.

def exec_arithmetic(t: Operation.Type,
a,
b)

Expand source code

def exec_arithmetic(t: Operation.Type, a, b):
    """Execute an arithmetic operation."""
    if t == Operation.Type.MOV:
        return b
    elif t == Operation.Type.ADD:
        return add(a, b)
    elif t == Operation.Type.SUB:
        return sub(a, b)
    elif t == Operation.Type.TRN:
        return trn(a, b)
    elif t == Operation.Type.MUL:
        return mul(a, b)
    elif t == Operation.Type.DIV:
        return div(a, b)
    elif t == Operation.Type.DIF:
        return dif(a, b)
    elif t == Operation.Type.DIR:
        return dir(a, b)
    elif t == Operation.Type.MOD:
        return mod(a, b)
    elif t == Operation.Type.POW:
        return pow(a, b)
    elif t == Operation.Type.GCD:
        return gcd(a, b)
    elif t == Operation.Type.LEX:
        return lex(a, b)
    elif t == Operation.Type.BIN:
        return bin(a, b)
    elif t == Operation.Type.FAC:
        return fac(a, b)
    elif t == Operation.Type.LOG:
        return log(a, b)
    elif t == Operation.Type.NRT:
        return nrt(a, b)
    elif t == Operation.Type.DGS:
        return dgs(a, b)
    elif t == Operation.Type.DGR:
        return dgr(a, b)
    elif t == Operation.Type.EQU:
        return equ(a, b)
    elif t == Operation.Type.NEQ:
        return neq(a, b)
    elif t == Operation.Type.LEQ:
        return leq(a, b)
    elif t == Operation.Type.GEQ:
        return geq(a, b)
    elif t == Operation.Type.MIN:
        return min(a, b)
    elif t == Operation.Type.MAX:
        return max(a, b)
    elif t == Operation.Type.BAN:
        return ban(a, b)
    elif t == Operation.Type.BOR:
        return bor(a, b)
    elif t == Operation.Type.BXO:
        return bxo(a, b)
    else:
        raise ValueError("operation type not arithmetic: {}".format(t))

Execute an arithmetic operation.

def fac(n, k)

Expand source code

def fac(n, k):
    """Falling and rising factorial."""
    if n is None or k is None:
        return None
    d = 1
    res = 1
    if k < 0:
        k = -k
        d = -1
    for i in range(k):
        res *= n
        if res == 0:
            return 0
        n += d
    return res

Falling and rising factorial.

def fil(mem, start, length)

Expand source code

def fil(mem, start, length):
    """Fill memory range. Sets all cells in range to the value at start."""
    value = mem.get(start, 0)
    first, second = get_range(start, length)
    for i in range(first, second):
        mem[i] = value

Fill memory range. Sets all cells in range to the value at start.

def gcd(a, b)

Expand source code

def gcd(a, b):
    """Greatest Common Divisor."""
    if a == None or b == None:
        return None
    return math.gcd(a, b)

Greatest Common Divisor.

def geq(a, b)

Expand source code

def geq(a, b):
    """Greater or equal."""
    if a == None or b == None:
        return None
    return 1 if a >= b else 0

Greater or equal.

def get_range(start, length)

Expand source code

def get_range(start, length):
    """Get the memory range [first, second) based on start and length.
    
    If length is positive, the range is [start, start+length).
    If length is negative, the range is [start+length+1, start+1).
    If length is zero, the range is [start, start) (empty range).
    """
    if length > 0:
        return (start, start + length)
    elif length < 0:
        return (start + length + 1, start + 1)
    else:
        return (start, start)

Get the memory range [first, second) based on start and length.

If length is positive, the range is [start, start+length). If length is negative, the range is [start+length+1, start+1). If length is zero, the range is [start, start) (empty range).

def leq(a, b)

Expand source code

def leq(a, b):
    """Less or equal."""
    if a == None or b == None:
        return None
    return 1 if a <= b else 0

Less or equal.

def lex(a, b)

Expand source code

def lex(a, b):
    """Largest exponent: returns the largest k such that b^k divides a (C++ semantics)."""
    if a is None or b is None:
        return None
    if b == 0 or abs(b) == 1:
        return 0
    r = 0
    aa = abs(a)
    bb = abs(b)
    while True:
        aaa = dif(aa, bb)
        if aaa == aa:
            break
        aa = aaa
        r += 1
    return r

Largest exponent: returns the largest k such that b^k divides a (C++ semantics).

def log(a, b)

Expand source code

def log(a, b):
    """Discrete logarithm: returns the integer part of log_b(a)."""
    if a is None or b is None or a < 1 or b < 2:
        return None
    if a == 1:
        return 0
    m = 1
    res = 0
    while m < a:
        m *= b
        res += 1
    return res if m == a else res - 1

Discrete logarithm: returns the integer part of log_b(a).

def max(a, b)

Expand source code

def max(a, b):
    """Maximum."""
    if a == None or b == None:
        return None
    return a if a > b else b

Maximum.

def min(a, b)

Expand source code

def min(a, b):
    """Minimum."""
    if a == None or b == None:
        return None
    return a if a < b else b

Minimum.

def mod(a, b)

Expand source code

def mod(a, b):
    """Modulus (Remainder)."""
    if a == None or b == None or b == 0:
        return None
    return a - mul(b, div(a, b))

Modulus (Remainder).

def mul(a, b)

Expand source code

def mul(a, b):
    """Multiplication."""
    if a == None or b == None:
        return None
    return a * b

Multiplication.

def neq(a, b)

Expand source code

def neq(a, b):
    """Inequality."""
    if a == None or b == None:
        return None
    return 1 if a != b else 0

Inequality.

def nrt(a, b)

Expand source code

def nrt(a, b):
    """n-th root: returns the integer part of the b-th root of a."""
    if a is None or b is None or a < 0 or b < 1:
        return None
    if a == 0 or a == 1 or b == 1:
        return a
    r = 1
    l = 0
    h = a
    while l < h:
        m = div(add(l, h), 2)
        p = pow(m, b)
        if p == a:
            return m
        if p < a:
            l = m
        else:
            h = m
        if r == m:
            break
        r = m
    return r

n-th root: returns the integer part of the b-th root of a.

def pow(a, b)

Expand source code

def pow(a, b):
    """Power."""
    if a == None or b == None:
        return None
    if a == 0:
        if b > 0:
            return 0  # 0^(positive number)
        elif b == 0:
            return 1  # 0^0
        else:
            return None  # 0^(negative number) => inf
    elif a == 1:
        return 1  # 1^x is always 1
    elif a == -1:
        return 1 if mod(b, 2) == 0 else -1  # (-1)^x
    else:
        if b < 0:
            return 0
        else:
            return a**b

Power.

def rol(mem, start, length)

Expand source code

def rol(mem, start, length):
    """Rotate left memory range. Shifts all values left by one position, wrapping around."""
    if length == 0:
        return
    first, second = get_range(start, length)
    leftmost = mem.get(first, 0)
    for i in range(first, second - 1):
        mem[i] = mem.get(i + 1, 0)
    mem[second - 1] = leftmost

Rotate left memory range. Shifts all values left by one position, wrapping around.

def ror(mem, start, length)

Expand source code

def ror(mem, start, length):
    """Rotate right memory range. Shifts all values right by one position, wrapping around."""
    if length == 0:
        return
    first, second = get_range(start, length)
    rightmost = mem.get(second - 1, 0)
    for i in range(second - 1, first, -1):
        mem[i] = mem.get(i - 1, 0)
    mem[first] = rightmost

Rotate right memory range. Shifts all values right by one position, wrapping around.

def sub(a, b)

Expand source code

def sub(a, b):
    """Subtraction."""
    if a == None or b == None:
        return None
    return a - b

Subtraction.

def trn(a, b)

Expand source code

def trn(a, b):
    """Truncated Subtraction."""
    if a == None or b == None:
        return None
    return max(a - b, 0)

Truncated Subtraction.