FA-15741 / Numerics / Open access

Walsh hadamard transform: butterfly stage termination · case 01

The exact walsh hadamard transform result violates the stated contract at butterfly stage termination.

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

ROOT CAUSE

The butterfly stage termination step uses h>=n//2 instead of h>=n.

VERIFIED REPAIR

Use h>=n at the butterfly stage termination step.

Unsuccessful approach: The partial repair h>n still violates the butterfly stage termination 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//2: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])], [([3, 3], [6, 0]), ([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])], [([-5, 4], [-1, -9]), ([-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	`[-5, -2]`	`[-7, -3]`	Failed
explicit oracle 1	`[-11, -1, 9, 3, -9, -7, -13, 13, 12, -2, 8, -2, -2, -16, -6, 0]`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 2	`[-4, 3]`	`[-1, -7]`	Failed
explicit oracle 3	`[2, 3]`	`[5, -1]`	Failed
explicit oracle 4	`[3, 3]`	`[6, 0]`	Failed
explicit oracle 5	`[-5, 4]`	`[-1, -9]`	Failed
explicit oracle 6	`[3, -3]`	`[0, 6]`	Failed
explicit oracle 7	`[-1, -1]`	`[-2, 0]`	Failed

SHA-256 / 24666b8f56e476743fb48ec3aa57dae18cef67b4c2cc49063d7babd601bf74bb

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])], [([3, 3], [6, 0]), ([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])], [([-5, 4], [-1, -9]), ([-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	`None`	`[-7, -3]`	Failed
explicit oracle 1	`None`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 2	`None`	`[-1, -7]`	Failed
explicit oracle 3	`None`	`[5, -1]`	Failed
explicit oracle 4	`None`	`[6, 0]`	Failed
explicit oracle 5	`None`	`[-1, -9]`	Failed
explicit oracle 6	`None`	`[0, 6]`	Failed
explicit oracle 7	`None`	`[-2, 0]`	Failed

SHA-256 / ab27f5a0730fe9e6cb2ad5d88dd7e2536c9637dbcbc6e67a4086d0fd4aa737be

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])], [([3, 3], [6, 0]), ([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])], [([-5, 4], [-1, -9]), ([-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 / 7b85019de41602c8639006b42f19849c3aa2bdbfde799a27b0e91ea25f04bb8c

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

Case digest / 0d97039508b0daad11958f9afbd297651d2db334a0c8ac3f3198407efc541d9f