FA-15746 / Numerics / Open access

Walsh hadamard transform: butterfly block stride · case 01

The exact walsh hadamard transform result violates the stated contract at butterfly block stride.

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

ROOT CAUSE

The butterfly block stride step uses range(0,n,h) instead of range(0,n,2*h).

VERIFIED REPAIR

Use range(0,n,2*h) at the butterfly block stride step.

Unsuccessful approach: The partial repair range(0,n,4*h) still violates the butterfly block stride 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,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, -1, -2, 5], [4, -4, -2, 10]), ([-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])], [([-4, 3], [-1, -7]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([-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]), ([-3, -4, -3, -1], [-11, -1, -3, 3]), ([-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]), ([-5, -1, 0, 2], [-4, -6, -8, -2]), ([-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]), ([-2, 2, 5, 2], [7, -1, -7, -7]), ([-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`	`[4, -4, -2, 10]`	Failed
explicit oracle 2	`None`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 3	`None`	`[-1, -7]`	Failed
explicit oracle 4	`None`	`[5, -1]`	Failed
explicit oracle 5	`None`	`[6, 0]`	Failed
explicit oracle 6	`None`	`[-1, -9]`	Failed
explicit oracle 7	`None`	`[0, 6]`	Failed

SHA-256 / b8a699206c2db5cca210cb234e3c9d579fc47a118e03f1f7796cd9a2d1f95867

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

SHA-256 / 8f6d6aa01a553d5d5e02aa9be9c07250a963ed3b2d4b33dcf44be771099c4bc0

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, -1, -2, 5], [4, -4, -2, 10]), ([-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])], [([-4, 3], [-1, -7]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([-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]), ([-3, -4, -3, -1], [-11, -1, -3, 3]), ([-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]), ([-5, -1, 0, 2], [-4, -6, -8, -2]), ([-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]), ([-2, 2, 5, 2], [7, -1, -7, -7]), ([-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	`[4, -4, -2, 10]`	`[4, -4, -2, 10]`	Passed
explicit oracle 2	`[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 3	`[-1, -7]`	`[-1, -7]`	Passed
explicit oracle 4	`[5, -1]`	`[5, -1]`	Passed
explicit oracle 5	`[6, 0]`	`[6, 0]`	Passed
explicit oracle 6	`[-1, -9]`	`[-1, -9]`	Passed
explicit oracle 7	`[0, 6]`	`[0, 6]`	Passed

SHA-256 / ad358700ab956dbba738142dcbd0068f45910de8c338dbb084606aa08d4a3723

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

Case digest / 632fb47e404ccfb767f090c721c7fda6192d073c832817ae6f780117bb462ab0