Irrationals
Digression
Catalan numbers:
- Set P of balanced parentheses strings are recursively defined as
- $λ ∈ P$ (λ is empty string)
- If $α, β ∈ P$, then $(α)β ∈ P$
- Every nonempty balanced paren string can be obtained via Rule 2 from a unique α, β pair
Enumeration
- $C_n$: number of balanced parentheses strings with exactly n pairs of parentheses $C_0 = 1$ empty string
- $C_{n+1}$? Every string with n+1 pairs of parentheses can be obtained in a unique way via rule 2.
- One paren pair comes explicitly from the rule.
- $k$ pairs from $α$, $n − k$ pairs from $β$
- $C_{n+1} = \sum_{n=0}^n C_k \dot C_{n-k} \qquad n \ge 0$
- $C_0=1 \quad C_1=C_0^2 = 1 \quad C_2=C_0C_1 + C_1C_0 = 2 \quad C_3 = \cdots = 5$
Newton’s Method
- Find root of $f(x) = 0$ through successive approximation e.g., $f(x) = x^2 − a$
- Tangent at $(x_i, f(x_i))$ is line $y = f(x_i)+ f’(x_i)·(x− x_i)$ where $f’(x_i)$ is the derivative. $x_{i+1}$ = intercept on x-axis
$$x_{i+1} = x_i - \frac{f(x_i)}{f’(x_i)}$$
High precision multiply
Multiplying two n-digit numbers (radix r = 2, 10) $0 ≤ x, y < r^n$
$$x = x_1 · r^{n/2} + x_0 \quad x_1 = high \; half$$ $$y = y_1 · r^{n/2} + y_0 \quad x_0 = low \; half$$ $$0 \le x_0, x_1 < r^{n/2}$$ $$0 \le y_0, y_1 < r^{n/2}$$ $$z = x·y = x_1y_1·r^{n} + (x_0·y_1 + x_1·y_0)r^{n/2} + x_0·y_0$$
- 4 multiplications of half-sized ⇒ quadratic algorithm $θ(n^2)$ time
Karatsuba’s Method
Let
$$z_0 = x_0·y_0$$ $$z_2 = x_1·y_1$$ $$z_1 = (x_0+x_1)·(y_0+y_1) - z_0 - z_2 = x_0y_1+x_1y_0$$ $$z = z_2·r^n +z_1·r^{n/2} +z_0$$
There are three multiplies in the above calculations.
$$T(n) = time \; to \; multiply \; two \; n-digit \; numbers
= 3T(n/2) + θ(n)
= θ(n^{log_23}) = θ(n^{1.5849625···})$$
A tutorial about Karatsuba’s method can be found here