1 unstable release
0.1.0 | Dec 19, 2022 |
---|
#346 in Math
50KB
1K
SLoC
Goldilocks-NTT
Fast number theoretic transforms over the 64-bit Goldilocks prime field $\mathbb{F}_p$ with
$$ p = 2^{63} - 2^{32} + 1 $$
To do
- Optimize transpose.
- Optimize twiddles in Cooley-Tukey.
- Good-Thomas inmplementation.
- Winograd NTT?
Build run test bench
cargo fmt &&\
cargo clippy --all-features --all-targets &&\
cargo test --workspace --all-features --doc -- --nocapture &&\
cargo test --workspace --all-features --all-targets -- --nocapture &&\
cargo doc --workspace --all-features --no-deps
cargo test --all-features -- --test-threads 1 --nocapture
Run Criterion benchmarks
cargo bench --all-features --bench criterion
Create a baseline
cargo bench --all-features --bench criterion -- --save-baseline main
cargo bench --all-features --bench criterion -- --baseline-lenient main
Run NTT benchmarks
cargo bench --all-features --bench ntt -- ntt 32
Check documentation coverage
RUSTDOCFLAGS="-Z unstable-options --show-coverage" cargo doc --workspace --all-features --no-deps
cargo run --bin codegen > small.rs && mv small.rs src/ntt && cargo test ntt::small
Inspect assembly using cargo-show-asm
cargo asm --lib -p goldilocks-ntt "ntt::small::ntt_2" 0
RUSTFLAGS="-Awarnings" cargo asm --lib --all-features -p goldilocks-ntt --rust "field::algo::generic::mul_redc_2"
See also
- [plonky2]
- winterfell
- risc0
http://fftw.org/fftw-paper-ieee.pdf
https://netlib.org/utk/people/JackDongarra/CCDSC-2014/talk35.pdf
Dependencies
~63KB