rust_algorithms/numbers/

arithmetic.rs

//! Arifmetik algoritmlar: EKUB/EKUK, tez darajaga ko'tarish, modul arifmetikasi, Fibonachchi.

/// Eng katta umumiy bo'luvchi (EKUB / GCD) — Evklid algoritmi.
///
/// **G'oya:** `gcd(a, b) = gcd(b, a mod b)`. Chunki `a` va `b` ning har qanday umumiy
/// bo'luvchisi `a - k·b` ni ham bo'ladi. `b` nolga aylanganda `a` — javob.
///
/// - **Time:** O(log min(a, b)), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::gcd;
///
/// assert_eq!(gcd(48, 18), 6);
/// assert_eq!(gcd(17, 5), 1);   // o'zaro tub
/// assert_eq!(gcd(0, 9), 9);
/// ```
pub fn gcd(a: u64, b: u64) -> u64 {
    let (mut a, mut b) = (a, b);
    while b != 0 {
        let t = a % b;
        a = b;
        b = t;
    }
    a
}

/// Eng kichik umumiy karrali (EKUK / LCM).
///
/// `lcm(a,b) = a / gcd(a,b) * b` — avval bo'lamiz, keyin ko'paytiramiz:
/// bu overflow ehtimolini kamaytiradi.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::lcm;
///
/// assert_eq!(lcm(4, 6), 12);
/// assert_eq!(lcm(0, 5), 0);
/// ```
pub fn lcm(a: u64, b: u64) -> u64 {
    if a == 0 || b == 0 {
        return 0;
    }
    a / gcd(a, b) * b
}

/// Kengaytirilgan Evklid algoritmi: `(g, x, y)` shundayki `a·x + b·y = g = gcd(a, b)`.
///
/// **Nima uchun kerak:** modul bo'yicha teskari element topish, diofant tenglamalar,
/// RSA kabi kriptografik sxemalar.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::extended_gcd;
///
/// let (g, x, y) = extended_gcd(240, 46);
/// assert_eq!(g, 2);
/// assert_eq!(240 * x + 46 * y, g);
/// ```
pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        return (a, 1, 0);
    }
    let (g, x1, y1) = extended_gcd(b, a % b);
    (g, y1, x1 - (a / b) * y1)
}

/// `a` ning `n` -darajasi — tez darajaga ko'tarish (binary exponentiation).
///
/// **G'oya:** `a⁸ = ((a²)²)²`. Darajani ikkilik sanoq sistemasida ko'rib,
/// har qadamda asosni kvadratga ko'taramiz va kerakli bitlarda javobga ko'paytiramiz.
///
/// - **Time:** O(log n) — `a⁶⁴` uchun 64 ta emas, atigi 7 ta ko'paytirish!
/// - Overflow bo'lsa `None` qaytadi.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::fast_pow;
///
/// assert_eq!(fast_pow(2, 10), Some(1024));
/// assert_eq!(fast_pow(3, 0), Some(1));
/// assert_eq!(fast_pow(u64::MAX, 2), None); // overflow
/// ```
pub fn fast_pow(a: u64, n: u32) -> Option<u64> {
    let mut natija: u64 = 1;
    let mut asos = a;
    let mut n = n;
    while n > 0 {
        if n & 1 == 1 {
            natija = natija.checked_mul(asos)?;
        }
        n >>= 1;
        if n > 0 {
            asos = asos.checked_mul(asos)?;
        }
    }
    Some(natija)
}

/// `(a^n) mod m` — modul bo'yicha tez darajaga ko'tarish.
///
/// Kriptografiyaning "ishchi oti": 2048-bitli sonlar bilan ham tez ishlaydi.
/// Overflowdan saqlanish uchun ichkarida `u128` ishlatilgan.
///
/// - **Time:** O(log n).
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::mod_pow;
///
/// assert_eq!(mod_pow(2, 10, 1000), 24);       // 1024 mod 1000
/// assert_eq!(mod_pow(3, 0, 7), 1);
/// assert_eq!(mod_pow(123456789, 987654321, 1_000_000_007), 652541198);
/// ```
pub fn mod_pow(a: u64, n: u64, m: u64) -> u64 {
    if m == 1 {
        return 0;
    }
    let mut natija: u128 = 1;
    let mut asos = (a % m) as u128;
    let m128 = m as u128;
    let mut n = n;
    while n > 0 {
        if n & 1 == 1 {
            natija = natija * asos % m128;
        }
        asos = asos * asos % m128;
        n >>= 1;
    }
    natija as u64
}

