# dpl.py: second-order enclosure arithmetic (piecewise-linear lower and upper bounds per grid cell, integers scaled by # 10^18, exact convolutions by FLINT integer polynomial products, outward rounding). Used by the cert2 engines. from fractions import Fraction as Fr from flint import fmpz_poly SCALE = 10 ** 18 M = None def init(m): global M M = m def fl(a, b): return a // b def ce(a, b): return -((-a) // b) def fz(x): return float(Fr(x, SCALE)) class D: __slots__ = ('la', 'lb', 'ua', 'ub') def __init__(self, la, lb, ua, ub): self.la, self.lb, self.ua, self.ub = la, lb, ua, ub def dz(): return D([0] * M, [0] * M, [0] * M, [0] * M) def d_copy(p): return D(list(p.la), list(p.lb), list(p.ua), list(p.ub)) def d_add(p, q, sign=1): if sign > 0: return D([x + y for x, y in zip(p.la, q.la)], [x + y for x, y in zip(p.lb, q.lb)], [x + y for x, y in zip(p.ua, q.ua)], [x + y for x, y in zip(p.ub, q.ub)]) return D([x - y for x, y in zip(p.la, q.ua)], [x - y for x, y in zip(p.lb, q.ub)], [x - y for x, y in zip(p.ua, q.la)], [x - y for x, y in zip(p.ub, q.lb)]) def d_neg(p): return D([-x for x in p.ua], [-x for x in p.ub], [-x for x in p.la], [-x for x in p.lb]) def d_scale(p, c): c = Fr(c); n, d = c.numerator, c.denominator if n >= 0: return D([fl(n * x, d) for x in p.la], [fl(n * x, d) for x in p.lb], [ce(n * x, d) for x in p.ua], [ce(n * x, d) for x in p.ub]) return D([fl(n * x, d) for x in p.ua], [fl(n * x, d) for x in p.ub], [ce(n * x, d) for x in p.la], [ce(n * x, d) for x in p.lb]) def d_div(p, k): assert k > 0 return D([fl(x, k) for x in p.la], [fl(x, k) for x in p.lb], [ce(x, k) for x in p.ua], [ce(x, k) for x in p.ub]) def d_trunc(p, c0, c1=None): c1 = M if c1 is None else c1 z = lambda arr: [arr[i] if c0 <= i < c1 else 0 for i in range(M)] return D(z(p.la), z(p.lb), z(p.ua), z(p.ub)) def d_cell(p, n): return (min(p.la[n], p.lb[n]), max(p.ua[n], p.ub[n])) def d_ends(p, n): return (p.la[n], p.lb[n], p.ua[n], p.ub[n]) def d_ends_rev(p, n): return (p.lb[n], p.la[n], p.ub[n], p.ua[n]) # the same cell seen in the reflected variable (left <-> right) def d_at1(p): return (p.lb[M - 1], p.ub[M - 1]) def d_at0(p): return (p.la[0], p.ua[0]) def d_from_cells(cells, c0): """D from per-cell end tuples (la, lb, ua, ub) for cells c0, c0+1, ...; zero elsewhere""" la = [0] * M; lb = [0] * M; ua = [0] * M; ub = [0] * M for idx, t in enumerate(cells): n = c0 + idx; la[n], lb[n], ua[n], ub[n] = t return D(la, lb, ua, ub) def d_const_cells(ivs, c0): """STEP-like D: per-cell constant intervals (lo, hi) for cells c0, ...""" return d_from_cells([(lo, lo, hi, hi) for lo, hi in ivs], c0) def d_minlow(p, c0, c1): return min(min(p.la[i], p.lb[i]) for i in range(c0, c1)) def d_maxup(p, c0, c1): return max(max(p.ua[i], p.ub[i]) for i in range(c0, c1)) def d_maxwidth(p, c0, c1): return max(max(p.ua[i] - p.la[i], p.ub[i] - p.lb[i]) for i in range(c0, c1)) def d_kernel(i0, i1): """1/u on cells [i0, i1) (i0 >= 1): chord above (convex), chord - M/(4 i^3) below (h^2/8 * 2/x_i^3)""" la = [0] * M; lb = [0] * M; ua = [0] * M; ub = [0] * M; SM = SCALE * M for i in range(i0, i1): assert i >= 1 ua[i] = ce(SM, i); ub[i] = ce(SM, i + 1) q = 4 * i ** 3 la[i] = fl(SM * (4 * i * i - 1), q); lb[i] = fl(SM * (q - (i + 1)), q * (i + 1)) return D(la, lb, ua, ub) # ---------------------------------------------------------------- sign splits of one bound function (a, b) (per-cell end values) def _pos_lo(a, b): return ([x if (x >= 0 and y >= 0) else 0 for x, y in zip(a, b)], [y if (x >= 0 and y >= 0) else 0 for x, y in zip(a, b)]) def _pos_hi(a, b): return ([x if x > 0 else 0 for x in a], [y if y > 0 else 0 for y in b]) def _neg_lo(a, b): return ([-x if (x <= 0 and y <= 0) else 0 for x, y in zip(a, b)], [-y if (x <= 0 and y <= 0) else 0 for x, y in zip(a, b)]) def _neg_hi(a, b): return ([-x if x < 0 else 0 for x in a], [-y if y < 0 else 0 for y in b]) # ---------------------------------------------------------------- exact integer sequence products (FLINT), trimmed to the support def _span(x): n = len(x); s = 0 while s < n and x[s] == 0: s += 1 if s == n: return None e = n while x[e - 1] == 0: e -= 1 return (s, e) def _mul(x, y): sx = _span(x); sy = _span(y) if sx is None or sy is None: return None p = fmpz_poly(x[sx[0]:sx[1]]) * fmpz_poly(y[sy[0]:sy[1]]) return (sx[0] + sy[0], [int(v) for v in p.coeffs()]) def _dense(pr, k0, k1): """coefficients of product pr at indices k0..k1-1 as a list""" out = [0] * (k1 - k0) if pr is None: return out off, lst = pr; L = len(lst) lo = max(k0, off); hi = min(k1, off + L) for k in range(lo, hi): out[k - k0] = lst[k - off] return out def _cb(F, G, side, mode): """one side of the enclosure of F*G (mode 'conv') or corr(F, G)(s) = int F(u) G(u - s) du (mode 'corr'), F, G single bound functions given as per-cell end lists (a, b), (c, d). side 'lo': chord - curvature slack (rounded down); 'hi': chord + slack (rounded up).""" a, b = F; c, d = G if not (any(a) or any(b)) or not (any(c) or any(d)): return ([0] * M, [0] * M) S6 = 6 * M * SCALE; S8 = 8 * M * SCALE da = [y - x for x, y in zip(a, b)] JF = [a[0]] + [a[n] - b[n - 1] for n in range(1, M)] JG = [c[0]] + [c[m] - d[m - 1] for m in range(1, M)] dc = [y - x for x, y in zip(c, d)] sa = [x + y for x, y in zip(a, b)] if mode == 'conv': sc = [x + y for x, y in zip(c, d)] pac = _mul(a, c); pbd = _mul(b, d); px = _mul(sa, sc) # N_k = 2 (a+b)*(c+d) - a*c - b*d at index k-1, k = 0..M A_ = _dense(pac, -1, M); B_ = _dense(pbd, -1, M); X_ = _dense(px, -1, M) N = [2 * x - y - z for x, y, z in zip(X_, A_, B_)] # N[k] for k = 0..M (index k-1 of the products) TT = _dense(_mul(da, dc), -1, M) # TT[k] = (da*dc)[k-1], k = 0..M BX = [x + y for x, y in zip(_dense(_mul(JF, dc), 0, M), _dense(_mul(da, JG), 0, M))] X1 = [TT[k] + BX[k] for k in range(M)] # s'' at x_k+ (times M/SCALE^2) X2 = [TT[k + 1] + BX[k] for k in range(M)] # s'' at x_{k+1}- else: cr = c[::-1]; dr = d[::-1]; dcr = dc[::-1]; JGr = JG[::-1] JFe = JF + [-b[M - 1]] # jump at x = 1 acts at s < 1 for correlations scr = [x + y for x, y in zip(cr, dr)] pac = _mul(a, cr); pbd = _mul(b, dr); px = _mul(sa, scr) # N_k = (a+b)*(c+d) + a*c + b*d at index k + M - 1, k = 0..M A_ = _dense(pac, M - 1, 2 * M); B_ = _dense(pbd, M - 1, 2 * M); X_ = _dense(px, M - 1, 2 * M) N = [x + y + z for x, y, z in zip(X_, A_, B_)] TT = _dense(_mul(da, dcr), M - 1, 2 * M) # TTc[d] for d = 0..M BX = [x + y for x, y in zip(_dense(_mul(JFe, dcr), M, 2 * M), _dense(_mul(da, JGr), M - 1, 2 * M - 1))] X1 = [-(TT[k] + BX[k]) for k in range(M)] X2 = [-(TT[k + 1] + BX[k]) for k in range(M)] if side == 'lo': g = [fl(x, S6) for x in N] e = [ce(max(0, x, y), S8) for x, y in zip(X1, X2)] return ([g[k] - e[k] for k in range(M)], [g[k + 1] - e[k] for k in range(M)]) g = [ce(x, S6) for x in N] e = [ce(max(0, -x, -y), S8) for x, y in zip(X1, X2)] return ([g[k] + e[k] for k in range(M)], [g[k + 1] + e[k] for k in range(M)]) def _sub(p, q): return ([x - y for x, y in zip(p[0], q[0])], [x - y for x, y in zip(p[1], q[1])]) def _addp(p, q): return ([x + y for x, y in zip(p[0], q[0])], [x + y for x, y in zip(p[1], q[1])]) def conv_nn(f, g, mode='conv'): """both nonnegative""" lo = _cb(_pos_lo(f.la, f.lb), _pos_lo(g.la, g.lb), 'lo', mode) hi = _cb(_pos_hi(f.ua, f.ub), _pos_hi(g.ua, g.ub), 'hi', mode) return D(lo[0], lo[1], hi[0], hi[1]) def conv_sn(f, g, mode='conv'): """f signed, g nonnegative""" glo = _pos_lo(g.la, g.lb); ghi = _pos_hi(g.ua, g.ub) lo = _sub(_cb(_pos_lo(f.la, f.lb), glo, 'lo', mode), _cb(_neg_hi(f.la, f.lb), ghi, 'hi', mode)) hi = _sub(_cb(_pos_hi(f.ua, f.ub), ghi, 'hi', mode), _cb(_neg_lo(f.ua, f.ub), glo, 'lo', mode)) return D(lo[0], lo[1], hi[0], hi[1]) def conv_ss(f, g, mode='conv'): """both signed: f+ in [pos_lo L_f, pos_hi U_f], f- in [neg_lo U_f, neg_hi L_f]""" fpl, fph, fml, fmh = _pos_lo(f.la, f.lb), _pos_hi(f.ua, f.ub), _neg_lo(f.ua, f.ub), _neg_hi(f.la, f.lb) gpl, gph, gml, gmh = _pos_lo(g.la, g.lb), _pos_hi(g.ua, g.ub), _neg_lo(g.ua, g.ub), _neg_hi(g.la, g.lb) lo = _sub(_addp(_cb(fpl, gpl, 'lo', mode), _cb(fml, gml, 'lo', mode)), _addp(_cb(fph, gmh, 'hi', mode), _cb(fmh, gph, 'hi', mode))) hi = _sub(_addp(_cb(fph, gph, 'hi', mode), _cb(fmh, gmh, 'hi', mode)), _addp(_cb(fpl, gml, 'lo', mode), _cb(fml, gpl, 'lo', mode))) return D(lo[0], lo[1], hi[0], hi[1]) def corr_sn(f, g): return conv_sn(f, g, 'corr') def corr_nn(f, g): return conv_nn(f, g, 'corr') def corr_ss(f, g): return conv_ss(f, g, 'corr') # ---------------------------------------------------------------- pointwise products and quotients on one cell (end tuples) def cell_mul(p, q): """p, q = (la, lb, ua, ub) of two enclosures on the same cell, same orientation -> enclosure of the product""" best = None for (x0, x1) in ((p[0], p[1]), (p[2], p[3])): for (y0, y1) in ((q[0], q[1]), (q[2], q[3])): s = ce(abs((x1 - x0) * (y1 - y0)), 4 * SCALE) v0 = x0 * y0; v1 = x1 * y1 t = (fl(v0, SCALE) - s, fl(v1, SCALE) - s, ce(v0, SCALE) + s, ce(v1, SCALE) + s) if best is None: best = list(t) else: best[0] = min(best[0], t[0]); best[1] = min(best[1], t[1]); best[2] = max(best[2], t[2]); best[3] = max(best[3], t[3]) return tuple(best) def cell_neg_quot(nm, bb): """enclosure of -num/B on one cell; nm, bb = (la, lb, ua, ub); B of one sign on the whole cell (asserted)""" assert (bb[0] > 0 and bb[1] > 0) or (bb[2] < 0 and bb[3] < 0), "B may vanish on the cell" lo0 = lo1 = hi0 = hi1 = None for (n0, n1) in ((nm[0], nm[1]), (nm[2], nm[3])): for (q0, q1) in ((bb[0], bb[1]), (bb[2], bb[3])): dn, dq = n1 - n0, q1 - q0 mq = min(abs(q0), abs(q1)) s = Fr(abs(dq) * abs(dn * q0 - n0 * dq) * SCALE, 4 * mq ** 3) r0 = Fr(-n0 * SCALE, q0); r1 = Fr(-n1 * SCALE, q1) a0, a1, b0, b1 = r0 - s, r1 - s, r0 + s, r1 + s lo0 = a0 if lo0 is None or a0 < lo0 else lo0; lo1 = a1 if lo1 is None or a1 < lo1 else lo1 hi0 = b0 if hi0 is None or b0 > hi0 else hi0; hi1 = b1 if hi1 is None or b1 > hi1 else hi1 f_ = lambda x: x.numerator // x.denominator c_ = lambda x: -((-x.numerator) // x.denominator) return (f_(lo0), f_(lo1), c_(hi0), c_(hi1)) def cell_add(p, q, s=1): if s > 0: return (p[0] + q[0], p[1] + q[1], p[2] + q[2], p[3] + q[3]) return (p[0] - q[2], p[1] - q[3], p[2] - q[0], p[3] - q[1]) def cell_contains0(p): return p[0] <= 0 <= p[2] and p[1] <= 0 <= p[3] def iv_mul(a, b): ps = [a[0] * b[0], a[0] * b[1], a[1] * b[0], a[1] * b[1]] return (fl(min(ps), SCALE), ce(max(ps), SCALE)) def iv_div(a, b): assert b[0] > 0 or b[1] < 0, "division by an interval containing 0" qs = [Fr(x * SCALE, y) for x in a for y in b] return (fl(min(qs).numerator, min(qs).denominator), ce(max(qs).numerator, max(qs).denominator)) def add_iv(a, b, s=1): return (a[0] + b[0], a[1] + b[1]) if s > 0 else (a[0] - b[1], a[1] - b[0]) def iv_scale(a, c): c = Fr(c); num, den = c.numerator, c.denominator if num >= 0: return (fl(num * a[0], den), ce(num * a[1], den)) return (fl(num * a[1], den), ce(num * a[0], den))