binius_circuits/bignum/
big_uint_divide.rs

1// Copyright 2025 Irreducible Inc.
2//! BigUint division hint implementation
3
4use binius_core::Word;
5use binius_frontend::{CircuitBuilder, Wire, hints::Hint};
6
7use super::num_biguint_from_u64_limbs;
8
9pub struct BigUintDivideHint;
10
11impl BigUintDivideHint {
12	pub const fn new() -> Self {
13		Self
14	}
15
16	/// BigUint division.
17	///
18	/// Returns `(quotient, remainder)` of the division of `dividend` by `divisor`.
19	///
20	/// This is a hint - a deterministic computation that happens only on the prover side.
21	/// The result should be additionally constrained by using bignum circuits to check that
22	/// `remainder + divisor * quotient == dividend`.
23	pub fn call(
24		builder: &CircuitBuilder,
25		dividend: &[Wire],
26		divisor: &[Wire],
27	) -> (Vec<Wire>, Vec<Wire>) {
28		let inputs: Vec<Wire> = dividend.iter().chain(divisor).copied().collect();
29		let mut out = builder.call_hint(Self::new(), &[dividend.len(), divisor.len()], &inputs);
30		let remainder = out.split_off(dividend.len());
31		(out, remainder)
32	}
33}
34
35impl Default for BigUintDivideHint {
36	fn default() -> Self {
37		Self::new()
38	}
39}
40
41impl Hint for BigUintDivideHint {
42	const NAME: &'static str = "binius.biguint_divide";
43
44	fn shape(&self, dimensions: &[usize]) -> (usize, usize) {
45		let [dividend_limbs, divisor_limbs] = dimensions else {
46			panic!("BigUintDivide requires 2 dimensions");
47		};
48		(*dividend_limbs + *divisor_limbs, *dividend_limbs + *divisor_limbs)
49	}
50
51	fn execute(&self, dimensions: &[usize], inputs: &[Word], outputs: &mut [Word]) {
52		let [n_dividend, n_divisor] = dimensions else {
53			panic!("BigUintDivide requires 2 dimensions");
54		};
55		let n_quotient = *n_dividend;
56		let n_remainder = *n_divisor;
57
58		let dividend_limbs = &inputs[0..*n_dividend];
59		let divisor_limbs = &inputs[*n_dividend..];
60
61		let dividend = num_biguint_from_u64_limbs(dividend_limbs.iter().map(|w| w.as_u64()));
62		let divisor = num_biguint_from_u64_limbs(divisor_limbs.iter().map(|w| w.as_u64()));
63
64		let zero = num_bigint::BigUint::ZERO;
65		let (quotient, remainder) = if divisor != zero {
66			(dividend.clone() / divisor.clone(), dividend % divisor)
67		} else {
68			(zero.clone(), zero)
69		};
70
71		// Fill quotient limbs (first part of output)
72		for (i, limb) in quotient.iter_u64_digits().enumerate() {
73			if i < n_quotient {
74				outputs[i] = Word::from_u64(limb);
75			}
76		}
77		// Zero remaining quotient outputs
78		for i in quotient.iter_u64_digits().len()..n_quotient {
79			outputs[i] = Word::ZERO;
80		}
81
82		// Fill remainder limbs (second part of output)
83		for (i, limb) in remainder.iter_u64_digits().enumerate() {
84			if i < n_remainder {
85				outputs[n_quotient + i] = Word::from_u64(limb);
86			}
87		}
88		// Zero remaining remainder outputs
89		for i in remainder.iter_u64_digits().len()..n_remainder {
90			outputs[n_quotient + i] = Word::ZERO;
91		}
92	}
93}
94
95#[cfg(test)]
96mod tests {
97	use super::*;
98
99	#[test]
100	fn test_biguint_divide_hint() {
101		let builder = CircuitBuilder::new();
102
103		// (2^128-1) % (2^64-5) = 24
104		let d0 = builder.add_constant_64(u64::MAX);
105		let d1 = builder.add_constant_64(u64::MAX);
106
107		let m = builder.add_constant_64(u64::MAX - 4);
108
109		let (q, r) = BigUintDivideHint::call(&builder, &[d0, d1], &[m]);
110
111		// A hint emits no constraint of its own, so pinning alone leaves these uncommitted.
112		// Promoting them to public outputs is what the test needs to read them back.
113		for &wire in q.iter().chain(&r) {
114			builder.mark_inout(wire);
115		}
116
117		let circuit = builder.build();
118		let mut w = circuit.new_witness_filler();
119		circuit.populate_wire_witness(&mut w).unwrap();
120
121		assert_eq!(r.len(), 1);
122		assert_eq!(w[r[0]], Word(24));
123
124		assert_eq!(q.len(), 2);
125		assert_eq!(w[q[0]], Word(5));
126		assert_eq!(w[q[1]], Word(1));
127	}
128
129	#[test]
130	fn test_biguint_divide_hint_div_by_zero() {
131		let builder = CircuitBuilder::new();
132
133		let d0 = builder.add_constant_64(u64::MAX);
134		let d1 = builder.add_constant_64(u64::MAX);
135
136		let m0 = builder.add_constant_64(0);
137		let m1 = builder.add_constant_64(0);
138
139		let (q, r) = BigUintDivideHint::call(&builder, &[d0, d1], &[m0, m1]);
140
141		// A hint emits no constraint of its own, so pinning alone leaves these uncommitted.
142		// Promoting them to public outputs is what the test needs to read them back.
143		for &wire in q.iter().chain(&r) {
144			builder.mark_inout(wire);
145		}
146
147		let circuit = builder.build();
148		let mut w = circuit.new_witness_filler();
149		circuit.populate_wire_witness(&mut w).unwrap();
150
151		assert_eq!(r.len(), 2);
152		assert_eq!(w[r[0]], Word(0));
153		assert_eq!(w[r[1]], Word(0));
154
155		assert_eq!(q.len(), 2);
156		assert_eq!(w[q[0]], Word(0));
157		assert_eq!(w[q[1]], Word(0));
158	}
159}
binius_circuits/bignum/big_uint_divide.rs

binius_circuits/bignum/
big_uint_divide.rs
