malachite-nz 0.9.2

The bignum types Natural and Integer, with efficient algorithms partially derived from GMP and FLINT.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.

use crate::natural::Natural;
use malachite_base::num::arithmetic::traits::{PowerOf2, ShrRound, Square};
use malachite_base::num::basic::traits::{One, Two};
use malachite_base::num::logic::traits::SignificantBits;
use malachite_base::rounding_modes::RoundingMode::*;
use std::cmp::Ordering::*;

pub(crate) fn floor_inverse_binary<F: Fn(&Natural) -> Natural>(
    f: F,
    x: &Natural,
    mut low: Natural,
    mut high: Natural,
) -> Natural {
    loop {
        if high <= low {
            return low;
        }
        let mid = (&low + &high).shr_round(1, Ceiling).0;
        match f(&mid).cmp(x) {
            Equal => return mid,
            Less => low = mid,
            Greater => high = mid - Natural::ONE,
        }
    }
}

pub fn floor_sqrt_binary(x: &Natural) -> Natural {
    if x < &Natural::TWO {
        x.clone()
    } else {
        let p = Natural::power_of_2(x.significant_bits().shr_round(1, Ceiling).0);
        floor_inverse_binary(|x| x.square(), x, &p >> 1, p)
    }
}

pub fn ceiling_sqrt_binary(x: &Natural) -> Natural {
    let floor_sqrt = floor_sqrt_binary(x);
    if &(&floor_sqrt).square() == x {
        floor_sqrt
    } else {
        floor_sqrt + Natural::ONE
    }
}

pub fn checked_sqrt_binary(x: &Natural) -> Option<Natural> {
    let floor_sqrt = floor_sqrt_binary(x);
    if &(&floor_sqrt).square() == x {
        Some(floor_sqrt)
    } else {
        None
    }
}

pub fn sqrt_rem_binary(x: &Natural) -> (Natural, Natural) {
    let floor_sqrt = floor_sqrt_binary(x);
    let rem = x - (&floor_sqrt).square();
    (floor_sqrt, rem)
}