Irreducible: Additive NTT
Optimization of the NTT implementation in Binius
About
The problem it solves The problem aims to optimize the current version of NTT in Binius. The submitted version tried to mimic the STWO implementation. We did not get this running correctly, but believe that this approach might bring a performance benefit. Our implementation is failing `test_repetition_property`. With the submitted version, we achieved 62.031% time improvement on x86 architecture.
How it's made
Challenges we ran into **Implementing Precomputation of the Gao–Mateer Basis in Rust** The existing Python code relies on deeply nested, generic types. Recasting these abstractions in Rust requires designing appropriate structs and traits **Correct Ordering in Twiddle-Factor Generation for the Gao–Mateer Basis** Develop an algorithm to generate and sequence twiddle factors across multiple basis layers. The current approach emits basis elements in ascending (smallest-first) order, which violates the mathematical requirements of the Gao–Mateer basis. The challenge is to derive the correct layer-by-layer ordering and implement it efficiently. **Debugging the ‘Repetition Property’ Test Failure** The implementation crashes under the repetition-property test due to an unsafe memory error. We would need to pinpoint and resolve the out-of-bounds or invalid-pointer access within our unsafe blocks.