Fq reduces after every multiplication. mul calls reduce_wide, a Barrett step, on each 256-bit product before handing back a canonical residue.
The sumcheck round bodies are sums of products, so most of those reductions are thrown away. cubic_contribution performs nine multiplications and returns three numbers, each one a sum of one or two products. sum_coefficients then adds those across the whole table before anything has to be canonical. Barrett reduction is linear over addition, so a sum of unreduced products reduces once to the same residue as reducing each term first.
What it could win: nine reductions per table entry become three per round. Reduction is a large share of a modular multiply, so the round body should drop by something near half.
We already do this for the other field. Wide256 (crates/field/src/gf128/wide.rs) is that accumulator for F128, and PR #40 uses it in the GKR round bodies. Fq has no equivalent.
The width is comfortable. Q100 is just under 2^100, so a product is below 2^200, and summing 2^24 of them stays below 2^224. reduce_wide already accepts a 256-bit input as a (lo, hi) pair, so a 256-bit accumulator covers any table we would build.
This replaces the "raw Montgomery residues" item from #41, which was wrong: Fq is Barrett, so there is no Montgomery conversion to defer.
Effort M.
Fqreduces after every multiplication.mulcallsreduce_wide, a Barrett step, on each 256-bit product before handing back a canonical residue.The sumcheck round bodies are sums of products, so most of those reductions are thrown away.
cubic_contributionperforms nine multiplications and returns three numbers, each one a sum of one or two products.sum_coefficientsthen adds those across the whole table before anything has to be canonical. Barrett reduction is linear over addition, so a sum of unreduced products reduces once to the same residue as reducing each term first.What it could win: nine reductions per table entry become three per round. Reduction is a large share of a modular multiply, so the round body should drop by something near half.
We already do this for the other field.
Wide256(crates/field/src/gf128/wide.rs) is that accumulator forF128, and PR #40 uses it in the GKR round bodies.Fqhas no equivalent.The width is comfortable.
Q100is just under 2^100, so a product is below 2^200, and summing 2^24 of them stays below 2^224.reduce_widealready accepts a 256-bit input as a(lo, hi)pair, so a 256-bit accumulator covers any table we would build.This replaces the "raw Montgomery residues" item from #41, which was wrong:
Fqis Barrett, so there is no Montgomery conversion to defer.Effort M.