1
$\begingroup$

I was trying to simplify the following sequence, such that I can calculate the $n$th term in $\log n$ time. This can be done, if we can express the $n$th in terms of combinations of Fibonacci like numbers.

$S_{n} = (S_{n-1} * S_{n-2} )^k$ given that $S_{0} = a$, $S_{1} = b$ and $k$ is an fixed integer.

I tried my best but could not find a simple formula. Is it possible to get some simple generating function so that I can convert that to Matrix form for calculating in $S_{n}$ in $\log n$ time.

1 Answers 1

3

Take logarithms, and define $T_n = \log S_n$. Then the recurrence relation $S_n = (S_{n-1} S_{n-2})^k$ becomes $\log S_n = k(\log S_{n-1} + \log S_{n-2})$ $T_n = kT_{n-1} + kT_{n-2}$

Now you can find $T_n$ in time $O(\log n)$, and then get back $S_n$ as $S_n = b^{T_n}$, where $b$ is the base of your logarithms.


Just to elaborate: To find $T_n$ in time $O(\log n)$, we can do the following. Let the matrix $A = \begin{pmatrix}0 & 1 \\ k & k \end{pmatrix}$, and the vector $X_n = \begin{pmatrix}T_n \\ T_{n+1}\end{pmatrix}$. Note that $X_n = AX_{n-1}$, and therefore $X_n = A^n X_0$. Now you can find $A^n$ in time $O(\log n)$ using the usual exponentiation-by-repeated-squaring trick, and you know $X_0 = \begin{pmatrix}T_0 \\ T_1\end{pmatrix}$, so you can calculate $X_n$.

  • 0
    Nice one! I will try that. I guess we can just use 2*2 matrix exponentiation.2012-09-13