deterministic.py

from .backend import xp

def reduce_tree_fixed(x, op: str = "sum"):
    # Deterministic pairwise reduction to the next power of two length.
    x = x.ravel()
    n = x.shape[0]
    if op == "sum":
        neutral = 0.0
    elif op == "max":
        neutral = -xp.inf
    else:
        raise ValueError(f"Unsupported op: {op}")
    m = 1 << (n - 1).bit_length()
    if m != n:
        pad = xp.full((m - n,), neutral, dtype=x.dtype)
        x = xp.concatenate([x, pad])
    while x.shape[0] > 1:
        if op == "sum":
            x = x[0::2] + x[1::2]
        else:
            x = xp.maximum(x[0::2], x[1::2])
    return x[0]

def sum_kahan_fixed(x):
    # Compensated summation with fixed order; uses float64 accumulator.
    x = x.astype(xp.float64, copy=False).ravel()
    s = xp.array(0.0, dtype=xp.float64)
    c = xp.array(0.0, dtype=xp.float64)
    for i in range(x.shape[0]):
        y = x[i] - c
        t = s + y
        c = (t - s) - y
        s = t
    return s