layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 🔄 Multiplierless FIR Filter ### Python 🐍 → Rust 🦀 → C++ ⚡ #### A Polyglot Porting Journey @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **Part 1: Background** 🎯 - Multiplierless FIR Filters 🤔 - The Polyglot Strategy 🌐 - Ellipsoid Method Quick Refresher 📐 **Part 2: Architecture** 🏗️ - Spectral Factorization 🧬 - Lowpass Oracle 🎯 - CSD Quantization 🔢 ] .pull-right[ **Part 3: Implementation Comparison** ⚖️ - Algorithmic Differences 🔍 - Key Findings 💡 - FFT vs Matrix Approaches 🧮 **Part 4: Performance Results** 📊 - Benchmark Setup 🛠️ - Runtime Comparison ⏱️ - Takeaways 🎯 ] --- class: nord-light, middle, center ## Part 1: Background 🎯 --- ### 🤔 What is a Multiplierless FIR Filter? A **Finite Impulse Response (FIR)** filter implemented **without general-purpose multipliers**: .mermaid[ <pre> graph LR X["x[n]\nInput"] --> Z0["z⁻¹"] Z0 --> Z1["z⁻¹"] Z1 --> Z2["z⁻¹"] Z2 --> Z3["⋯"] X --> M0["× h₀"] Z0 --> M1["× h₁"] Z1 --> M2["× h₂"] Z2 --> M3["× h₃"] M0 --> SUM["+"] M1 --> SUM M2 --> SUM M3 --> SUM SUM --> Y["y[n]\nOutput"] style X fill:#4caf50,color:#fff style Y fill:#ff9800,color:#fff style M0 fill:#e3f2fd style M1 fill:#e3f2fd style M2 fill:#e3f2fd style M3 fill:#e3f2fd </pre> ] Instead of multipliers, each tap uses **shift-and-add** operations with Canonical Signed Digit (CSD) coefficients, saving **90%+ hardware area** 🎯 --- ### 🧮 Why CSD Representation? **Canonical Signed Digit** represents numbers using only $\{-, 0, +\}$ with **no adjacent non-zero digits**: $$ 28.5_{10} = \texttt{+00-00.+0}_{\text{CSD}} $$ $$ = 32 - 4 + 0.5 = 28.5 $$ **Advantages:** ✨ - **Minimal non-zero digits** → fewer adders in hardware - **Unique representation** — no ambiguity - **Hardware-friendly** — shift + add/subtract only **Example:** $h_i = 0.125 = 2^{-3}$ needs **0 adders** (just a shift) ✅ --- ### 🌐 The Polyglot Strategy Same algorithm, three languages — each with different trade-offs: .mermaid[ <pre> graph LR subgraph "Python 🐍" P1["Prototype first\nEasy to debug"] P2["numpy/scipy stack\nSlow loops"] end subgraph "Rust 🦀" R1["Memory safe\nZero-cost abstractions"] R2["Cargo ecosystem\nNear-C speed"] end subgraph "C++ ⚡" C1["Maximum performance\nFFTW / MKL"] C2["Mature ecosystem\nFine-grained control"] end P1 --> R1 R1 --> C1 style P1 fill:#4caf50,color:#fff style P2 fill:#81c784 style R1 fill:#ff5722,color:#fff style R2 fill:#ff8a65 style C1 fill:#2196f3,color:#fff style C2 fill:#64b5f6 </pre> ] **Why port to Rust?** 🦀 Rust gives C++-like performance with Python-like safety — the "sweet spot". Fewer Heisenbugs, fearless concurrency. --- ### 📐 Ellipsoid Method Refresher The core optimization engine — iteratively shrinks an ellipsoid around the feasible region: $$ \mathcal{E}_{k+1} = \left\{ x \;|\; (x - x_c)^T P_k^{-1} (x - x_c) \le 1 \right\} $$ .mermaid[ <pre> graph LR E0["Initial ellipsoid\nE₀(40²)"] --> O["Oracle:\nviolated constraint?"] O -->|"Yes ✂️"| CUT["Add cutting plane"] CUT --> UPDATE["Shrink ellipsoid\nEₖ → Eₖ₊₁"] UPDATE --> O O -->|"No ✅"| DONE["Optimal found!"] DONE --> SF["Spectral\nFactorization"] SF --> CSDQ["CSD\nQuantize"] style E0 fill:#e3f2fd style O fill:#fff9c4 style CUT fill:#ffe0b2 style UPDATE fill:#f3e5f5 style DONE fill:#c8e6c9 style SF fill:#e1f5fe style CSDQ fill:#fff3e0 </pre> ] For our filter: ${\color{orange} \text{\~50k max iterations}}$, ${\color{green} \text{converges in \~2k}}$ 🎯 --- class: nord-light, middle, center ## Part 2: Architecture 🏗️ --- ### 🧬 Spectral Factorization — The Algorithm Given autocorrelation $r[k]$, find minimum-phase impulse response $h[n]$: $$ R(\omega) = r_0 + 2\sum_{k=1}^{N-1} r_k \cos(k\omega) \ge 0 $$ $$ H_{\text{min}}(\omega) = \exp\left(\frac{1}{2}\ln R(\omega) + j\,\mathcal{H}[\ln\sqrt{R(\omega)}]\right) $$ **Two approaches:** | Method ⚡ | Technique | Speed | Accuracy | |:----------|:----------|:-----:|:--------:| | **FFT-based** 🌀 | Kolmogorov 1939, Hilbert via FFT | 🟢 Fast | 🟢 Good | | **Root-based** 🌱 | Aberth-Ehrlich root finding | 🟡 Medium | 🟢 Best | Both methods produce **identical energy**: $\sum h[n]^2 = r[0]$ ✅ --- ### 🧬 Spectral Factorization — Implementation **Step-by-step (FFT method):** 1. **Oversample** $R(\omega)$ by $100\times$ the filter order $N$ → $m = 100N$ points 2. **Compute** $\alpha(\omega) = \frac{1}{2} \ln R(\omega)$ 3. **Hilbert transform** via FFT to get minimum-phase $\phi(\omega)$: $$ \phi = \texttt{IFFT}\big(j \cdot \texttt{FFT}(\alpha)\big), \quad \text{flip negative freqs} $$ 4. **Downsample** to $N$ frequency points (DFT grid) 5. **Reconstruct**: $h = \texttt{IFFT}\big(\exp(\alpha + j\phi)\big)$ The minimum-phase response **preserves magnitude** $|H(\omega)| = \sqrt{R(\omega)}$ while having **all zeros inside the unit circle** 🔄 --- ### 🎯 Lowpass Oracle Design The oracle checks **three constraint types** in round-robin fashion: .mermaid[ <pre> graph LR START(["x = r[k]"]) --> NR["x[0] ≥ 0?\nNon-negative real"] NR -->|No ❌| CUT1["g = [-1,0,...]\nf = -x[0]"] NR -->|Yes ✅| PB["Passband:\nL² ≤ R(ω) ≤ U²"] PB -->|Violated ❌| CUT2["g = ±Aₚ(ω)\nf = R(ω) ∓ bound"] PB -->|OK ✅| SB["Stopband:\nR(ω) ≤ S²"] SB -->|Violated ❌| CUT3["g = ±Aₛ(ω)\nf = R(ω) - S²"] SB -->|OK ✅| NNR["Non-redundant:\nR(ω) ≥ 0"] NNR -->|Violated ❌| CUT4["g = -Aₙᵣ(ω)\nf = -R(ω)"] NNR -->|OK ✅| OPT["Optimal ✅"] style NR fill:#e3f2fd style PB fill:#fff9c4 style SB fill:#ffe0b2 style NNR fill:#f3e5f5 style OPT fill:#c8e6c9 style CUT1 fill:#ffcdd2 style CUT2 fill:#ffcdd2 style CUT3 fill:#ffcdd2 style CUT4 fill:#ffcdd2 </pre> ] Each violation produces a **cutting plane** $(g, f)$ to shrink the ellipsoid 🎯 --- ### 🔢 CSD Quantization Pipeline After optimization, coefficients are quantized to CSD format: .mermaid[ <pre> graph LR R["r* (optimal)\nAutocorrelation"] --> SF["Spectral\nFactor"] SF --> H["h (continuous)\nImpulse response"] H --> CSDQ["CSD quantize\n≤ nnz non-zero digits"] CSDQ --> HCSD["h̃ (CSD)"] HCSD --> INV["Inverse Spectral\nFactor"] INV --> RCSD["r̃ (CSD)\nAutocorrelation"] style R fill:#4caf50,color:#fff style SF fill:#2196f3,color:#fff style H fill:#ff9800,color:#fff style CSDQ fill:#9c27b0,color:#fff style HCSD fill:#e91e63,color:#fff style INV fill:#00bcd4,color:#fff style RCSD fill:#ff5722,color:#fff </pre> ] **Key insight:** The quantized ${\color{orange} \tilde{r}}$ is fed back into the oracle for **retry** — if the cut has no effect, the quantization error is added to the cutting plane: ${\color{red} h_c \mathrel{+}= g_c \cdot (\tilde{r} - r)}$ 🔄 --- class: nord-light, middle, center ## Part 3: Implementation Comparison ⚖️ --- ### 🔍 Module Mapping: C++ → Rust → Python .font-sm[ | Module 📦 | C++ ⚡ | Rust 🦀 | Python 🐍 | |:----------|:-------|:--------|:----------| | **FFT Engine** 🌀 | FFTW3 (`rfft` + complex FFT) | realfft 3.x + rustfft 6.x (power spectrum via `rfft`, Hilbert via complex FFT) | numpy.fft (power spectrum via `rfft`) ✅ | | **Root Finder** 🌱 | ginger-cpp (Aberth-Ehrlich) | ginger-rs (Aberth-Ehrlich) | ginger-py (Aberth-Ehrlich) | | **CSD Quant** 🔢 | `csd_quantize()` direct double→double | `csd_quantize_direct()` direct double→double ✅ | `csd_quantize()` direct double→double ✅ | | **Ellipsoid** 📐 | ellalgo-cpp | ellalgo-rs | ellalgo (Python) | | **Constraint Matrix** 📊 | Ap/As/Anr (3 split matrices) | Ap/As/Anr (same as C++) | Single spectrum w/ index ranges | | **Build System** 🏗️ | xmake / CMake | Cargo | pip / setuptools | ] --- ### 🧮 FFT Approach: Three Ways **Computing the Power Spectrum $R(\omega)$:** | Language | Method | Complexity | |:---------|:-------|:----------:| | **C++** ⚡ | Zero-pad $r$ to $m$, `rfft`, then $R[k] = 2\,\text{Re}(S[k]) - r_0$ | $O(m\log m)$ | | **Python** 🐍 | Zero-pad $r$ to $m$, `np.fft.rfft`, then $R[k] = 2\,\text{Re}(S[k]) - r_0$ (now same as C++/Rust) | $O(m\log m)$ ✅ | | **Rust** 🦀 | Zero-pad $r$ to $m$, `rfft`, then $R[k] = 2\,\text{Re}(S[k]) - r_0$ (matches C++) | $O(m\log m)$ ✅ | All three now use the **same FFT-based approach** for the power spectrum, replacing the matrix-vector multiply. For typical values ($n=32$, $m=3200$), the FFT approach is slightly faster and scales better for larger $n$. 🎯 --- ### 🌱 Root vs FFT: Which is Faster? **Surprising result:** It depends entirely on the **language implementation quality**! .font-sm[ | Lang 🚀 | Method | n=7 | n=16 | n=32 | Winner 🏆 | |:--------|:-------|:---:|:----:|:----:|:---------:| | **Python** 🐍 | root 🌱 | 1.6 ms | — | 28.9 ms | | | | fft 🌀 | **0.4 ms** | — | **2.2 ms** | 🌀 FFT | | **Rust** 🦀 | root 🌱 | **0.017 ms** | **0.083 ms** | **0.493 ms** | 🌱 Root | | | fft 🌀 | **0.031 ms** | **0.098 ms** | **0.512 ms** | 🌀 FFT (new) | | **C++** ⚡ | root 🌱 | **0.037 ms** | **0.163 ms** | 0.780 ms | ⚖️ Tie | | | fft 🌀 | 0.222 ms | 0.335 ms | **0.639 ms** | | ] **Analysis:** 🤔 - **Python**: numpy is optimized Fortran/C; ginger is pure-Python → **FFT crushes root** (10-13×) - **Rust**: ginger-rs is fast native code; `realfft` replaces naive matrix loops → **root ≈ FFT, now neck-and-neck** (previously 5-10× gap) ✅ - **C++**: FFTW3 is extremely optimized; ginger is also optimized native code → **roughly equal, crossover at n≈32** **Takeaway:** Algorithm choice is secondary to **implementation quality** in each language! 🎯 --- ### 💡 Key Finding: rustfft Normalization **Critical discovery** during the Rust port: `rustfft` v6.x does **NOT** normalize inverse FFT output! | Library | Forward FFT | Inverse FFT | |:--------|:-----------:|:-----------:| | **FFTW3** ⚡ | No scaling | $\div N$ | | **numpy.fft** 🐍 | No scaling | $\div N$ | | **rustfft 6.x** 🦀 | No scaling | **No scaling!** 😱 | **Fix:** Explicitly divide by $N$ after every IFFT call: ```text phi[i] = alphatmp[i].re * inv_m; // ÷ m after Hilbert IFFT h[i] = complex_out[i].re * inv_n; // ÷ n after final IFFT ``` Without this fix, the output energy was **$N^2$ times too large**! 🔴 --- ### 🔢 CSD Quantization: Double vs String **C++** has a dedicated `csd_quantize()` that processes doubles directly: ```text bit_val = ldexp(1.0, ceil(log2(|num| * 1.5)) - 1) while nnz > 0 && |num| > 1e-100: if |1.5 * num| > bit_val: result += sign(num) * bit_val num -= sign(num) * bit_val nnz -= 1 bit_val *= 0.5 ``` **Rust** and **Python** now use direct double→double (same as C++): `csd_quantize()` via `ldexp(1.0, ceil(log2(|num|·1.5)) - 1)` — no string allocation. This was the **#1 bottleneck** in the hot path. ✅ All three languages now share the **same direct quantization algorithm**, eliminating the string round-trip overhead that affected the original Python and Rust implementations. The string-based approach (`to_csdnnz()/to_decimal()`) is still available for **debugging readability** 🐛 --- ### ⚖️ Constraint Matrix Organization **C++ / Rust approach** (Ap/As/Anr split): .mermaid[ <pre> graph TD A["Full Spectrum Matrix A\n(m × n)"] --> AP["Ap: passband rows\n0 ≤ ω ≤ ωₚ"] A --> AS["As: stopband rows\nωₛ ≤ ω ≤ π"] A --> ANR["Anr: transition rows\nωₚ < ω < ωₛ"] style A fill:#e3f2fd style AP fill:#c8e6c9 style AS fill:#ffcdd2 style ANR fill:#fff9c4 </pre> ] **Python approach**: Single matrix + index tracking (idx1, idx2, idx3). Less code duplication but harder to verify correctness. Both achieve **identical constraint checking** — just different organizational philosophies. 🤝 --- class: nord-light, middle, center ## Part 4: Performance Results 📊 --- ### 🛠️ Benchmark Setup .pull-left[ **Test Configuration:** 🧪 | Parameter | Value | |:----------|:-----:| | Filter order $N$ | 32 | | Passband edge | $0.12\pi$ | | Stopband edge | $0.20\pi$ | | CSD non-zero digits | 7 | | Max iterations | 50,000 | | Tolerance | $10^{-14}$ | ] .pull-right[ **Environment:** Windows x64, MSVC 2026, Python 3.14, Rust 1.96, Release builds. 7 runs each (2 warmup + 5 measured). 🔄 ] --- ### ⏱️ Runtime Comparison | Implementation 🚀 | Avg Time ⏱️ | Min ⏱️ | Max ⏱️ | vs C++ ⚡ | vs Rust 🦀 | |:-----------------|:----------:|:------:|:------:|:---------:|:-----------:| | **C++ (FFTW3)** ⚡ | **303 ms** | 274 ms | 338 ms | **1.0×** | 1.06× slower | | **Rust (realfft)** 🦀 | **286 ms** | 261 ms | 310 ms | **0.95× faster** 🔥 | **1.0×** | | **Python (numpy)** 🐍 | **4046 ms** | 3865 ms | 4277 ms | 13.4× slower | 14.2× slower | .mermaid[ <pre> graph TD subgraph "Relative Performance" CPP["C++\n303ms\n1.0×"] -.-> RUST["Rust 🏆\n286ms\n0.95×"] RUST --> PY["Python\n4046ms\n14.2×"] end style CPP fill:#2196f3,color:#fff style RUST fill:#4caf50,color:#fff style PY fill:#ff5722,color:#fff </pre> ] --- ### 📊 Breakdown: Where Does the Time Go? .mermaid[ <pre> graph TD subgraph "Optimization Loop (~95% of time)" O1["Constraint check\n(matrix dot product)"] O2["Ellipsoid update"] O3["Cutting plane"] O1 --> O2 --> O3 --> O1 end subgraph "Spectral Factorization (~5%)" S1["Power spectrum\n(FFT or matrix)"] S2["Hilbert transform\n(FFT-based)"] S1 --> S2 end style O1 fill:#e3f2fd style O2 fill:#f3e5f5 style O3 fill:#fff9c4 style S1 fill:#e8f5e9 style S2 fill:#fff3e0 </pre> ] **Bottleneck:** The optimization loop executes **thousands of matrix-vector dot products** (one per constraint check). Python pays a heavy overhead here due to CPython interpreter loop and dynamic dispatch. 🐢 **Optimization impact:** After applying optimizations, Rust's per-iteration cost dropped from **0.324 ms** to **0.113 ms** (65% reduction), making it faster per-iteration than C++ (0.164 ms). Python's time dropped from **5551 ms to 4046 ms** (27% reduction), driven by direct CSD quantization, FFT-based power spectrum, and pre-allocated gradient buffers. Python's per-iteration cost also improved from **2.74 ms to 2.39 ms** (13% reduction). 🐍✅ The remaining iteration count differences (C++ 1,850, Python 1,693, Rust 2,530) are due to floating-point trajectory differences between FFTW3, numpy.fft, and realfft — not algorithmic inefficiency. 🎯 --- ### 📈 Convergence Comparison All three converge to **valid, equivalent solutions**: | Metric 📊 | C++ ⚡ | Python 🐍 (optimized) | Rust 🦀 (optimized) | |:----------|:-----:|:---------------------:|:--------------------:| | Iterations | 1,850 | 1,693 | 2,530 | | $h[0]$ | 0.009918 | 0.009451 | 0.009454 | | $\sum h^2$ | 0.1365 | 0.1356 | 0.1359 | | **Per-iter cost** | **0.164 ms** 🐢 | **2.39 ms** 🐌 | **0.113 ms** 🚀 | **Same energy** ✅ — the ellipsoid method naturally takes different paths due to floating-point sensitivity, but the **physical solution quality is equivalent**. The coefficients satisfy the same passband/stopband constraints within the specified tolerances. 🎯 --- ### 🔍 Wait — Are They Using the Same Parameters? .font-sm[ | Parameter 📋 | C++ ⚡ | Python 🐍 | Rust 🦀 | |:------------|:-----:|:---------:|:-------:| | filter_order | 32 | 32 | 32 | | passband_edge | 0.12 | 0.12 | 0.12 | | stopband_edge | 0.2 | 0.2 | 0.2 | | passband_ripple | 0.125 | 0.125 | 0.125 | | stopband_attenuation | 0.125 | 0.125 | 0.125 | | csd_nnz | 7 | 7 | 7 | | discretization_factor | 15 | 15 | 15 | | max_iters | 50,000 | 50,000 | 50,000 | | tolerance | $10^{-14}$ | $10^{-14}$ | $10^{-14}$ | | ellipsoid_radius | 40.0 | 40.0 | 40.0 | ] All three read the **same JSON spec file** and have **identical defaults** for any missing fields. ✅ --- ### 🤔 So Why Aren't the Solutions Identical? If parameters are the same, why does each language produce different coefficients? .mermaid[ <pre> graph TD P["Same Parameters ✅"] --> C["CSD Quantization:"] P --> F["FFT Library:"] P --> A["FP Accumulation:"] C --> C1["All three:\ndirect double→double\ncsd_quantize() ✅"] C --> C2["(was Python/Rust string\nround-trip, fixed now)"] F --> F1["C++: FFTW3 (rfft)"] F --> F2["Python: numpy.fft\n(rfft, like C++)"] F --> F3["Rust: realfft\n(rfft, like C++)"] A --> A1["Over 2000+ iterations,\nULP differences compound 🔄"] C1 --> D["Different cutting planes →"] F1 --> D F2 --> D F3 --> D A1 --> D D --> R["Different Pareto-optimal points\nAll satisfying same constraints ✅"] style P fill:#c8e6c9 style C fill:#fff9c4 style F fill:#fff9c4 style A fill:#fff9c4 style D fill:#ffe0b2 style R fill:#c8e6c9 </pre> ] **Bottom line:** The ellipsoid method is a **first-order algorithm** — unlike interior-point or SQP solvers, it has no mechanism to converge to a unique optimum. Different floating-point trajectories → different valid solutions. All three pass the same specification. 🎯 --- ### ✅ Optimization Results: Closing the Gap **Rust went from 1.9× slower to 0.95× faster than C++ — all four optimizations implemented:** 🔧 1. **Direct CSD quantization** 🔢 — replaced `to_csdnnz()→string→to_decimal()` round-trip with direct `f64→f64` (matching C++ `ldexp` algorithm): **~3× faster quantization** ✅ 2. **FFT-based power spectrum** 🌀 — replaced $O(m \cdot n)$ matrix-vector multiply with $O(m \log m)$ real FFT via `realfft` crate: **~10× faster for R(ω)** ✅ 3. **Pre-allocate gradient buffer** 📦 — added pre-allocated `g_buf` to `LowpassOracle` struct; uses `ptr::copy_nonoverlapping` (memcpy) instead of per-iteration `Arr::new` + element-wise copy: **~15% speedup** ✅ 4. **Rayon NOT beneficial for n=32** ⚡ — rayon's `par_iter` overhead dominates for 32-element vectors. Sequential iterator with LLVM auto-vectorization is **35× faster** for dot products this small. Rayon only benefits when `n > 1000`. 🔍 **Result:** Rust **286 ms** avg vs C++ **303 ms** avg — **Rust wins by ~5%** 🏆 --- ### 🐍 Python Optimization Results **Python went from 5551 ms to 4046 ms (27% reduction, 1.37× faster):** 🔧 1. **Direct CSD quantization** 🔢 — same `csd_quantize()` via `ldexp` as C++/Rust: **eliminates string allocation** in hot path ✅ 2. **FFT-based power spectrum** 🌀 — replaced `O(m·n)` matrix multiply with `np.fft.rfft` (Fortran-optimized, `O(m log m)`): **matches C++/Rust approach** ✅ 3. **Pre-allocate gradient buffer** 📦 — single `np.zeros(N)` in `Oracle.__init__` avoids per-call allocation in the constraint-checking hot loop: **modest win** ✅ **Limitation:** Python's **interpreter overhead** for the constraint-checking loop (~480 rows × 1700 iterations = ~816k pure-Python iterations) is the dominant cost. No amount of micro-optimization can match compiled C++/Rust here — the **27% reduction** is from eliminating string/allocation overhead in the hot path, but the loop itself remains Python-bound. 🐢 --- class: nord-light, middle, center ## Part 5: Lessons Learned 💡 --- ### 📚 Key Takeaways 1. **Polyglot strategies work** 🌐 — Python for prototyping, Rust for production, C++ for maximum performance 2. **Rust CAN match C++** 🦀🏆 — after optimization, Rust **beats C++ by ~5%** (286 ms vs 303 ms). Memory safety and zero-cost abstractions don't have to cost performance. 3. **Optimization is systematic** 🔧 — direct CSD quantization, FFT-based power spectrum, and pre-allocated buffers closed the 1.9× gap. Each contributed incrementally. 4. **Rayon isn't always faster** ⚡ — for small vectors (n=32), rayon's parallel overhead overwhelms the computation. A simple sequential iterator gave **35× better** performance than `par_iter`. Always measure! 5. **Know your FFT library** 🌀 — `rustfft` doesn't normalize IFFT; FFTW and numpy do. Always verify! 6. **CSD via string is slow** 🔢 — direct double-to-double quantization is ~3× faster for this workload. **All three languages now use this approach.** ✅ 7. **Python's bottleneck is the interpreter loop** 🐍 — not CSD quantization or spectrum computation. The constraint-check loop executes ~816k pure-Python iterations. Micro-optimizations help (~27%), but the **10-14× gap to compiled languages** will persist without rewriting the hot loop in Cython/Numba. 8. **Convergence ≠ determinism** 📊 — ellipsoid method takes different paths across languages, but reaches equivalent solutions --- ### 🔮 Future Work .mermaid[ <pre> graph LR subgraph "Completed ✅" C1["Direct csd_quantize()\nin Rust + Python"] C2["rfft for power\nspectrum (all 3 langs)"] C3["Pre-allocated\ngradient buffer"] end subgraph "Future 🚀" M1["SIMD-optimized\nArr operations"] M2["Benchmark harness\n(hyperfine/criterion)"] M3["GitHub Actions CI\nfor all 3 langs"] end style C1 fill:#4caf50,color:#fff style C2 fill:#4caf50,color:#fff style C3 fill:#4caf50,color:#fff style M1 fill:#fff9c4 style M2 fill:#fff9c4 style M3 fill:#fff9c4 </pre> ] **Note:** Parallel constraint checking with rayon was tried but **did not help** for this workload (n=32). Rayon's overhead for small vector dot products dominated the computation — sequential auto-vectorized loops were 35× faster. For larger filter orders (n > 512), re-evaluating parallelism may be worthwhile. 🔄 --- count: false class: nord-dark, middle, center # 🙋 Q&A ### Questions? Discussion? 💬 **Code:** 🐙 - C++: [github.com/luk036/multiplierless-cpp](https://github.com/luk036/multiplierless-cpp) - Python: [github.com/luk036/multiplierless](https://github.com/luk036/multiplierless) - Rust: [github.com/luk036/multiplierless-rs](https://github.com/luk036/multiplierless-rs) --- count: false class: nord-dark, middle, center # 👏 Thank You ### Multiplierless FIR Filter Design in 3 Languages Python 🐍 · Rust 🦀 · C++ ⚡ ```text Slides built with Remark.js 🎉 KaTeX 📐 | Mermaid 🧩 | Nord Theme 🌙 ```