bench_poly_eval/
lib.rs

1//! Polynomial evaluation via Horner's method — mirrors
2//! `p3_uni_stark::verify`'s AIR constraint polynomial evaluation at
3//! FRI challenge points.
4//!
5//! For each of `NUM_POINTS` challenge points `x`, evaluate a degree-
6//! `(DEGREE - 1)` polynomial
7//! `p(x) = c_0 + c_1·x + c_2·x² + … + c_{DEGREE-1}·x^(DEGREE-1)` via
8//! Horner's method. Memory access is a sequential streaming read of
9//! `coeffs[]` (4096 × u64 = 32 KiB, fits in L1). Compute: `DEGREE-1`
10//! chained `mul + add` per point — totally dependent (each step
11//! needs the previous result).
12//!
13//! Complements:
14//!   - `goldilocks-mul`: chained mul, no add, no memory
15//!   - `mini-verifier`: closed-form constraint eval (no memory access)
16//!   - `fri-fold-tree`: scattered memory access
17
18#![cfg_attr(target_os = "none", no_std)]
19
20use nub_rt as _;
21
22#[cfg(target_os = "none")]
23extern crate alloc;
24
25#[cfg(target_os = "none")]
26use alloc::vec::Vec;
27
28use gp::{add, canonical, mul, ZERO};
29
30const DEGREE: usize = 4096;
31const NUM_POINTS: usize = 64;
32const SEED_COEFFS: u64 = 0x123456789abcdef0;
33const SEED_POINTS: u64 = 0xfedcba9876543210;
34const MULTIPLIER: u64 = 0x9E3779B97F4A7C15;
35
36pub fn poly_eval_bench() -> u32 {
37    let mut coeffs: Vec<u64> = Vec::with_capacity(DEGREE);
38    let mut x = SEED_COEFFS;
39    let mut i = 0;
40    while i < DEGREE {
41        x = mul(x, MULTIPLIER);
42        coeffs.push(x);
43        i += 1;
44    }
45
46    let mut points: [u64; NUM_POINTS] = [0; NUM_POINTS];
47    let mut y = SEED_POINTS;
48    let mut j = 0;
49    while j < NUM_POINTS {
50        y = mul(y, MULTIPLIER);
51        points[j] = y;
52        j += 1;
53    }
54
55    let mut accum = ZERO;
56    let mut k = 0;
57    while k < NUM_POINTS {
58        let z = points[k];
59        let mut result = coeffs[DEGREE - 1];
60        let mut idx = DEGREE - 1;
61        while idx > 0 {
62            idx -= 1;
63            result = add(mul(result, z), coeffs[idx]);
64        }
65        accum = add(accum, result);
66        k += 1;
67    }
68
69    (canonical(accum) & 0xFFFF_FFFF) as u32
70}
bench_poly_eval/lib.rs

bench_poly_eval/
lib.rs
