Num Algorithms

// Showcase — a tiny integer-math toolkit.
//
// Integration example combining several control-flow and operator features:
//   recursion · while loops · modulo (%) · compound assignment (+=)
//   · saturating and checked overflow methods · Option + match deconstruction
//   · tuples · loop-as-value · nested if/else · early return
//   · nesting block comments.
//
// Five classic routines are computed and composed into a single exit code.

// Integer square root via linear scan.
func isqrt(n: i32) -> i32 {
    mut r: i32 = 0
    while (r + 1) * (r + 1) <= n {
        r += 1
    }
    return r
}

/* Shelved: Newton's method converges in far fewer steps, but it needs a
   division-by-zero guard the linear scan above does not, so it stays parked
   here until the guard is worth writing. The whole block is inert — including
   the ordinary comment inside it, which is why the outer comment has to nest.

func isqrt_newton(n: i32) -> i32 {
    if n == 0 { return 0 }
    mut r: i32 = n
    loop {
        /* Averaging r and n/r halves the error each round. */
        val next = (r + n / r) / 2
        if next >= r { break }
        r = next
    }
    return r
}
*/

// Greatest common divisor — Euclid's algorithm, recursive.
func gcd(a: i32, b: i32) -> i32 {
    if b == 0 { return a }
    return gcd(b, a % b)
}

// Primality test by trial division.
func is_prime(n: i32) -> bool {
    if n < 2 { return false }
    mut d: i32 = 2
    while d * d <= n {
        if n % d == 0 { return false }
        d += 1
    }
    return true
}

// Integer power using saturating multiply, so it never traps on overflow.
func ipow(base: i32, exp: i32) -> i32 {
    mut acc: i32 = 1
    mut i: i32 = 0
    while i < exp {
        acc = acc.saturating_mul(base)
        i += 1
    }
    return acc
}

// The same power, but reporting overflow rather than clamping it away.
// `checked_mul` yields `Option::None` at the first step whose product does not fit,
// and the loop stops there with the absent answer.
func pow_checked(base: i32, exp: i32) -> Option<i32> {
    mut acc: i32 = 1
    mut i: i32 = 0
    val outcome = loop {
        if i == exp {
            break Option::Some(acc)
        }
        // One match, both halves: the product and whether it fit.
        val step: (i32, bool) = match acc.checked_mul(base) {
            Option::Some(v) => (v, true),
            Option::None => (acc, false)
        }
        if step.1 == false {
            break Option::None
        }
        acc = step.0
        i += 1
    }
    return outcome
}

func main() -> i32 {
    val s = isqrt(144)      // 12
    val g = gcd(48, 36)     // 12
    val p = ipow(2, 10)     // 1024

    // 2^10 fits in an i32; 1000^5 = 10^15 does not, and says so.
    val fits = match pow_checked(2, 10) {
        Option::Some(v) => v,          // 1024
        Option::None => 0
    }
    val refused = match pow_checked(1000, 5) {
        Option::Some(_) => 0,
        Option::None => 1              // 1
    }

    // Count primes in 0..=20: {2,3,5,7,11,13,17,19} -> 8.
    mut primes: i32 = 0
    mut k: i32 = 0
    while k <= 20 {
        if is_prime(k) { primes += 1 }
        k += 1
    }

    println("isqrt(144)             = {s}")
    println("gcd(48, 36)            = {g}")
    println("ipow(2, 10)            = {p}")
    println("pow_checked(2, 10) Some= {fits}")
    println("pow_checked(1000, 5) None -> {refused}")
    println("primes in 0..=20       = {primes}")

    // Compose, gated on both power results agreeing.
    if p == 1024 {
        if fits == 1024 {
            val total = s + g + primes + refused   // 12 + 12 + 8 + 1 = 33
            println("total                  = {total}")
            return total
        }
    }
    println("a power result disagreed")
    return 1
}