Interval-math

#!/usr/bin/env node
/* interval-math.js — interval arithmetic (+ - * /) over a JSONL stream of operations.
   Dependency-free, deterministic. Runs in Node or a browser. MIT.

   WHAT IT IS. Give it a stream of operations — one JSON record per line (JSONL),
   each naming two intervals and an operator — and it computes the resulting interval
   and emits it. An interval [lo, hi] stands for "some real number between lo and hi,
   inclusive"; interval arithmetic computes the tightest interval GUARANTEED to
   contain the true result whatever the inputs actually were. Same stream in,
   byte-identical stream out, on every machine and every run. It is a TRANSFORM: one
   record in, one record out, in the same order.

   THE OPERATION RECORD. Each non-blank line is one JSON object:

       {"op": "+", "a": [1, 2], "b": [3, 4]}   -> {"lo":4,"hi":6}
       {"op": "*", "a": [-1, 2], "b": [3, 4]}  -> {"lo":-4,"hi":8}
       {"op": "/", "a": [1, 1], "b": [2, 4]}   -> {"lo":0.25,"hi":0.5}

   "op" is one of "+", "-", "*", "/". "a" and "b" are each a two-element array
   [lo, hi] of finite JSON numbers with lo <= hi. The output is {"lo":L, "hi":H}.

   THE CONTAINMENT GUARANTEE (the whole point). For every operation the result [L,H]
   is computed so that for ALL x in a and ALL y in b, (x op y) lies in [L, H]. This
   is the load-bearing invariant: interval arithmetic is only correct if it never
   loses a possible result.

     +   [a,b] + [c,d] = [a+c, b+d]
     -   [a,b] - [c,d] = [a-d, b-c]              (subtract the OTHER interval flipped)
     *   [a,b] * [c,d] = [min(P), max(P)]  where P = {a*c, a*d, b*c, b*d}
                                            (ALL FOUR corner products — a naive
                                             [a*c, b*d] is WRONG whenever a sign
                                             crosses zero)
     /   [a,b] / [c,d] = [a,b] * [1/d, 1/c]      (multiply by the reciprocal interval)
                                            ONLY when [c,d] does NOT contain 0 —

   DIVISION BY AN INTERVAL SPANNING ZERO IS A HARD ERROR. If b = [c,d] has c <= 0 <= d
   the reciprocal interval is unbounded (the result would be (-inf, +inf) or a split),
   so this gift REFUSES it (exit 2) rather than emit a bound it cannot honor. Dividing
   by an interval strictly on one side of zero (c>0 or d<0) is fine.

   NUMERIC HONESTY. Bounds are IEEE-754 doubles. Every endpoint must be a FINITE JSON
   number; a NaN/Infinity/overflow (e.g. 1e999 -> Infinity) or an interval with
   lo > hi is a HARD ERROR (exit 2) naming the line — never a silent skip. See the
   printed edge for the rounding caveat: this is EXACT for representable endpoints and
   representable results, but does NOT do outward-directed rounding, so a result whose
   true endpoint is not exactly representable in a double is stored as the nearest
   double (which may be a hair inside the mathematically-guaranteed bound). For
   verified/certified interval arithmetic use a rational or a directed-rounding
   library; this gift is the honest zero-dep representation, not a proof engine.

   USAGE
     printf '%s\n' '{"op":"+","a":[1,2],"b":[3,4]}' | node interval-math.js
     printf '%s\n' '{"op":"*","a":[-1,2],"b":[3,4]}' | node interval-math.js
     node interval-math.js ops.jsonl
     node interval-math.js --help

   Each non-blank line is one operation record; blank lines are skipped; a trailing
   \r (CRLF files) is trimmed. Output is one compact JSON object ({"lo":L,"hi":H})
   per record, one per line, in input order.

   Exit codes: 0 success · 2 input error (a line that is not a valid operation record,
   an unknown op, a non-finite or mis-ordered interval, or a division by an interval
   spanning zero). Always a clean one-line message on stderr, never a stack trace.

   Released under MIT. Its edge is printed in the README: this does the four
   arithmetic ops (+ - * /) on real intervals. It is NOT a full interval library — no
   power/exponent, roots, or transcendental functions (sin/exp/log), no interval
   union/intersection/hull, and NO outward-directed rounding (bounds are plain
   doubles). Division by an interval containing zero is refused, not split.
*/
"use strict";

