Algorithms for computing $(I + \frac{Q}{n})^n$

Question

I need to compute the matrix $(I + \frac{Q}{n})^n$ where $n = 2^k$, $k$ is integer. I want to know if there is any practical and effective algorithms.

Answer 1

Let $Q\in M_m$. If you want a result for only one large $n$, then use the Hyperplane's method (the complexity is $k$ matrix mult, that is, $km^3$ mult-add. on the entries).

If you want results for $p$ values of large $n$, then diagonalize $Q$ (if possible) $Q=Pdiag(\lambda_i)P^{-1}$ (complexity $\approx 40m^3$). Then, for each $n$, $(I+Q/n)^n=Pdiag((1+\lambda_i/n)^n)P^{-1}$; that is, a total complexity $(40+p)m^3$.

Answer 2

$$ x^{16} = (x^8)^2 = ((x^4)^2)^2 = (((x^2)^2)^2)^2 $$