problemreductions/models/algebraic/
quadratic_diophantine_equations.rs

1//! Quadratic Diophantine Equations problem implementation.
2//!
3//! Given positive integers `a`, `b`, and `c`, determine whether there exist
4//! positive integers `x`, `y` such that `a x^2 + b y = c`.
5//!
6//! The witness integer `x` is encoded as a little-endian binary vector so the
7//! model can represent large reductions without fixed-width overflow.
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry};
10use crate::traits::Problem;
11use crate::types::Or;
12use num_bigint::{BigUint, ToBigUint};
13use num_traits::{One, Zero};
14use serde::de::Error as _;
15use serde::{Deserialize, Deserializer, Serialize};
16
17inventory::submit! {
18    ProblemSchemaEntry {
19        name: "QuadraticDiophantineEquations",
20        display_name: "Quadratic Diophantine Equations",
21        aliases: &["QDE"],
22        dimensions: &[],
23        category: crate::registry::ProblemCategory::Algebraic,
24        module_path: module_path!(),
25        description: "Decide whether ax^2 + by = c has a solution in positive integers x, y",
26        fields: &[
27            FieldInfo { name: "a", type_name: "BigUint", description: "Coefficient of x^2" },
28            FieldInfo { name: "b", type_name: "BigUint", description: "Coefficient of y" },
29            FieldInfo { name: "c", type_name: "BigUint", description: "Right-hand side constant" },
30        ],
31    }
32}
33
34/// Quadratic Diophantine Equations problem.
35///
36/// Given positive integers `a`, `b`, and `c`, determine whether there exist
37/// positive integers `x`, `y` such that `a x^2 + b y = c`.
38///
39/// The configuration encodes `x` in little-endian binary:
40/// `config[i] in {0,1}` is the coefficient of `2^i`.
41#[derive(Debug, Clone, Serialize)]
42pub struct QuadraticDiophantineEquations {
43    /// Coefficient of x^2.
44    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
45    a: BigUint,
46    /// Coefficient of y.
47    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
48    b: BigUint,
49    /// Right-hand side constant.
50    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
51    c: BigUint,
52}
53
54fn bit_length(value: &BigUint) -> usize {
55    if value.is_zero() {
56        0
57    } else {
58        let bytes = value.to_bytes_be();
59        let msb = *bytes.first().expect("nonzero BigUint has bytes");
60        8 * (bytes.len() - 1) + (8 - msb.leading_zeros() as usize)
61    }
62}
63
64impl QuadraticDiophantineEquations {
65    fn validate_inputs(
66        a: &BigUint,
67        b: &BigUint,
68        c: &BigUint,
69    ) -> Result<(), crate::registry::ConstructionError> {
70        if a.is_zero() {
71            return Err("Coefficient a must be positive".to_string().into());
72        }
73        if b.is_zero() {
74            return Err("Coefficient b must be positive".to_string().into());
75        }
76        if c.is_zero() {
77            return Err("Right-hand side c must be positive".to_string().into());
78        }
79        Ok(())
80    }
81
82    fn isqrt(n: &BigUint) -> BigUint {
83        if n.is_zero() {
84            return BigUint::zero();
85        }
86
87        let mut low = BigUint::zero();
88        let mut high = BigUint::one() << bit_length(n).div_ceil(2);
89
90        while low < high {
91            let mid = (&low + &high + BigUint::one()) >> 1usize;
92            if &mid * &mid <= *n {
93                low = mid;
94            } else {
95                high = mid - BigUint::one();
96            }
97        }
98
99        low
100    }
101
102    /// Create a new QuadraticDiophantineEquations instance, returning an error
103    /// instead of panicking when inputs are invalid.
104    pub fn try_new<A, B, C>(a: A, b: B, c: C) -> Result<Self, crate::registry::ConstructionError>
105    where
106        A: ToBigUint,
107        B: ToBigUint,
108        C: ToBigUint,
109    {
110        let a = a
111            .to_biguint()
112            .ok_or_else(|| "Coefficient a must be nonnegative".to_string())?;
113        let b = b
114            .to_biguint()
115            .ok_or_else(|| "Coefficient b must be nonnegative".to_string())?;
116        let c = c
117            .to_biguint()
118            .ok_or_else(|| "Right-hand side c must be nonnegative".to_string())?;
119        Self::validate_inputs(&a, &b, &c)?;
120        Ok(Self { a, b, c })
121    }
122
123    /// Create a new QuadraticDiophantineEquations instance.
124    ///
125    /// # Panics
126    ///
127    /// Panics if any of `a`, `b`, `c` is zero.
128    pub fn new<A, B, C>(a: A, b: B, c: C) -> Self
129    where
130        A: ToBigUint,
131        B: ToBigUint,
132        C: ToBigUint,
133    {
134        Self::try_new(a, b, c).unwrap_or_else(|msg| panic!("{msg}"))
135    }
136
137    /// Get the coefficient a (coefficient of x^2).
138    pub fn a(&self) -> &BigUint {
139        &self.a
140    }
141
142    /// Get the coefficient b (coefficient of y).
143    pub fn b(&self) -> &BigUint {
144        &self.b
145    }
146
147    /// Get the right-hand side constant c.
148    pub fn c(&self) -> &BigUint {
149        &self.c
150    }
151
152    /// Number of bits needed to encode the coefficient a.
153    pub fn bit_length_a(&self) -> usize {
154        bit_length(&self.a)
155    }
156
157    /// Number of bits needed to encode the coefficient b.
158    pub fn bit_length_b(&self) -> usize {
159        bit_length(&self.b)
160    }
161
162    /// Number of bits needed to encode the constant c.
163    pub fn bit_length_c(&self) -> usize {
164        bit_length(&self.c)
165    }
166
167    fn max_x(&self) -> BigUint {
168        if self.c < self.a {
169            return BigUint::zero();
170        }
171        Self::isqrt(&(&self.c / &self.a))
172    }
173
174    fn witness_bit_length(&self) -> usize {
175        let max_x = self.max_x();
176        if max_x.is_zero() {
177            0
178        } else {
179            bit_length(&max_x)
180        }
181    }
182
183    /// Check whether a given x yields a valid positive integer y.
184    ///
185    /// Returns `Some(y)` if `y` is a positive integer, `None` otherwise.
186    pub fn check_x(&self, x: &BigUint) -> Option<BigUint> {
187        if x.is_zero() {
188            return None;
189        }
190
191        let ax2 = &self.a * x * x;
192        if ax2 >= self.c {
193            return None;
194        }
195
196        let remainder = &self.c - ax2;
197        if (&remainder % &self.b) != BigUint::zero() {
198            return None;
199        }
200
201        let y = remainder / &self.b;
202        if y.is_zero() {
203            return None;
204        }
205
206        Some(y)
207    }
208}
209
210#[derive(Deserialize)]
211struct QuadraticDiophantineEquationsData {
212    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
213    a: BigUint,
214    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
215    b: BigUint,
216    #[serde(with = "crate::models::misc::biguint_serde::decimal_biguint")]
217    c: BigUint,
218}
219
220impl<'de> Deserialize<'de> for QuadraticDiophantineEquations {
221    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
222    where
223        D: Deserializer<'de>,
224    {
225        let data = QuadraticDiophantineEquationsData::deserialize(deserializer)?;
226        Self::try_new(data.a, data.b, data.c).map_err(D::Error::custom)
227    }
228}
229
230impl Problem for QuadraticDiophantineEquations {
231    const NAME: &'static str = "QuadraticDiophantineEquations";
232    type Solution = BigUint;
233    type Value = Or;
234
235    crate::problem_parameters![
236        ("bit_length_a", bit_length_a),
237        ("bit_length_b", bit_length_b),
238        ("bit_length_c", bit_length_c),
239    ];
240
241    fn variant() -> Vec<(&'static str, &'static str)> {
242        crate::variant_params![]
243    }
244
245    fn evaluate(&self, x: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
246        Ok({
247            if x.is_zero() || x > &self.max_x() {
248                return Ok(Or(false));
249            }
250
251            Or(self.check_x(x).is_some())
252        })
253    }
254}
255
256impl crate::solvers::BruteForceProblem for QuadraticDiophantineEquations {
257    fn dimensions(&self) -> Vec<usize> {
258        let num_bits = self.witness_bit_length();
259        if num_bits == 0 {
260            Vec::new()
261        } else {
262            vec![2; num_bits]
263        }
264    }
265}
266
267crate::declare_variants! {
268    default QuadraticDiophantineEquations => "2^bit_length_c",
269}
270
271crate::register_brute_force! {
272    QuadraticDiophantineEquations decode |_: &QuadraticDiophantineEquations, indices: Vec<usize>| indices.into_iter().enumerate().fold(BigUint::zero(), |value, (bit, set)| if set == 0 { value } else { value + (BigUint::one() << bit) }),
273}
274
275#[cfg(feature = "example-db")]
276pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
277    let instance = QuadraticDiophantineEquations::new(3u32, 5u32, 53u32);
278    let optimal_config = BigUint::from(1u32);
279
280    vec![crate::example_db::specs::ModelExampleSpec {
281        id: "quadratic_diophantine_equations",
282        instance: Box::new(instance),
283        optimal_config: serde_json::to_value(optimal_config)
284            .expect("solution serialization must succeed"),
285        optimal_value: serde_json::json!(true),
286    }]
287}
288
289#[cfg(test)]
290#[path = "../../unit_tests/models/algebraic/quadratic_diophantine_equations.rs"]
291mod tests;
problemreductions/models/algebraic/quadratic_diophantine_equations.rs

problemreductions/models/algebraic/
quadratic_diophantine_equations.rs