var OPS = { "+": true, "-": true, "*": true, "/": true };

// Validate an interval value: a 2-element array of finite numbers with lo <= hi.
function checkInterval(v, which, lineNo) {
  if (!Array.isArray(v) || v.length !== 2) {
    throw new Error("line " + lineNo + " field " + JSON.stringify(which) +
      " must be a two-element [lo,hi] array");
  }
  var lo = v[0], hi = v[1];
  if (typeof lo !== "number" || typeof hi !== "number" || !isFinite(lo) || !isFinite(hi)) {
    throw new Error("line " + lineNo + " field " + JSON.stringify(which) +
      " endpoints must be finite numbers");
  }
  if (lo > hi) {
    throw new Error("line " + lineNo + " field " + JSON.stringify(which) +
      " has lo > hi (" + lo + " > " + hi + ")");
  }
  return [lo, hi];
}

// Compute one interval operation. Throws (clean, line-named) on divide-by-spanning-0.
function apply(op, a, b, lineNo) {
  var al = a[0], ah = a[1], bl = b[0], bh = b[1];
  switch (op) {
    case "+":
      return [al + bl, ah + bh];
    case "-":
      return [al - bh, ah - bl];
    case "*": {
      var p = [al * bl, al * bh, ah * bl, ah * bh];
      return [Math.min(p[0], p[1], p[2], p[3]), Math.max(p[0], p[1], p[2], p[3])];
    }
    case "/": {
      if (bl <= 0 && bh >= 0) {
        throw new Error("line " + lineNo +
          " divides by an interval spanning zero [" + bl + "," + bh + "] (unbounded result; refused)");
      }
      // reciprocal of [bl,bh] (which does not contain 0) is [1/bh, 1/bl]
      var rl = 1 / bh, rh = 1 / bl;
      var q = [al * rl, al * rh, ah * rl, ah * rh];
      return [Math.min(q[0], q[1], q[2], q[3]), Math.max(q[0], q[1], q[2], q[3])];
    }
    default:
      throw new Error("line " + lineNo + " unknown op " + JSON.stringify(op) +
        " (expected + - * /)");
  }
}

// Convert one parsed record -> {lo,hi}. Throws on a malformed record.
function computeRecord(rec, lineNo) {
  if (rec === null || typeof rec !== "object" || Array.isArray(rec)) {
    throw new Error("line " + lineNo + " is not an operation object");
  }
  var op = rec.op;
  if (typeof op !== "string" || !OPS[op]) {
    throw new Error("line " + lineNo + " has a missing or unknown op " +
      JSON.stringify(op) + " (expected + - * /)");
  }
  var a = checkInterval(rec.a, "a", lineNo);
  var b = checkInterval(rec.b, "b", lineNo);
  var r = apply(op, a, b, lineNo);
  return { lo: r[0], hi: r[1] };
}

// The public transform: JSONL text -> { lines: [json per record..], count }.
function transform(text) {
  var rawLines = String(text).split("\n");
  var out = [];
  var i, line, rec, result;
  for (i = 0; i < rawLines.length; i++) {
    line = rawLines[i];
    if (line.charCodeAt(line.length - 1) === 0x0d) line = line.slice(0, -1); // trim \r
    if (line.length === 0) continue; // blank line

    try { rec = JSON.parse(line); }
    catch (e) {
      throw new Error("line " + (i + 1) + " is not valid JSON: " + JSON.stringify(line.slice(0, 40)));
    }
    result = computeRecord(rec, i + 1);
    out.push(JSON.stringify(result));
  }
  return { lines: out, count: out.length };
}

/* ---- exports (browser + Node) ------------------------------------ */
if (typeof window !== "undefined") {
  window.ForestGifts = window.ForestGifts || {};
  window.ForestGifts.intervalMath = transform;
  window.ForestGifts.intervalOp = function (op, a, b) { return apply(op, checkInterval(a, "a", 1), checkInterval(b, "b", 1), 1); };
}
if (typeof module !== "undefined" && module.exports) {
  module.exports = { transform: transform, apply: apply, computeRecord: computeRecord, checkInterval: checkInterval };
}

