FA-15756 / Numerics / Open access

Walsh hadamard transform: difference wing · case 01

The exact walsh hadamard transform result violates the stated contract at difference wing.

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

ROOT CAUSE

The difference wing step uses v-u instead of u-v.

VERIFIED REPAIR

Use u-v at the difference wing step.

Unsuccessful approach: The partial repair u+v still violates the difference wing invariant.

Case contract

Input integer list of power-of-two length; return unnormalized Sylvester-ordered Walsh-Hadamard transform. Bounds: length<=1024.

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=x[:];n=len(a);h=1
    for _ in range(10):
     if h>=n:break
     for i in range(0,n,2*h):
      for j in range(i,i+h):
       if j+h>=n:return None
       u,v=a[j],a[j+h]
       a[j]=u+v
       a[j+h]=v-u
     h=h*2
    return a
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-4, 3], [-1, -7]), ([2, 3], [5, -1]), ([3, 3], [6, 0]), ([-5, 4], [-1, -9]), ([3, -3], [0, 6]), ([-1, -1], [-2, 0])], [([-4, 3], [-1, -7]), ([3, 3], [6, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-3, -3], [-6, 0]), ([-4, 0], [-4, -4]), ([-2, 5], [3, -7]), ([3, 1], [4, 2])], [([2, 3], [5, -1]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-5, 3], [-2, -8]), ([-2, 4], [2, -6]), ([3, 2], [5, 1]), ([-1, 5], [4, -6])], [([-5, 4], [-1, -9]), ([2, 2], [4, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([4, 4, 3, 4], [15, -1, 1, 1]), ([1, -2, -5, 5], [-1, -7, -1, 13]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([2, -2, -2, -1], [-3, 3, 3, 5])], [([3, -3], [0, 6]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([2, -2, -2, 4], [2, -2, -2, 10]), ([5, -2, 5, 4], [12, 8, -6, 6]), ([5, -1, -5, 3], [2, -2, 6, 14]), ([-2, -5, 1, -3], [-9, 7, -5, -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	`[-7, 3]`	`[-7, -3]`	Failed
explicit oracle 1	`[1, 3, -17, 1, 11, -23, -19, -13, 23, 1, 1, -5, -7, -9, 7, 13]`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 2	`[-1, 7]`	`[-1, -7]`	Failed
explicit oracle 3	`[5, 1]`	`[5, -1]`	Failed
explicit oracle 4	`[6, 0]`	`[6, 0]`	Passed
explicit oracle 5	`[-1, 9]`	`[-1, -9]`	Failed
explicit oracle 6	`[0, -6]`	`[0, 6]`	Failed
explicit oracle 7	`[-2, 0]`	`[-2, 0]`	Passed

SHA-256 / fd92ef3edf114e74adea9f0a7ac3eb8be22c272535f2d96211c8adf56c8da531

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=x[:];n=len(a);h=1
    for _ in range(10):
     if h>=n:break
     for i in range(0,n,2*h):
      for j in range(i,i+h):
       if j+h>=n:return None
       u,v=a[j],a[j+h]
       a[j]=u+v
       a[j+h]=u+v
     h=h*2
    return a
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-4, 3], [-1, -7]), ([2, 3], [5, -1]), ([3, 3], [6, 0]), ([-5, 4], [-1, -9]), ([3, -3], [0, 6]), ([-1, -1], [-2, 0])], [([-4, 3], [-1, -7]), ([3, 3], [6, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-3, -3], [-6, 0]), ([-4, 0], [-4, -4]), ([-2, 5], [3, -7]), ([3, 1], [4, 2])], [([2, 3], [5, -1]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-5, 3], [-2, -8]), ([-2, 4], [2, -6]), ([3, 2], [5, 1]), ([-1, 5], [4, -6])], [([-5, 4], [-1, -9]), ([2, 2], [4, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([4, 4, 3, 4], [15, -1, 1, 1]), ([1, -2, -5, 5], [-1, -7, -1, 13]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([2, -2, -2, -1], [-3, 3, 3, 5])], [([3, -3], [0, 6]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([2, -2, -2, 4], [2, -2, -2, 10]), ([5, -2, 5, 4], [12, 8, -6, 6]), ([5, -1, -5, 3], [2, -2, 6, 14]), ([-2, -5, 1, -3], [-9, 7, -5, -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	`[-7, -7]`	`[-7, -3]`	Failed
explicit oracle 1	`[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 2	`[-1, -1]`	`[-1, -7]`	Failed
explicit oracle 3	`[5, 5]`	`[5, -1]`	Failed
explicit oracle 4	`[6, 6]`	`[6, 0]`	Failed
explicit oracle 5	`[-1, -1]`	`[-1, -9]`	Failed
explicit oracle 6	`[0, 0]`	`[0, 6]`	Failed
explicit oracle 7	`[-2, -2]`	`[-2, 0]`	Failed

SHA-256 / 882ec8252eb43f086ec278ce6982b37358db4ddc88650f6d67a30f57a99831ed

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=x[:];n=len(a);h=1
    for _ in range(10):
     if h>=n:break
     for i in range(0,n,2*h):
      for j in range(i,i+h):
       if j+h>=n:return None
       u,v=a[j],a[j+h]
       a[j]=u+v
       a[j+h]=u-v
     h=h*2
    return a
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-4, 3], [-1, -7]), ([2, 3], [5, -1]), ([3, 3], [6, 0]), ([-5, 4], [-1, -9]), ([3, -3], [0, 6]), ([-1, -1], [-2, 0])], [([-4, 3], [-1, -7]), ([3, 3], [6, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-3, -3], [-6, 0]), ([-4, 0], [-4, -4]), ([-2, 5], [3, -7]), ([3, 1], [4, 2])], [([2, 3], [5, -1]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-5, 3], [-2, -8]), ([-2, 4], [2, -6]), ([3, 2], [5, 1]), ([-1, 5], [4, -6])], [([-5, 4], [-1, -9]), ([2, 2], [4, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([4, 4, 3, 4], [15, -1, 1, 1]), ([1, -2, -5, 5], [-1, -7, -1, 13]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([2, -2, -2, -1], [-3, 3, 3, 5])], [([3, -3], [0, 6]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([2, -2, -2, 4], [2, -2, -2, 10]), ([5, -2, 5, 4], [12, 8, -6, 6]), ([5, -1, -5, 3], [2, -2, 6, 14]), ([-2, -5, 1, -3], [-9, 7, -5, -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	`[-7, -3]`	`[-7, -3]`	Passed
explicit oracle 1	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Passed
explicit oracle 2	`[-1, -7]`	`[-1, -7]`	Passed
explicit oracle 3	`[5, -1]`	`[5, -1]`	Passed
explicit oracle 4	`[6, 0]`	`[6, 0]`	Passed
explicit oracle 5	`[-1, -9]`	`[-1, -9]`	Passed
explicit oracle 6	`[0, 6]`	`[0, 6]`	Passed
explicit oracle 7	`[-2, 0]`	`[-2, 0]`	Passed

SHA-256 / d00ae3396e4e75a388fa8d5b600f3a4c379dc086729a01a5d92a4286763731f6

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:30.069187+00:00.

Case digest / c62470992154a3e8890ade6d4c0e3e8ddb0179b0071dfefa6949ea2e45f5a4d4