dpp/util/
is_non_zero_fibonacci_number.rs

1fn is_perfect_square(number: u64) -> bool {
2    if number < 2 {
3        return true;
4    }
5    // Integer square root via Newton's method
6    let mut x = number;
7    let mut y = x.div_ceil(2);
8    while y < x {
9        x = y;
10        y = (x + number / x) / 2;
11    }
12    x * x == number
13}
14
15pub fn is_non_zero_fibonacci_number(number: u64) -> bool {
16    if number == 0 {
17        return false;
18    }
19
20    let square_check_up = 5u64
21        .checked_mul(number)
22        .and_then(|n| n.checked_mul(number))
23        .and_then(|n| n.checked_add(4));
24
25    let square_check_down = 5u64
26        .checked_mul(number)
27        .and_then(|n| n.checked_mul(number))
28        .and_then(|n| n.checked_sub(4));
29
30    match (square_check_up, square_check_down) {
31        (Some(n1), Some(n2)) => is_perfect_square(n1) || is_perfect_square(n2),
32        (Some(n1), None) => is_perfect_square(n1),
33        (None, Some(n2)) => is_perfect_square(n2),
34        (None, None) => false,
35    }
36}
37
38#[cfg(test)]
39mod tests {
40    use super::*;
41
42    /// AUDIT M6: Floating-point imprecision in is_perfect_square for large values.
43    ///
44    /// `is_perfect_square` casts u64 to f64 and checks `sqrt().fract() == 0.0`.
45    /// f64 has only 52 bits of mantissa, so for values above 2^52, precision is lost.
46    /// This means `is_perfect_square` can return incorrect results for large numbers.
47    ///
48    /// Currently not exploitable for `core_fee_per_byte` (u32), but the function
49    /// accepts u64 and is technically unsound for large inputs.
50    ///
51    /// Location: rs-dpp/src/util/is_non_zero_fibonacci_number.rs:1-3
52    #[test]
53    fn test_is_perfect_square_large_values() {
54        // For small values, is_perfect_square works correctly
55        assert!(is_perfect_square(0));
56        assert!(is_perfect_square(1));
57        assert!(is_perfect_square(4));
58        assert!(is_perfect_square(9));
59        assert!(is_perfect_square(16));
60        assert!(!is_perfect_square(2));
61        assert!(!is_perfect_square(3));
62
63        // Find a value where f64 imprecision causes is_perfect_square to give wrong answer.
64        // The number (2^26 + 1)^2 = 2^52 + 2^27 + 1 = 4503599761588225
65        // When cast to f64, this may lose the +1 and appear as (2^26 + 1)^2 exactly,
66        // or nearby non-squares may appear as perfect squares.
67        //
68        // Strategy: find a non-square near a large perfect square where f64 rounds
69        // the sqrt to an exact integer.
70        let base: u64 = (1u64 << 26) + 1; // 67108865
71        let perfect_square = base * base; // 4503599761588225
72
73        // Verify perfect_square is correctly identified
74        assert!(
75            is_perfect_square(perfect_square),
76            "AUDIT M6: {} should be a perfect square ({}^2)",
77            perfect_square,
78            base
79        );
80
81        // Check non-squares adjacent to large perfect squares.
82        // Due to f64 imprecision, some of these may incorrectly return true.
83        let false_positives: Vec<u64> = (1..=10u64)
84            .filter(|&offset| {
85                let candidate = perfect_square + offset;
86                // This should NOT be a perfect square, but f64 may say it is
87                is_perfect_square(candidate)
88            })
89            .collect();
90
91        // If is_perfect_square is sound, there should be no false positives.
92        // With f64 imprecision, some non-squares will be falsely identified as perfect squares.
93        assert!(
94            false_positives.is_empty(),
95            "AUDIT M6: is_perfect_square returned true for non-square values near {}^2: \
96            offsets {:?}. This is caused by f64 imprecision — (number as f64).sqrt() \
97            rounds to an exact integer for these non-square values. \
98            Fix: use integer square root instead of floating-point.",
99            base,
100            false_positives
101        );
102    }
103
104    /// AUDIT M6 (supplementary): Verify is_non_zero_fibonacci_number works for known values
105    #[test]
106    fn test_known_non_zero_fibonacci_numbers() {
107        // Known non-zero Fibonacci numbers
108        let fibs = [
109            1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
110        ];
111        for &n in &fibs {
112            assert!(
113                is_non_zero_fibonacci_number(n),
114                "{} should be recognized as a Fibonacci number",
115                n
116            );
117        }
118
119        // Known non-Fibonacci numbers
120        let non_fibs = [0, 4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 22, 100];
121        for &n in &non_fibs {
122            assert!(
123                !is_non_zero_fibonacci_number(n),
124                "{} should NOT be recognized as a Fibonacci number",
125                n
126            );
127        }
128    }
129}
dpp/util/is_non_zero_fibonacci_number.rs

dpp/util/
is_non_zero_fibonacci_number.rs