/// `a` ning `m` moduli bo'yicha teskarisi: `a · x ≡ 1 (mod m)`.
///
/// `gcd(a, m) != 1` bo'lsa teskari element mavjud emas → `None`.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::mod_inverse;
///
/// assert_eq!(mod_inverse(3, 11), Some(4)); // 3*4 = 12 ≡ 1 (mod 11)
/// assert_eq!(mod_inverse(2, 4), None);     // gcd(2,4) = 2
/// ```
pub fn mod_inverse(a: i64, m: i64) -> Option<i64> {
    let (g, x, _) = extended_gcd(a.rem_euclid(m), m);
    if g != 1 {
        return None;
    }
    Some(x.rem_euclid(m))
}

/// `n!` — faktorial (iterativ, overflowga xavfsiz).
///
/// `u64` da `20!` gacha sig'adi; kattasida `None`.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::factorial;
///
/// assert_eq!(factorial(5), Some(120));
/// assert_eq!(factorial(0), Some(1));
/// assert_eq!(factorial(21), None);
/// ```
pub fn factorial(n: u32) -> Option<u64> {
    (1..=n as u64).try_fold(1u64, |acc, x| acc.checked_mul(x))
}

/// `n` -Fibonachchi soni — iterativ, O(n).
///
/// **Nega rekursiya emas?** Sodda rekursiya bir xil qiymatni qayta-qayta hisoblab
/// O(2ⁿ) ga chiqadi: `fib(50)` uyingizdagi kompyuterda bir necha kun ishlaydi.
/// Bu yerda faqat oxirgi ikkita qiymatni eslab qolamiz.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::fibonacci;
///
/// assert_eq!(fibonacci(0), Some(0));
/// assert_eq!(fibonacci(10), Some(55));
/// assert_eq!(fibonacci(90), Some(2880067194370816120));
/// assert_eq!(fibonacci(93), Some(12200160415121876738)); // u64 dagi oxirgisi
/// assert_eq!(fibonacci(94), None);                       // u64 ga sig'maydi
/// ```
pub fn fibonacci(n: u32) -> Option<u64> {
    if n > 200 {
        return None;
    }
    // Ichkarida u128 — shunda 93-Fibonachchini ham overflowsiz hisoblaymiz.
    let (mut a, mut b) = (0u128, 1u128);
    for _ in 0..n {
        let t = a + b;
        a = b;
        b = t;
    }
    u64::try_from(a).ok()
}

/// `n` -Fibonachchi soni — O(log n) ("fast doubling").
///
/// Formulalar:
/// `F(2k) = F(k)·(2·F(k+1) − F(k))`, `F(2k+1) = F(k)² + F(k+1)²`.
///
/// Natija `u128` da qaytadi — `n = 180` gacha bemalol.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::{fibonacci, fibonacci_fast};
///
/// assert_eq!(fibonacci_fast(10), 55);
/// assert_eq!(fibonacci_fast(90) as u64, fibonacci(90).unwrap());
/// ```
pub fn fibonacci_fast(n: u32) -> u128 {
    fn doubling(n: u32) -> (u128, u128) {
        if n == 0 {
            return (0, 1);
        }
        let (a, b) = doubling(n / 2);
        let c = a * (2 * b - a);
        let d = a * a + b * b;
        if n % 2 == 0 {
            (c, d)
        } else {
            (d, c + d)
        }
    }
    doubling(n).0
}

/// Sonning raqamlari (eng kattasidan kichigiga qarab).
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::digits;
///
/// assert_eq!(digits(4071), vec![4, 0, 7, 1]);
/// assert_eq!(digits(0), vec![0]);
/// ```
pub fn digits(mut n: u64) -> Vec<u8> {
    if n == 0 {
        return vec![0];
    }
    let mut out = Vec::new();
    while n > 0 {
        out.push((n % 10) as u8);
        n /= 10;
    }
    out.reverse();
    out
}

