binius_math/multilinear/
fold.rs

1// Copyright 2026 The Binius Developers
2
3//! Fixing the highest variable of a multilinear to a value.
4//!
5//! Fixing one variable of an `n`-variate multilinear leaves an `(n-1)`-variate one:
6//!
7//! ```text
8//! g(X_0, ..., X_{n-2}) = f(X_0, ..., X_{n-2}, r)
9//! ```
10//!
11//! Coefficients are stored with the highest variable selecting which half of the buffer a
12//! coefficient falls in.
13//! So fixing the highest variable pairs the two halves and leaves the result in the first one.
14//!
15//! Every routine here specializes a generic hypercube routine to the basis `(1 - X, X)`.
16
17use std::ops::Deref;
18
19use binius_compute::{Allocator, BufferData};
20use binius_field::PackedField;
21
22use super::hypercube::{self, OneCube};
23use crate::{FieldBuffer, FieldVec};
24
25/// Fixes the highest variable of a multilinear to a value, in place.
26///
27/// ```text
28/// g(X_0, ..., X_{n-2}) = f(X_0, ..., X_{n-2}, r)
29/// ```
30///
31/// The result occupies the first half of the buffer.
32/// The buffer then reports one variable fewer.
33///
34/// ## Preconditions
35///
36/// * the buffer must have at least one variable
37pub fn fold_highest_var_inplace<P: PackedField, Data: BufferData<P>>(
38	values: &mut FieldBuffer<P, Data>,
39	scalar: P::Scalar,
40) {
41	hypercube::fold_highest_var_inplace::<OneCube, P, Data>(values, scalar);
42}
43
44/// Fixes the highest variable of a multilinear to a value, writing into memory from an allocator.
45///
46/// The input is left untouched.
47/// Use this when the input is borrowed or must be preserved.
48/// Otherwise prefer the form that overwrites the input.
49///
50/// ## Preconditions
51///
52/// * the buffer must have at least one variable
53pub fn fold_highest_var<A: Allocator, P: PackedField, Data: Deref<Target = [P]>>(
54	alloc: &A,
55	values: &FieldBuffer<P, Data>,
56	scalar: P::Scalar,
57) -> FieldVec<P, A> {
58	hypercube::fold_highest_var::<OneCube, A, P, Data>(alloc, values, scalar)
59}
60
61#[cfg(test)]
62mod tests {
63	use binius_compute::GlobalAllocator;
64	use binius_utils::rayon::task_size::{WorkPerItem, min_len_for_work};
65	use proptest::prelude::*;
66	use rand::prelude::*;
67
68	use super::*;
69	use crate::{
70		line::extrapolate_line,
71		test_utils::{B128, Packed128b, random_field_buffer, random_scalars},
72	};
73
74	type P = Packed128b;
75	type F = B128;
76
77	// The packing width is four scalars, so this range straddles it in both directions.
78	const MAX_VARS: usize = 8;
79
80	#[test]
81	fn fold_splits_above_the_task_threshold() {
82		let mut rng = StdRng::seed_from_u64(0);
83
84		// Invariant: a fold splits only once each half holds two minimum tasks.
85		// Below that it runs inline, leaving the parallel path unexercised.
86		//
87		//     words in one half = 2^(n_vars - 1) / scalars per word
88		//     smallest n_vars with words in one half >= 2 * minimum
89		//
90		// Every other fold test is smaller, so this one covers the split.
91		let min_len = min_len_for_work(WorkPerItem::FieldMuls);
92		let n_vars = (2 * min_len * P::WIDTH).next_power_of_two().ilog2() as usize + 1;
93		let half = 1 << (n_vars - 1);
94		let original = random_field_buffer::<P>(&mut rng, n_vars);
95		let challenge = random_scalars::<F>(&mut rng, 1)[0];
96
97		let mut folded = original.clone();
98		fold_highest_var_inplace(&mut folded, challenge);
99		assert_eq!(folded.log_len(), n_vars - 1);
100
101		// Scalar reference: each output interpolates one (lo, hi) pair at the challenge.
102		for i in 0..half {
103			let expected = extrapolate_line(original.get(i), original.get(i | half), challenge);
104			assert_eq!(folded.get(i), expected, "mismatch at index {i}");
105		}
106	}
107
108	#[test]
109	fn folding_a_slice_backed_buffer_matches_folding_an_owned_one() {
110		let mut rng = StdRng::seed_from_u64(0);
111
112		// Invariant: a fold shrinks its buffer, which each backing store does its own way.
113		// A vector drops its tail, a mutable slice re-slices itself.
114		// Both must leave the same coefficients behind.
115		//
116		// Fixture state: one 5-variable buffer, folded twice by the same challenge.
117		//
118		//     owned store      [ c_0 ... c_31 ]  -> [ c'_0 ... c'_15 ]
119		//     slice store      [ c_0 ... c_31 ]  -> [ c'_0 ... c'_15 ]
120		let original = random_field_buffer::<P>(&mut rng, 5);
121		let scalar = random_scalars::<F>(&mut rng, 1)[0];
122
123		let mut expected = original.clone();
124		fold_highest_var_inplace(&mut expected, scalar);
125
126		let mut owned = original;
127		let mut slice = owned.as_mut_view();
128		fold_highest_var_inplace(&mut slice, scalar);
129
130		assert_eq!(slice.log_len(), 4);
131		assert_eq!(slice, expected.as_mut_view());
132	}
133
134	proptest! {
135		#[test]
136		fn the_two_folds_agree(
137			n_vars in 1..=MAX_VARS,
138			seed: u64,
139		) {
140			let mut rng = StdRng::seed_from_u64(seed);
141			let original = random_field_buffer::<P>(&mut rng, n_vars);
142			let scalar = random_scalars::<F>(&mut rng, 1)[0];
143
144			// Out of place leaves the input alone and returns a fresh half-size buffer.
145			let out_of_place = fold_highest_var(&GlobalAllocator, &original, scalar);
146
147			// In place overwrites the input's first half and shrinks it.
148			let mut in_place = original;
149			fold_highest_var_inplace(&mut in_place, scalar);
150
151			prop_assert_eq!(out_of_place.log_len(), n_vars - 1);
152			prop_assert_eq!(out_of_place, in_place);
153		}
154	}
155}
binius_math/multilinear/fold.rs

binius_math/multilinear/
fold.rs
