The algorithm puzzle was to find the integer part of $(1 + \sqrt{2})^n$ using only integer arithmetic, in number of operations which is polynomial in $\log n$
[Note: the puzzle post mistakenly said time, instead of number of operations. Fixed now]
Solution
By the binomial theorem, notice that
$$ (1 + \sqrt{2})^n = a_n + b_n \sqrt{2}$$
where $a_n$ and $b_n$ are both integers.
Now
$$(a_n + b_n \sqrt{2})(1 + \sqrt{2}) = (a_n + 2b_n) + (a_n +b_n)\sqrt{2}$$
Thus we get the recurrence relations:
$$ a_{n+1} = a_n + 2b_n $$
$$ b_{n+1} = a_n + b_n $$
This can be written in matrix form as
$$\begin{bmatrix}1&2\\1&1\end{bmatrix}\begin{bmatrix} a_n\\b_n \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$
i.e.
$$A \begin{bmatrix}a_n\\b_n \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$
Giving us
$$ A^n \begin{bmatrix}a_1\\b_1 \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$
$A^n$ can be computed in $O(\log n)$ integer operations.
Once we have $(a_n, b_n)$ we can compute the integer part of $a_n + b_n \sqrt{2}$ by computing the integer part of $b_n \sqrt{2}$ using binary search for integer $x$ such that $x^2 \lt 2b_n^2 \lt (x+1)^2$ (or other algorithms) and adding that to $a_n$.
We could also solve this problem by a more straight-forward divide and conquer + memoization algorithm, like we did for Fibonacci earlier, by writing $(a_{2n}, b_{2n})$ in terms of $(a_n, b_n)$ etc.
[Note: the puzzle post mistakenly said time, instead of number of operations. Fixed now]
Solution
By the binomial theorem, notice that
$$ (1 + \sqrt{2})^n = a_n + b_n \sqrt{2}$$
where $a_n$ and $b_n$ are both integers.
Now
$$(a_n + b_n \sqrt{2})(1 + \sqrt{2}) = (a_n + 2b_n) + (a_n +b_n)\sqrt{2}$$
Thus we get the recurrence relations:
$$ a_{n+1} = a_n + 2b_n $$
$$ b_{n+1} = a_n + b_n $$
This can be written in matrix form as
$$\begin{bmatrix}1&2\\1&1\end{bmatrix}\begin{bmatrix} a_n\\b_n \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$
i.e.
$$A \begin{bmatrix}a_n\\b_n \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$
Giving us
$$ A^n \begin{bmatrix}a_1\\b_1 \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$
$A^n$ can be computed in $O(\log n)$ integer operations.
Once we have $(a_n, b_n)$ we can compute the integer part of $a_n + b_n \sqrt{2}$ by computing the integer part of $b_n \sqrt{2}$ using binary search for integer $x$ such that $x^2 \lt 2b_n^2 \lt (x+1)^2$ (or other algorithms) and adding that to $a_n$.
We could also solve this problem by a more straight-forward divide and conquer + memoization algorithm, like we did for Fibonacci earlier, by writing $(a_{2n}, b_{2n})$ in terms of $(a_n, b_n)$ etc.
No comments:
Post a Comment