/// Raqamlar yig'indisi.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::digit_sum;
///
/// assert_eq!(digit_sum(12345), 15);
/// ```
pub fn digit_sum(mut n: u64) -> u64 {
    let mut s = 0;
    while n > 0 {
        s += n % 10;
        n /= 10;
    }
    s
}

/// Sonni teskari o'girish: `1234 → 4321`.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::reverse_number;
///
/// assert_eq!(reverse_number(1234), 4321);
/// assert_eq!(reverse_number(1200), 21);
/// ```
pub fn reverse_number(mut n: u64) -> u64 {
    let mut out = 0u64;
    while n > 0 {
        out = out * 10 + n % 10;
        n /= 10;
    }
    out
}

/// Sonni `base` (2..=36) sanoq sistemasiga o'tkazadi.
///
/// # Misol
/// ```
/// use rust_algorithms::numbers::to_base;
///
/// assert_eq!(to_base(255, 2), "11111111");
/// assert_eq!(to_base(255, 16), "ff");
/// assert_eq!(to_base(0, 8), "0");
/// ```
pub fn to_base(mut n: u64, base: u32) -> String {
    assert!((2..=36).contains(&base), "base 2..=36 oralig'ida bo'lsin");
    if n == 0 {
        return "0".to_string();
    }
    const RAQAMLAR: &[u8] = b"0123456789abcdefghijklmnopqrstuvwxyz";
    let mut buf = Vec::new();
    while n > 0 {
        buf.push(RAQAMLAR[(n % base as u64) as usize]);
        n /= base as u64;
    }
    buf.reverse();
    String::from_utf8(buf).unwrap()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn gcd_va_lcm() {
        assert_eq!(gcd(12, 8), 4);
        assert_eq!(gcd(0, 0), 0);
        assert_eq!(gcd(7, 0), 7);
        assert_eq!(lcm(21, 6), 42);
        // gcd(a,b) * lcm(a,b) == a*b
        for a in 1u64..30 {
            for b in 1u64..30 {
                assert_eq!(gcd(a, b) * lcm(a, b), a * b);
            }
        }
    }

    #[test]
    fn extended_gcd_identiteti() {
        for a in 1i64..50 {
            for b in 1i64..50 {
                let (g, x, y) = extended_gcd(a, b);
                assert_eq!(g, gcd(a as u64, b as u64) as i64);
                assert_eq!(a * x + b * y, g);
            }
        }
    }

    #[test]
    fn fast_pow_togri() {
        for a in 1u64..10 {
            for n in 0u32..10 {
                assert_eq!(fast_pow(a, n), Some(a.pow(n)));
            }
        }
    }

    #[test]
    fn mod_pow_togri() {
        let m = 1_000_000_007u64;
        for a in 1u64..20 {
            let mut kutilgan = 1u64;
            for n in 0u64..20 {
                assert_eq!(mod_pow(a, n, m), kutilgan, "a={a}, n={n}");
                kutilgan = kutilgan * a % m;
            }
        }
        assert_eq!(mod_pow(5, 100, 1), 0);
    }

    #[test]
    fn mod_inverse_togri() {
        let m = 13;
        for a in 1..m {
            let inv = mod_inverse(a, m).unwrap();
            assert_eq!(a * inv % m, 1);
        }
        assert_eq!(mod_inverse(6, 9), None);
    }

    #[test]
    fn fibonacci_ikki_usul_mos() {
        for n in 0..=90u32 {
            assert_eq!(fibonacci(n).unwrap() as u128, fibonacci_fast(n));
        }
    }

    #[test]
    fn raqamlar_bilan_ishlash() {
        assert_eq!(digits(1000), vec![1, 0, 0, 0]);
        assert_eq!(digit_sum(0), 0);
        assert_eq!(reverse_number(0), 0);
        assert_eq!(to_base(31, 32), "v");
    }
}