/* ---- CLI (runs only when invoked directly, never on require) ------ */
function run(text) {
  var r = transform(text);
  var body = r.lines.length ? r.lines.join("\n") + "\n" : "";
  return { out: body, count: r.count };
}

function main(argv) {
  var args = argv.slice(2);
  if (args.indexOf("--help") !== -1 || args.indexOf("-h") !== -1) {
    process.stdout.write(
      "interval-math.js — interval arithmetic (+ - * /) over a JSONL stream.\n\n" +
      "  printf '%s\\n' '{\"op\":\"+\",\"a\":[1,2],\"b\":[3,4]}' | node interval-math.js   -> {\"lo\":4,\"hi\":6}\n" +
      "  printf '%s\\n' '{\"op\":\"*\",\"a\":[-1,2],\"b\":[3,4]}' | node interval-math.js  -> {\"lo\":-4,\"hi\":8}\n" +
      "  node interval-math.js ops.jsonl\n" +
      "  node interval-math.js --help\n\n" +
      "Each non-blank line is one operation object {op, a:[lo,hi], b:[lo,hi]}. The\n" +
      "result [L,H] is guaranteed to contain every (x op y) for x in a, y in b. Output\n" +
      "is one {\"lo\":L,\"hi\":H} per record, in input order.\n\n" +
      "Edge: the four arithmetic ops on real intervals. NOT a full interval library\n" +
      "(no powers/roots/transcendentals, no union/intersection, no outward rounding).\n" +
      "Division by an interval spanning zero is a hard error, not split.\n"
    );
    return 0;
  }

  var files = [];
  var i;
  try {
    for (i = 0; i < args.length; i++) {
      if (args[i].charAt(0) === "-" && args[i] !== "-") { throw new Error("unknown option " + args[i]); }
      else { files.push(args[i]); }
    }
  } catch (e) {
    process.stderr.write("interval-math: " + e.message + "\n");
    return 2;
  }

  function emit(text) {
    try {
      var r = run(text);
      process.stdout.write(r.out);
      return 0;
    } catch (e) {
      process.stderr.write("interval-math: " + e.message + "\n");
      return 2;
    }
  }

  if (files.length > 0) {
    var fs = require("fs");
    var text;
    try { text = fs.readFileSync(files[0], "utf8"); }
    catch (e) {
      process.stderr.write("interval-math: cannot read " + files[0] +
        " (" + (e.code === "EISDIR" ? "is a directory" : (e.code || "read error")) + ")\n");
      return 2;
    }
    return emit(text);
  }

  var chunks = [];
  process.stdin.on("data", function (d) { chunks.push(d); });
  process.stdin.on("end", function () {
    process.exitCode = emit(Buffer.concat(chunks).toString("utf8"));
  });
  return 0;
}

if (typeof require !== "undefined" && require.main === module) {
  process.exitCode = main(process.argv);
}

#!/usr/bin/env node
/* test_interval-math.js — golden battery for the interval-math gift.

   Out-of-band and self-verifying. The oracle here is not an external library — it is
   the CONTAINMENT INVARIANT, which is self-witnessing:

     (1) CONTAINMENT. For each op and interval pair, sample a dense grid of x in a and
         y in b, compute (x op y) directly, and assert EVERY sampled result lies
         within the gift's returned [lo,hi]. A correct interval result cannot fail
         this; an under-wide (buggy) result will. This needs no external authority —
         the definition of interval arithmetic IS the test.

     (2) TIGHTNESS (a companion, so containment isn't passed by returning [-inf,inf]).
         For + - * / on continuous inputs the true result range endpoints are attained
         at interval corners, so the gift's [lo,hi] must EQUAL [min,max] of the sampled
         direct results to within a small epsilon — i.e. the interval is not just
         containing but tight.

     (3) FROZEN hand goldens — the sign-crossing multiply (the corner case), the
         subtraction flip, reciprocal division, and the division-spanning-zero refusal.

   A planted mutation (the bite, §BITE) MUST be caught: the naive multiply
   [a*c, b*d] (only two corners) is WRONG on a sign-crossing interval; the oracle
   (containment) must reject it.

   Run:  node test_interval-math.js   -> exit 0 GREEN / non-zero RED
*/
"use strict";
var im = require("./interval-math.js");

