# Math & Matrix — Part 1: The Pattern

A handful of math tools and matrix manipulations show up again and again: **gcd** (Euclid), **fast exponentiation** (O(log n) by squaring), **modular arithmetic** for huge answers ("return the result mod 10⁹ + 7"), the **sieve of Eratosthenes** for primes, cycle detection on number sequences, and **in-place matrix transformations** (rotate, spiral order, marking rows/columns). None of these need deep math, just the right identity and careful indexing.

![Rotating a matrix 90° clockwise = transpose + reverse each row](diagrams/01-rotate.svg)

## 1. Templates

```typescript
function gcd(a: number, b: number): number {
  while (b) [a, b] = [b, a % b];
  return a;
}

function fastPow(x: number, n: number, mod: number): number {
  let result = 1n, base = BigInt(x) % BigInt(mod), e = BigInt(n);
  const m = BigInt(mod);
  while (e > 0n) {                   // BigInt avoids precision loss above 2^53
    if (e & 1n) result = (result * base) % m;
    base = (base * base) % m;
    e >>= 1n;
  }
  return Number(result);
}

function sieve(n: number): number[] {
  const isPrime = new Array(n).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let p = 2; p * p < n; p++) if (isPrime[p]) for (let q = p * p; q < n; q += p) isPrime[q] = false;
  return isPrime.flatMap((v, i) => (v && i < n ? [i] : []));
}

function mathDemo(a: number, b: number, x: number, k: number, m: number, n: number): any[] {
  return [gcd(a, b), fastPow(x, k, m), sieve(n)];
}
```

```python
def gcd(a, b):
    while b:
        a, b = b, a % b              # Euclid: gcd(a, b) = gcd(b, a mod b)
    return a

def fast_pow(x, n, mod):             # x^n mod m in O(log n)
    result = 1
    x %= mod
    while n:
        if n & 1:
            result = result * x % mod
        x = x * x % mod
        n >>= 1
    return result

def sieve(n):                        # primes < n in O(n log log n)
    is_prime = [True] * n
    is_prime[0:2] = [False, False][:n]
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for q in range(p * p, n, p):
                is_prime[q] = False
    return [i for i in range(n) if is_prime[i]]

def math_demo(a, b, x, k, m, n):
    return [gcd(a, b), fast_pow(x, k, m), sieve(n)]
```

## 2. Modular Arithmetic

- `(a + b) % m = ((a % m) + (b % m)) % m`, and the same for multiplication: reduce after every step to keep numbers small.
- Division needs a **modular inverse**: for a prime m, `a⁻¹ = a^(m−2) mod m` (Fermat), computed with fast power.
- In JavaScript, products above 2⁵³ lose precision: use **BigInt** for modular multiplication with large moduli. In C#, use `long` (and `checked` blocks if you want overflow errors).

## 3. Matrix Patterns

| Task | Idea |
|---|---|
| rotate 90° clockwise in place | **transpose** (swap `m[i][j]` and `m[j][i]`), then **reverse each row** |
| rotate counter-clockwise | transpose, then reverse each column (or reverse rows first) |
| spiral order | four boundaries `top, bottom, left, right`; walk one edge, shrink that boundary |
| set matrix zeroes in O(1) space | use the **first row and column as markers** (plus one flag for the first column) |
| diagonal traversal | cells with the same `r + c` (anti-diagonal) or `r − c` (diagonal) |
| 2D binary search (sorted rows & columns) | start at the top-right; move left or down: O(m + n) |

## Under the Hood: Why Fast Power Is O(log n)

Write n in binary: `x¹³ = x⁸ · x⁴ · x¹` (13 = 1101₂). Squaring x repeatedly gives x, x², x⁴, x⁸ … (one squaring per bit), and you multiply in the powers whose bit is set. So you do about 2·log₂ n multiplications instead of n. The same trick computes Fibonacci numbers in O(log n) with **matrix exponentiation**, and it underpins RSA and Diffie–Hellman (modular exponentiation with 2048-bit numbers).

## Common Pitfalls

1. **Overflow** before taking the modulus (`a * b` in 32-bit C#, or above 2⁵³ in JS).
2. **Negative modulo** in JS/C# (`-7 % 3 == -1`): normalize with `((x % m) + m) % m`.
3. **Negative exponents** in `pow(x, n)`: use `1 / x^(−n)`, and beware `−(−2³¹)` overflowing in C#.
4. **Spiral off-by-one:** after walking the top row, `top += 1` before the right column, and check bounds before walking back.
5. **Sieve upper bound:** the outer loop only needs `p * p < n`.

## Quick Reference

```text
gcd: while b: a, b = b, a % b · lcm = a / gcd * b
fast pow: while n: if n&1: r *= x; x *= x; n >>= 1   (mod after each step)
sieve: for p*p < n: if prime: mark p*p, p*p+p, …
rotate CW: transpose + reverse rows · spiral: shrink 4 boundaries
```