FA-14596 / Numerics / Open access

Polynomial long division: leading coefficient cancellation · case 01

The exact polynomial long division result violates the stated contract at leading coefficient cancellation.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The leading coefficient cancellation step uses r[-1] instead of r[-1]/b[-1].

VERIFIED REPAIR

Use r[-1]/b[-1] at the leading coefficient cancellation step.

Unsuccessful approach: The partial repair r[-1]*b[-1] still violates the leading coefficient cancellation invariant.

Case contract

Input [A,B] integer ascending coefficients, B nonzero canonical; return rational quotient/remainder coefficient pairs; zero polynomial is []. Bounds: len(A)<=4 and 1<=len(B)<=4.

Why this case matters

Exact discrete arithmetic with observable algorithmic state; no floating point approximation is used.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    A,B=x
    r=list(map(Fraction,A));b=list(map(Fraction,B))
    while r and r[-1]==0:r.pop()
    q=[Fraction(0)]*max(0,len(r)-len(b)+1)
    for _ in range(20):
     if len(r)<len(b):break
     k=len(r)-len(b)
     if k<0 or k>=len(q):return None
     c=r[-1]
     q[k]=q[k]+c
     for j in range(len(b)):
      if j+k>=len(r):return None
      r[j+k]=r[j+k]-c*b[j]
     while r and r[-1]==0:r.pop()
    while q and q[-1]==0:q.pop()
    return [[[v.numerator,v.denominator] for v in z] for z in (q,r)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [-1, 2]], [[[-3, 4], [-1, 2]], [[-7, 4]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, -1], [-1, 1]], [[[-2, 1], [-1, 1]], [[-3, 1]]]), ([[-1, -1, -1], [0, -1]], [[[1, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [0, 1]], [[[-1, 1], [-1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [0, 2]], [[[-1, 2], [-1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [1, -1]], [[[2, 1], [1, 1]], [[-3, 1]]])], [([[-1, -1, -1], [-1, 2]], [[[-3, 4], [-1, 2]], [[-7, 4]]]), ([[-1, -1, -1], [2, 2]], [[[0, 1], [-1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, 0], [0, 2]], [[[-1, 2]], [[-1, 1]]]), ([[-1, -1, 0], [1, -1]], [[[1, 1]], [[-2, 1]]]), ([[-1, -1, 0], [1, 1]], [[[-1, 1]], []]), ([[-1, -1, 0], [1, 2]], [[[-1, 2]], [[-1, 2]]])], [([[-1, -1, -1], [0, -1]], [[[1, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, 0], [1, 2]], [[[-1, 2]], [[-1, 2]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, 1], [2, 1]], [[[-3, 1], [1, 1]], [[5, 1]]]), ([[-1, -1, 1], [2, 2]], [[[-1, 1], [1, 2]], [[1, 1]]]), ([[-1, -1, 2], [-1, -1]], [[[3, 1], [-2, 1]], [[2, 1]]]), ([[-1, -1, 2], [-1, 1]], [[[1, 1], [2, 1]], []])], [([[-1, -1, -1], [0, 2]], [[[-1, 2], [-1, 2]], [[-1, 1]]]), ([[-1, -1, 1], [0, 2]], [[[-1, 2], [1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, 0, -1], [0, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, 0, -1], [0, 1]], [[[0, 1], [-1, 1]], [[-1, 1]]]), ([[-1, 0, -1], [0, 2]], [[[0, 1], [-1, 2]], [[-1, 1]]]), ([[-1, 0, -1], [1, -1]], [[[1, 1], [1, 1]], [[-2, 1]]])], [([[-1, -1, -1], [1, -1]], [[[2, 1], [1, 1]], [[-3, 1]]]), ([[-1, -1, 2], [-1, 2]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, 0, 0], [1, 2]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, -1]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, 1]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, 2]], [[], [[-1, 1]]])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`[[[0, 1], [-1048575, 1]], [[-1, 1], [-1048576, 1], [-1048576, 1]]]`	`[[[0, 1], [1, 1]], [[-1, 1]]]`	Failed
explicit oracle 1	`[[], [[-1, 1], [-1, 1], [-1, 1]]]`	`[[[-3, 4], [-1, 2]], [[-7, 4]]]`	Failed
explicit oracle 2	`[[], [[1, 1], [2, 1], [3, 1], [4, 1]]]`	`[[[3, 2], [2, 1]], [[-1, 2]]]`	Failed
explicit oracle 3	`[[[-2, 1], [-1, 1]], [[-3, 1]]]`	`[[[-2, 1], [-1, 1]], [[-3, 1]]]`	Passed
explicit oracle 4	`[[[0, 1], [-1048575, 1]], [[-1, 1], [-1, 1], [-1048576, 1]]]`	`[[[1, 1], [1, 1]], [[-1, 1]]]`	Failed
explicit oracle 5	`[[[-1, 1], [-1, 1]], [[-1, 1]]]`	`[[[-1, 1], [-1, 1]], [[-1, 1]]]`	Passed
explicit oracle 6	`[[], [[-1, 1], [-1, 1], [-1, 1]]]`	`[[[-1, 2], [-1, 2]], [[-1, 1]]]`	Failed
explicit oracle 7	`[[[0, 1], [-1048575, 1]], [[-1, 1], [1048574, 1], [-1048576, 1]]]`	`[[[2, 1], [1, 1]], [[-3, 1]]]`	Failed

SHA-256 / c3dc5321076c60b22d0ebe26afe5172fa9075df3df45000fb53be4f461475271

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    A,B=x
    r=list(map(Fraction,A));b=list(map(Fraction,B))
    while r and r[-1]==0:r.pop()
    q=[Fraction(0)]*max(0,len(r)-len(b)+1)
    for _ in range(20):
     if len(r)<len(b):break
     k=len(r)-len(b)
     if k<0 or k>=len(q):return None
     c=r[-1]*b[-1]
     q[k]=q[k]+c
     for j in range(len(b)):
      if j+k>=len(r):return None
      r[j+k]=r[j+k]-c*b[j]
     while r and r[-1]==0:r.pop()
    while q and q[-1]==0:q.pop()
    return [[[v.numerator,v.denominator] for v in z] for z in (q,r)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [-1, 2]], [[[-3, 4], [-1, 2]], [[-7, 4]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, -1], [-1, 1]], [[[-2, 1], [-1, 1]], [[-3, 1]]]), ([[-1, -1, -1], [0, -1]], [[[1, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [0, 1]], [[[-1, 1], [-1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [0, 2]], [[[-1, 2], [-1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [1, -1]], [[[2, 1], [1, 1]], [[-3, 1]]])], [([[-1, -1, -1], [-1, 2]], [[[-3, 4], [-1, 2]], [[-7, 4]]]), ([[-1, -1, -1], [2, 2]], [[[0, 1], [-1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, 0], [0, 2]], [[[-1, 2]], [[-1, 1]]]), ([[-1, -1, 0], [1, -1]], [[[1, 1]], [[-2, 1]]]), ([[-1, -1, 0], [1, 1]], [[[-1, 1]], []]), ([[-1, -1, 0], [1, 2]], [[[-1, 2]], [[-1, 2]]])], [([[-1, -1, -1], [0, -1]], [[[1, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, 0], [1, 2]], [[[-1, 2]], [[-1, 2]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, 1], [2, 1]], [[[-3, 1], [1, 1]], [[5, 1]]]), ([[-1, -1, 1], [2, 2]], [[[-1, 1], [1, 2]], [[1, 1]]]), ([[-1, -1, 2], [-1, -1]], [[[3, 1], [-2, 1]], [[2, 1]]]), ([[-1, -1, 2], [-1, 1]], [[[1, 1], [2, 1]], []])], [([[-1, -1, -1], [0, 2]], [[[-1, 2], [-1, 2]], [[-1, 1]]]), ([[-1, -1, 1], [0, 2]], [[[-1, 2], [1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, 0, -1], [0, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, 0, -1], [0, 1]], [[[0, 1], [-1, 1]], [[-1, 1]]]), ([[-1, 0, -1], [0, 2]], [[[0, 1], [-1, 2]], [[-1, 1]]]), ([[-1, 0, -1], [1, -1]], [[[1, 1], [1, 1]], [[-2, 1]]])], [([[-1, -1, -1], [1, -1]], [[[2, 1], [1, 1]], [[-3, 1]]]), ([[-1, -1, 2], [-1, 2]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, 0, 0], [1, 2]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, -1]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, 1]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, 2]], [[], [[-1, 1]]])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`[[[0, 1], [1, 1]], [[-1, 1]]]`	`[[[0, 1], [1, 1]], [[-1, 1]]]`	Passed
explicit oracle 1	`[[[0, 1], [1743392200, 1]], [[-1, 1], [1743392199, 1], [-3486784401, 1]]]`	`[[[-3, 4], [-1, 2]], [[-7, 4]]]`	Failed
explicit oracle 2	`[[[0, 1], [-6973568800, 1]], [[1, 1], [6973568802, 1], [3, 1], [13947137604, 1]]]`	`[[[3, 2], [2, 1]], [[-1, 2]]]`	Failed
explicit oracle 3	`[[[-2, 1], [-1, 1]], [[-3, 1]]]`	`[[[-2, 1], [-1, 1]], [[-3, 1]]]`	Passed
explicit oracle 4	`[[[1, 1], [1, 1]], [[-1, 1]]]`	`[[[1, 1], [1, 1]], [[-1, 1]]]`	Passed
explicit oracle 5	`[[[-1, 1], [-1, 1]], [[-1, 1]]]`	`[[[-1, 1], [-1, 1]], [[-1, 1]]]`	Passed
explicit oracle 6	`[[[0, 1], [1743392200, 1]], [[-1, 1], [-1, 1], [-3486784401, 1]]]`	`[[[-1, 2], [-1, 2]], [[-1, 1]]]`	Failed
explicit oracle 7	`[[[2, 1], [1, 1]], [[-3, 1]]]`	`[[[2, 1], [1, 1]], [[-3, 1]]]`	Passed

SHA-256 / 27c81fd2d1bbff251b2e08c377bd5a9d3c66cda2977c620433030708886e1a89

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    A,B=x
    r=list(map(Fraction,A));b=list(map(Fraction,B))
    while r and r[-1]==0:r.pop()
    q=[Fraction(0)]*max(0,len(r)-len(b)+1)
    for _ in range(20):
     if len(r)<len(b):break
     k=len(r)-len(b)
     if k<0 or k>=len(q):return None
     c=r[-1]/b[-1]
     q[k]=q[k]+c
     for j in range(len(b)):
      if j+k>=len(r):return None
      r[j+k]=r[j+k]-c*b[j]
     while r and r[-1]==0:r.pop()
    while q and q[-1]==0:q.pop()
    return [[[v.numerator,v.denominator] for v in z] for z in (q,r)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [-1, 2]], [[[-3, 4], [-1, 2]], [[-7, 4]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, -1], [-1, 1]], [[[-2, 1], [-1, 1]], [[-3, 1]]]), ([[-1, -1, -1], [0, -1]], [[[1, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [0, 1]], [[[-1, 1], [-1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [0, 2]], [[[-1, 2], [-1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [1, -1]], [[[2, 1], [1, 1]], [[-3, 1]]])], [([[-1, -1, -1], [-1, 2]], [[[-3, 4], [-1, 2]], [[-7, 4]]]), ([[-1, -1, -1], [2, 2]], [[[0, 1], [-1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, 0], [0, 2]], [[[-1, 2]], [[-1, 1]]]), ([[-1, -1, 0], [1, -1]], [[[1, 1]], [[-2, 1]]]), ([[-1, -1, 0], [1, 1]], [[[-1, 1]], []]), ([[-1, -1, 0], [1, 2]], [[[-1, 2]], [[-1, 2]]])], [([[-1, -1, -1], [0, -1]], [[[1, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, 0], [1, 2]], [[[-1, 2]], [[-1, 2]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, -1, 1], [2, 1]], [[[-3, 1], [1, 1]], [[5, 1]]]), ([[-1, -1, 1], [2, 2]], [[[-1, 1], [1, 2]], [[1, 1]]]), ([[-1, -1, 2], [-1, -1]], [[[3, 1], [-2, 1]], [[2, 1]]]), ([[-1, -1, 2], [-1, 1]], [[[1, 1], [2, 1]], []])], [([[-1, -1, -1], [0, 2]], [[[-1, 2], [-1, 2]], [[-1, 1]]]), ([[-1, -1, 1], [0, 2]], [[[-1, 2], [1, 2]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, 0, -1], [0, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, 0, -1], [0, 1]], [[[0, 1], [-1, 1]], [[-1, 1]]]), ([[-1, 0, -1], [0, 2]], [[[0, 1], [-1, 2]], [[-1, 1]]]), ([[-1, 0, -1], [1, -1]], [[[1, 1], [1, 1]], [[-2, 1]]])], [([[-1, -1, -1], [1, -1]], [[[2, 1], [1, 1]], [[-3, 1]]]), ([[-1, -1, 2], [-1, 2]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[-1, -1, -1], [-1, -1]], [[[0, 1], [1, 1]], [[-1, 1]]]), ([[1, 2, 3, 4], [1, 0, 2]], [[[3, 2], [2, 1]], [[-1, 2]]]), ([[-1, 0, 0], [1, 2]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, -1]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, 1]], [[], [[-1, 1]]]), ([[-1, 0, 0], [2, 2]], [[], [[-1, 1]]])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`[[[0, 1], [1, 1]], [[-1, 1]]]`	`[[[0, 1], [1, 1]], [[-1, 1]]]`	Passed
explicit oracle 1	`[[[-3, 4], [-1, 2]], [[-7, 4]]]`	`[[[-3, 4], [-1, 2]], [[-7, 4]]]`	Passed
explicit oracle 2	`[[[3, 2], [2, 1]], [[-1, 2]]]`	`[[[3, 2], [2, 1]], [[-1, 2]]]`	Passed
explicit oracle 3	`[[[-2, 1], [-1, 1]], [[-3, 1]]]`	`[[[-2, 1], [-1, 1]], [[-3, 1]]]`	Passed
explicit oracle 4	`[[[1, 1], [1, 1]], [[-1, 1]]]`	`[[[1, 1], [1, 1]], [[-1, 1]]]`	Passed
explicit oracle 5	`[[[-1, 1], [-1, 1]], [[-1, 1]]]`	`[[[-1, 1], [-1, 1]], [[-1, 1]]]`	Passed
explicit oracle 6	`[[[-1, 2], [-1, 2]], [[-1, 1]]]`	`[[[-1, 2], [-1, 2]], [[-1, 1]]]`	Passed
explicit oracle 7	`[[[2, 1], [1, 1]], [[-3, 1]]]`	`[[[2, 1], [1, 1]], [[-3, 1]]]`	Passed

SHA-256 / 24e5861901f7ca7b84850f7dcc76d13a1387b75c743efcaef09f03fee8fb8e9f

Verification & scope

A deterministic bounded teaching model. Inputs are restricted to the explicit contract; this is not a production algebra library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:39:18.489017+00:00.

Case digest / 02f7bf052afc62e0cc54a290632fd48ce7a51ab13d98eaeba4c36521aa00579b