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

problemreductions/models/algebraic/
quadratic_diophantine_equations.rs
