binius_math/
line.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! Extrapolation of the line through two points.
5
6use binius_field::field::FieldOps;
7
8/// Extrapolates a line through two points.
9///
10/// The two points are `(0, x_0)` and `(1, x_1)`.
11/// The line through them, evaluated at the parameter `z`, is
12///
13/// ```text
14/// x_0 + (x_1 - x_0) * z
15/// ```
16///
17/// The two points are also the halves a variable splits a multilinear into.
18/// Read that way, this binds that variable to `z`.
19#[inline]
20pub fn extrapolate_line<F: FieldOps>(x0: F, x1: F, z: F) -> F {
21	// The line is affine in `z`, so one multiplication and two additions suffice.
22	x0.clone() + (x1 - x0) * z
23}
24
25#[cfg(test)]
26mod tests {
27	use binius_field::{Field, Random, field::FieldOps};
28	use rand::prelude::*;
29
30	use super::*;
31	use crate::test_utils::{B128, Packed128b};
32
33	type P = Packed128b;
34	type F = B128;
35
36	#[test]
37	fn extrapolate_line_reads_the_endpoints_at_zero_and_one() {
38		let mut rng = StdRng::seed_from_u64(0);
39
40		// The line is pinned by its two endpoints, which is what fixes the argument order:
41		//
42		//     z = 0  ->  x_0
43		//     z = 1  ->  x_1
44		let x0 = F::random(&mut rng);
45		let x1 = F::random(&mut rng);
46		assert_eq!(extrapolate_line(x0, x1, F::ZERO), x0);
47		assert_eq!(extrapolate_line(x0, x1, F::ONE), x1);
48
49		// A packed field is a vector of independent lanes, and the same must hold lane by lane.
50		let x0_packed = P::random(&mut rng);
51		let x1_packed = P::random(&mut rng);
52		assert_eq!(extrapolate_line(x0_packed, x1_packed, P::zero()), x0_packed);
53		assert_eq!(extrapolate_line(x0_packed, x1_packed, P::one()), x1_packed);
54	}
55
56	#[test]
57	fn extrapolate_line_matches_the_closed_form() {
58		let mut rng = StdRng::seed_from_u64(0);
59
60		// Away from the endpoints the value is the closed form of the line through them.
61		// Drawing `z` from a proper subfield also covers the cheaper subfield multiplication.
62		for _ in 0..10 {
63			let x0 = F::random(&mut rng);
64			let x1 = F::random(&mut rng);
65			let z = F::from(rng.next_u64() as u128);
66			assert_eq!(extrapolate_line(x0, x1, z), x0 + (x1 - x0) * z);
67		}
68	}
69}
binius_math/line.rs

binius_math/
line.rs
