Give an algorithm to compute the integer part of
$$(1+ \sqrt{2})^n $$
in number of operations which is polynomial in $\log n$.
Note: I had a mistake earlier by using time, instead of number of operations. Even though we use only polynomial in $\log n$ integer operations, the running time will be $\Omega(n)$, as we are dealing with $\theta(n)$ bit integers.
[Solution]
$$(1+ \sqrt{2})^n $$
in number of operations which is polynomial in $\log n$.
Note: I had a mistake earlier by using time, instead of number of operations. Even though we use only polynomial in $\log n$ integer operations, the running time will be $\Omega(n)$, as we are dealing with $\theta(n)$ bit integers.
[Solution]
No comments:
Post a Comment