From 994c8e29bac4a5969cffb9eb913d2e74692bc71c Mon Sep 17 00:00:00 2001 From: skal Date: Tue, 24 Mar 2026 07:52:25 +0100 Subject: fix(fft): replace iterative twiddle with direct cosf/sinf, add tests A-E fft_radix2 now computes wr=cosf(angle*k)/wi=sinf(angle*k) directly per k, eliminating float drift over long iteration runs. Iterative approach documented in comment for reference. Tests A-E added (bit-reverse, small-N DFT, twiddle drift, DCT small/large N). arrays_match tolerance reverted to 5e-3. TODO.md updated. handoff(Gemini): fft twiddle fix complete, 38/38 tests passing. --- TODO.md | 35 ++++------------------------------- 1 file changed, 4 insertions(+), 31 deletions(-) (limited to 'TODO.md') diff --git a/TODO.md b/TODO.md index 3943a61..0184f0a 100644 --- a/TODO.md +++ b/TODO.md @@ -16,37 +16,10 @@ Procedural spectrogram tool: 50-100× compression (5 KB .spec → ~100 bytes C++ **Status:** 38/38 tests passing -### Fix FFT twiddle factor accumulation bug (`src/audio/fft.cc`) - -**Root cause:** `fft_radix2` updates twiddle factors iteratively over 256 iterations -in the final stage (N=512). Accumulated floating-point drift causes sign flips on -specific DCT coefficients. Round-trip (DCT+IDCT) still works because both sides -make the same errors symmetrically, masking the bug. - -**Fix:** Replace iterative twiddle update with direct `cosf/sinf` per k: -```cpp -// fft_radix2, inner loop — replace: -wr = wr_old * wr_delta - wi * wi_delta; -wi = wr_old * wi_delta + wi * wr_delta; -// with: -wr = cosf(angle * (float)k); -wi = sinf(angle * (float)k); -``` - -**Test plan (`src/tests/audio/test_fft.cc`):** add one test per component, in order: - -- [ ] **A: `bit_reverse_permute`** — for N=8 verify exact index mapping: - 0→0, 1→4, 2→1, 3→6, 4→2, 5→7, 6→3, 7→5 (must be exact) -- [ ] **B: `fft_radix2` small N** — DFT of `[1,0,0,0]` (N=4) via FFT vs direct sum; - all 4 unit impulses. Expect machine epsilon. -- [ ] **C: twiddle accumulation** — compare iterative vs `cosf/sinf` twiddle factors - at k=128..255, stage size=512. **This test must fail before the fix.** -- [ ] **D: `dct_fft` small N** — all 8 unit impulses for N=8 vs reference. - Expect machine epsilon (exact for small N). -- [ ] **E: `dct_fft` large N** — all original test cases (N=512): impulse[0], - impulse[N/2], sinusoidal, complex. Expect < 1e-5 after fix. - -Revert threshold in `arrays_match` back to `5e-3` (or tighter) once fixed. +### ✅ Fix FFT twiddle factor accumulation bug (`src/audio/fft.cc`) — DONE + +`fft_radix2` now computes `wr = cosf(angle*k); wi = sinf(angle*k);` directly per k. +Tests A–E added to `test_fft.cc`. `arrays_match` default tolerance reverted to 5e-3. ## Priority 4: Audio System Enhancements [LOW PRIORITY] -- cgit v1.2.3