var pass = 0, fail = 0;
function ok(name, cond) {
  if (cond) { pass++; }
  else { fail++; console.log("  FAIL  " + name); }
}
function J(v) { return JSON.stringify(v); }
function giftOp(op, a, b) {
  var r = im.transform(J({ op: op, a: a, b: b }) + "\n");
  return JSON.parse(r.lines[0]); // {lo,hi}
}

// direct scalar op
function scalar(op, x, y) {
  if (op === "+") return x + y;
  if (op === "-") return x - y;
  if (op === "*") return x * y;
  if (op === "/") return x / y;
  throw new Error("bad op");
}
// sample N points across [lo,hi] inclusive
function grid(lo, hi, n) {
  if (lo === hi) return [lo];
  var out = [];
  for (var i = 0; i <= n; i++) out.push(lo + (hi - lo) * i / n);
  return out;
}

/* ---- (1)+(2) containment AND tightness over a spread of ops+intervals ----- */
(function () {
  var cases = [
    ["+", [1, 2], [3, 4]],
    ["-", [1, 2], [3, 4]],
    ["*", [-1, 2], [3, 4]],       // sign-crossing a
    ["*", [-3, -1], [-4, -2]],    // both negative
    ["*", [-2, 3], [-5, 4]],      // both sign-crossing (the hard corner case)
    ["*", [0, 5], [2, 3]],
    ["/", [1, 1], [2, 4]],
    ["/", [-6, 6], [2, 3]],       // numerator spans 0, denom positive
    ["/", [1, 2], [-4, -2]],      // denom strictly negative
    ["+", [-5, -5], [5, 5]],      // degenerate (points)
  ];
  var containFail = 0, tightFail = 0;
  cases.forEach(function (c) {
    var op = c[0], a = c[1], b = c[2];
    var got = giftOp(op, a, b);
    var xs = grid(a[0], a[1], 20), ys = grid(b[0], b[1], 20);
    var minR = Infinity, maxR = -Infinity, allIn = true;
    for (var i = 0; i < xs.length; i++) for (var j = 0; j < ys.length; j++) {
      var v = scalar(op, xs[i], ys[j]);
      if (v < minR) minR = v;
      if (v > maxR) maxR = v;
      if (v < got.lo - 1e-9 || v > got.hi + 1e-9) allIn = false;
    }
    if (!allIn) { containFail++; console.log("    CONTAIN " + op + " " + J(a) + J(b) + " -> " + J(got)); }
    // tightness: the gift's bounds equal the sampled extremes to epsilon
    if (Math.abs(got.lo - minR) > 1e-6 || Math.abs(got.hi - maxR) > 1e-6) {
      tightFail++; console.log("    TIGHT " + op + " " + J(a) + J(b) + " gift=" + J(got) + " sampled=[" + minR + "," + maxR + "]");
    }
  });
  ok("containment: every sampled x∘y lies in the gift interval (" + cases.length + " cases)", containFail === 0);
  ok("tightness: gift bounds == sampled extremes (" + cases.length + " cases)", tightFail === 0);
})();

/* ---- (3) frozen hand goldens --------------------------------------------- */
function G(name, op, a, b, lo, hi) {
  var g = giftOp(op, a, b);
  ok(name, g.lo === lo && g.hi === hi);
}
G("add", "+", [1, 2], [3, 4], 4, 6);
G("sub flips the other interval", "-", [1, 2], [3, 4], -3, -1);
G("mul sign-crossing (all four corners)", "*", [-1, 2], [3, 4], -4, 8);
G("mul both negative", "*", [-3, -1], [-4, -2], 2, 12);
G("mul both sign-crossing", "*", [-2, 3], [-5, 4], -15, 12);
G("div by positive interval", "/", [1, 1], [2, 4], 0.25, 0.5);
G("div numerator spans zero", "/", [-6, 6], [2, 3], -3, 3);
G("div by strictly-negative interval", "/", [1, 2], [-4, -2], -1, -0.25);

