"""vconv.py: VERIFIED convolution of step-function bounds by EXACT integer polynomial products (python-flint fmpz_poly). No floating-point transform is used anywhere.""" import math import numpy as np from flint import fmpz_poly INF = np.inf def dn(x): return np.nextafter(x, -INF) def up(x): return np.nextafter(x, INF) def scale_exp(arrs): """S with max |a| * 2**S < 2**52 over the given arrays (None if all are zero).""" m = 0.0 for a in arrs: a = np.asarray(a, dtype=np.float64) if a.size: m = max(m, float(np.max(np.abs(a)))) if m == 0.0: return None assert np.isfinite(m) e = math.frexp(m)[1] # m < 2**e return 52 - e def to_poly(a, S, upper): """integer polynomial with coefficients floor (or ceil) of a * 2**S; |coefficients| <= 2**52.""" assert S >= 0, "vconv integer images require upward binary scaling" x = np.ldexp(np.asarray(a, dtype=np.float64), S) q = np.ceil(x) if upper else np.floor(x) assert np.all(np.abs(q) <= 2.0 ** 52) return fmpz_poly(q.astype(np.int64).tolist()) def poly_values(c, L, S, M, lower): """bounds for the exact reals c_k * 2**-S / M, k = 0..L-1 (c an fmpz_poly; missing coefficients are 0).""" co = c.coeffs() v = np.zeros(L) if len(co): n = min(len(co), L) v[:n] = np.array([float(int(x)) for x in co[:n]], dtype=np.float64) Mf = float(M) if lower: v = dn(v); v = dn(v / Mf); v = dn(np.ldexp(v, -S)) else: v = up(v); v = up(v / Mf); v = up(np.ldexp(v, -S)) return v def nz_range(hi, lo=None): """index range [first, last+1) where hi (or lo) is nonzero; None if both are identically zero.""" nz = (hi != 0) if lo is None else ((hi != 0) | (lo != 0)) idx = np.nonzero(nz)[0] if idx.size == 0: return None return int(idx[0]), int(idx[-1]) + 1 def pos_neg(F): """F = (lo, hi) signed: F+ in [P0, P1], F- in [N0, N1], all >= 0.""" return ((np.maximum(F[0], 0.0), np.maximum(F[1], 0.0)), (np.maximum(-F[1], 0.0), np.maximum(-F[0], 0.0))) class Exact: """exact convolutions of full-length cell arrays (cells [0, M)); results as grid-point bounds on [0, M] or cell bounds on [0, M).""" def __init__(self, M): assert isinstance(M, (int, np.integer)) and 0 < M <= 2**53, "M must be an exactly representable positive integer" self.M = int(M) self.nconv = 0 def _grid_combo(self, terms_lo, terms_hi, nonneg): """terms: lists of (sign, Fpart_lo_or_hi_array, a0, Gpart_array, b0); every array nonnegative and segment-restricted. Returns grid arrays (Plo, Phi) of length M+1 (grid points 0..M).""" M = self.M out = [] for terms, lower in ((terms_lo, True), (terms_hi, False)): terms = [t for t in terms if t[1].size and t[3].size] if not terms: out.append(np.zeros(M + 1)); continue SF = scale_exp([t[1] for t in terms]); SG = scale_exp([t[3] for t in terms]) if SF is None or SG is None: out.append(np.zeros(M + 1)); continue base = min(t[2] + t[4] for t in terms) acc = fmpz_poly([]) for sgn, Fa, a0, Ga, b0 in terms: # the positive-signed terms of a lower bound and the negative-signed terms of an upper bound use DOWN-rounded operands down = (sgn > 0) == lower A = to_poly(Fa, SF, upper=not down); B = to_poly(Ga, SG, upper=not down) need = M - base # after the shift, coefficient k <-> grid point base + 1 + k <= M sh = a0 + b0 - base if need - sh <= 0: continue P = A.mul_low(B, need - sh) # this term's coefficients 0 .. need-sh-1 <-> grid points a0+b0+1 .. M if sh: P = P.left_shift(sh) acc = acc + P if sgn > 0 else acc - P self.nconv += 1 L = M - base # grid points base+1 .. M vals = poly_values(acc, max(L, 0), SF + SG, M, lower) G = np.zeros(M + 1) # grid points <= base: every term is exactly 0 there if L > 0: G[base + 1:M + 1] = vals if nonneg and lower: G = np.maximum(G, 0.0) out.append(G) return out[0], out[1] def combo_grid(self, items): """items: list of (sign, K, E, kind) with kind 'nn' (K, E >= 0) or 'ns' (K >= 0, E signed); grid bounds of sum sign * (K*E), all products combined exactly before the single outward conversion.""" lo_terms = []; hi_terms = [] for sgn, K, E, kind in items: rk = nz_range(K[1]); re_ = nz_range(E[1], E[0]) if kind == 'ns' else nz_range(E[1]) if rk is None or re_ is None: continue t = self._trunc(rk, re_) if t is None: continue (a0, a1), (b0, b1) = t Klo = np.maximum(K[0][a0:a1], 0.0); Khi = K[1][a0:a1] if kind == 'nn': Elo = np.maximum(E[0][b0:b1], 0.0); Ehi = E[1][b0:b1] if sgn > 0: lo_terms.append((1, Klo, a0, Elo, b0)); hi_terms.append((1, Khi, a0, Ehi, b0)) else: lo_terms.append((-1, Khi, a0, Ehi, b0)); hi_terms.append((-1, Klo, a0, Elo, b0)) else: (Ep0, Ep1), (Em0, Em1) = pos_neg((E[0][b0:b1], E[1][b0:b1])) if sgn > 0: # K*E in [Klo E+lo - Khi E-hi, Khi E+hi - Klo E-lo] lo_terms += [(1, Klo, a0, Ep0, b0), (-1, Khi, a0, Em1, b0)] hi_terms += [(1, Khi, a0, Ep1, b0), (-1, Klo, a0, Em0, b0)] else: # -(K*E) in [-(Khi E+hi - Klo E-lo), -(Klo E+lo - Khi E-hi)] lo_terms += [(-1, Khi, a0, Ep1, b0), (1, Klo, a0, Em0, b0)] hi_terms += [(-1, Klo, a0, Ep0, b0), (1, Khi, a0, Em1, b0)] return self._grid_combo(lo_terms, hi_terms, nonneg=False) def _trunc(self, ra, rb): """truncate segment ranges so that all pairs reaching grid points <= M are kept and nothing else.""" M = self.M a0, a1 = ra; b0, b1 = rb a1 = min(a1, M - b0); b1 = min(b1, M - a0) if a1 <= a0 or b1 <= b0: return None return (a0, a1), (b0, b1) def nn_grid(self, F, G): """F, G nonnegative (lo, hi) full arrays: grid bounds of F*G (lo*lo <= true <= hi*hi).""" rf = nz_range(F[1]); rg = nz_range(G[1]) if rf is None or rg is None: return np.zeros(self.M + 1), np.zeros(self.M + 1) t = self._trunc(rf, rg) if t is None: return np.zeros(self.M + 1), np.zeros(self.M + 1) (a0, a1), (b0, b1) = t Flo = np.maximum(F[0][a0:a1], 0.0); Fhi = F[1][a0:a1]; Glo = np.maximum(G[0][b0:b1], 0.0); Ghi = G[1][b0:b1] return self._grid_combo([(1, Flo, a0, Glo, b0)], [(1, Fhi, a0, Ghi, b0)], nonneg=True) def signed_grid(self, K, E): """K nonnegative (lo, hi), E signed (lo, hi): grid bounds of K*E (L = Klo E+lo - Khi E-hi, U = Khi E+hi - Klo E-lo).""" rk = nz_range(K[1]); re_ = nz_range(E[1], E[0]) if rk is None or re_ is None: return np.zeros(self.M + 1), np.zeros(self.M + 1) t = self._trunc(rk, re_) if t is None: return np.zeros(self.M + 1), np.zeros(self.M + 1) (a0, a1), (b0, b1) = t Klo = np.maximum(K[0][a0:a1], 0.0); Khi = K[1][a0:a1] (Ep0, Ep1), (Em0, Em1) = pos_neg((E[0][b0:b1], E[1][b0:b1])) lo_terms = [(1, Klo, a0, Ep0, b0), (-1, Khi, a0, Em1, b0)] hi_terms = [(1, Khi, a0, Ep1, b0), (-1, Klo, a0, Em0, b0)] return self._grid_combo(lo_terms, hi_terms, nonneg=False) def ss_grid(self, F, G): """F, G signed: grid bounds of F*G via positive and negative parts (8 products).""" rf = nz_range(F[1], F[0]); rg = nz_range(G[1], G[0]) if rf is None or rg is None: return np.zeros(self.M + 1), np.zeros(self.M + 1) t = self._trunc(rf, rg) if t is None: return np.zeros(self.M + 1), np.zeros(self.M + 1) (a0, a1), (b0, b1) = t (Fp0, Fp1), (Fm0, Fm1) = pos_neg((F[0][a0:a1], F[1][a0:a1])) (Gp0, Gp1), (Gm0, Gm1) = pos_neg((G[0][b0:b1], G[1][b0:b1])) lo_terms = [(1, Fp0, a0, Gp0, b0), (1, Fm0, a0, Gm0, b0), (-1, Fp1, a0, Gm1, b0), (-1, Fm1, a0, Gp1, b0)] hi_terms = [(1, Fp1, a0, Gp1, b0), (1, Fm1, a0, Gm1, b0), (-1, Fp0, a0, Gm0, b0), (-1, Fm0, a0, Gp0, b0)] return self._grid_combo(lo_terms, hi_terms, nonneg=False) @staticmethod def cells(Plo, Phi): """cell bounds from grid bounds of a piecewise-linear function: min / max of the two endpoint values.""" return np.minimum(Plo[:-1], Plo[1:]), np.maximum(Phi[:-1], Phi[1:]) def nn(self, F, G): return self.cells(*self.nn_grid(F, G)) def signed(self, K, E): return self.cells(*self.signed_grid(K, E)) def ss(self, F, G): return self.cells(*self.ss_grid(F, G))