binius_frontend/compiler/hints/
big_uint_divide.rs

1// Copyright 2025 Irreducible Inc.
2//! BigUint division hint implementation
3
4use binius_core::Word;
5
6use super::Hint;
7use crate::util::num_biguint_from_u64_limbs;
8
9pub struct BigUintDivideHint;
10
11impl BigUintDivideHint {
12	pub fn new() -> Self {
13		Self
14	}
15}
16
17impl Default for BigUintDivideHint {
18	fn default() -> Self {
19		Self::new()
20	}
21}
22
23impl Hint for BigUintDivideHint {
24	const NAME: &'static str = "binius.biguint_divide";
25
26	fn shape(&self, dimensions: &[usize]) -> (usize, usize) {
27		let [dividend_limbs, divisor_limbs] = dimensions else {
28			panic!("BigUintDivide requires 2 dimensions");
29		};
30		(*dividend_limbs + *divisor_limbs, *dividend_limbs + *divisor_limbs)
31	}
32
33	fn execute(&self, dimensions: &[usize], inputs: &[Word], outputs: &mut [Word]) {
34		let [n_dividend, n_divisor] = dimensions else {
35			panic!("BigUintDivide requires 2 dimensions");
36		};
37		let n_quotient = *n_dividend;
38		let n_remainder = *n_divisor;
39
40		let dividend_limbs = &inputs[0..*n_dividend];
41		let divisor_limbs = &inputs[*n_dividend..];
42
43		let dividend = num_biguint_from_u64_limbs(dividend_limbs.iter().map(|w| w.as_u64()));
44		let divisor = num_biguint_from_u64_limbs(divisor_limbs.iter().map(|w| w.as_u64()));
45
46		let zero = num_bigint::BigUint::ZERO;
47		let (quotient, remainder) = if divisor != zero {
48			(dividend.clone() / divisor.clone(), dividend % divisor)
49		} else {
50			(zero.clone(), zero.clone())
51		};
52
53		// Fill quotient limbs (first part of output)
54		for (i, limb) in quotient.iter_u64_digits().enumerate() {
55			if i < n_quotient {
56				outputs[i] = Word::from_u64(limb);
57			}
58		}
59		// Zero remaining quotient outputs
60		for i in quotient.iter_u64_digits().len()..n_quotient {
61			outputs[i] = Word::ZERO;
62		}
63
64		// Fill remainder limbs (second part of output)
65		for (i, limb) in remainder.iter_u64_digits().enumerate() {
66			if i < n_remainder {
67				outputs[n_quotient + i] = Word::from_u64(limb);
68			}
69		}
70		// Zero remaining remainder outputs
71		for i in remainder.iter_u64_digits().len()..n_remainder {
72			outputs[n_quotient + i] = Word::ZERO;
73		}
74	}
75}
binius_frontend/compiler/hints/big_uint_divide.rs

binius_frontend/compiler/hints/
big_uint_divide.rs
