Number Algorithms

Classic number theory: GCD, primality test, collatz sequence.

Example 019 of the basic Soma programs: a small, commented program that teaches one thing. Every output below was printed by soma 3.2.4 when this page was built.

How it is built

The cell NumberAlgorithms has no face and no memory. Handlers: run (line 15), gcd (line 34), is_prime (line 46) and collatz (line 61).

Generated from soma describe on this file.

The source

019_number_algorithms.cell

// ============================================================================
// 019 — Number Algorithms
// ============================================================================
// Classic number theory: GCD, primality test, collatz sequence.
//
// Run:   soma run 019_number_algorithms.cell run
// Expect:
//   GCD of 48 and 18: 6
//   Is 17 prime? yes
//   Is 15 prime? no
//   Collatz(6): 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (8 steps)

cell NumberAlgorithms {

    on run() {
        // GCD using Euclidean algorithm
        let g = gcd(48, 18)
        print("GCD of 48 and 18: {g}")

        // Primality testing
        let p1 = is_prime(17)
        print("Is 17 prime? {p1}")
        let p2 = is_prime(15)
        print("Is 15 prime? {p2}")

        // Collatz conjecture: if even n/2, if odd 3n+1
        let steps = collatz(6)
        print("{steps}")

        return "done"
    }

    // Euclidean GCD algorithm
    on gcd(a: Int, b: Int) {
        let x = a
        let y = b
        while y != 0 {
            let temp = y
            y = x % y
            x = temp
        }
        return x
    }

    // Trial division primality test
    on is_prime(n: Int) {
        if n < 2 {
            return "no"
        }
        let i = 2
        while i * i <= n {
            if n % i == 0 {
                return "no"
            }
            i = i + 1
        }
        return "yes"
    }

    // Collatz sequence — returns description string
    on collatz(n: Int) {
        let current = n
        let result = to_string(n)
        let steps = 0
        while current != 1 {
            if current % 2 == 0 {
                current = current / 2
            } else {
                current = 3 * current + 1
            }
            result += " -> "
            result += to_string(current)
            steps = steps + 1
        }
        result = "Collatz({n}): " + result
        result += " ({steps} steps)"
        return result
    }
}

What the toolchain says

$ soma check 019_number_algorithms.cell
warning: `result` grows by concatenation inside a loop — each step copies the whole value, so the loop is quadratic (8 MB took 32 s, a list + join() 30 ms): push the pieces to a List and `join(parts, "")` once
  --> 019_number_algorithms.cell:71:13
   |
71 |             result += " -> "
   |             ^
✓ 1 warning(s), no errors.

$ soma run 019_number_algorithms.cell run
GCD of 48 and 18: 6
Is 17 prime? yes
Is 15 prime? no
Collatz(6): 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (8 steps)
done