/* ---- (4) division-by-spanning-zero is a HARD ERROR ------------------------ */
function throws(name, fn) {
  var t = false;
  try { fn(); } catch (e) { t = true; }
  ok(name, t);
}
throws("div by [-1,1] (spans 0) refused", function () { giftOp("/", [1, 2], [-1, 1]); });
throws("div by [0,2] (touches 0 at lo) refused", function () { giftOp("/", [1, 2], [0, 2]); });
throws("div by [-2,0] (touches 0 at hi) refused", function () { giftOp("/", [1, 2], [-2, 0]); });
throws("div by [0,0] refused", function () { giftOp("/", [1, 2], [0, 0]); });

/* ---- (5) transform shape + input honesty --------------------------------- */
(function () {
  var text = '{"op":"+","a":[1,2],"b":[3,4]}\n{"op":"*","a":[0,1],"b":[2,2]}\n';
  var r = im.transform(text);
  ok("one output per input, in order", J(r.lines) === J(['{"lo":4,"hi":6}', '{"lo":0,"hi":2}']));
  ok("count == records", r.count === 2);
})();
ok("blank lines skipped", im.transform('{"op":"+","a":[1,1],"b":[1,1]}\n\n').count === 1);
ok("CRLF trimmed", J(im.transform('{"op":"+","a":[1,1],"b":[2,2]}\r\n').lines) === J(['{"lo":3,"hi":3}']));
(function () {
  var t = '{"op":"*","a":[-2,3],"b":[-5,4]}\n';
  ok("determinism: two runs identical", im.transform(t).lines.join() === im.transform(t).lines.join());
})();

throws("unknown op is a hard error", function () { giftOp("^", [1, 2], [3, 4]); });
throws("missing op is a hard error", function () { im.transform('{"a":[1,2],"b":[3,4]}\n'); });
throws("interval not a 2-array", function () { im.transform('{"op":"+","a":[1,2,3],"b":[3,4]}\n'); });
throws("interval lo>hi is a hard error", function () { im.transform('{"op":"+","a":[2,1],"b":[3,4]}\n'); });
throws("non-finite endpoint (1e999->Infinity) is a hard error", function () { im.transform('{"op":"+","a":[1e999,1e999],"b":[3,4]}\n'); });
throws("non-object record is a hard error", function () { im.transform('[1,2]\n'); });
throws("non-JSON line is a hard error", function () { im.transform('not json\n'); });
ok("hard error names the line", (function () {
  try { im.transform('{"op":"+","a":[1,1],"b":[2,2]}\n{"op":"?","a":[1,1],"b":[2,2]}\n'); return false; }
  catch (e) { return /line 2/.test(e.message); }
})());

/* ---- §BITE — the naive-multiply mutation must be caught ------------------- */
/* The classic wrong build is mul = [a*c, b*d] (only 2 corners). It agrees with the
   correct gift when signs don't cross, but is WRONG on a sign-crossing interval. We
   build that mutant and assert containment (the oracle) rejects it on a crossing
   case — so a regression to naive-corners fails test (1). */
(function () {
  function naiveMul(a, b) { return { lo: a[0] * b[0], hi: a[1] * b[1] }; }
  var a = [-2, 3], b = [-5, 4];
  var gift = giftOp("*", a, b);            // correct: [-15, 12]
  var mutant = naiveMul(a, b);             // naive: [10, 12]  (WRONG, misses -15 and lower)
  // containment check on the mutant: does a sampled product escape it?
  var xs = grid(a[0], a[1], 20), ys = grid(b[0], b[1], 20);
  var mutantEscapes = false, giftContains = true;
  for (var i = 0; i < xs.length; i++) for (var j = 0; j < ys.length; j++) {
    var v = xs[i] * ys[j];
    if (v < mutant.lo - 1e-9 || v > mutant.hi + 1e-9) mutantEscapes = true;
    if (v < gift.lo - 1e-9 || v > gift.hi + 1e-9) giftContains = false;
  }
  ok("BITE: naive-corners mutant fails containment where the gift holds",
     mutantEscapes === true && giftContains === true &&
     gift.lo === -15 && gift.hi === 12);
})();

/* ---- report --------------------------------------------------------------- */
console.log("");
console.log("interval-math battery: " + pass + " passed, " + fail + " failed");
process.exit(fail === 0 ? 0 : 1);