Provide an efficient algorithm for computing $(a + b \sqrt{3})^n$?

Question

Provide an efficient algorithm that takes three integers as input and returns two integers that satisfy the condition. Only simple arithmetic operations are allowed (square root operation is not permitted).

Input: $(a, b, n)$ where $a, b, n$ are positive integers greater than $0$.

Output: $(c, d)$ where $c$ and $d$ are integers that satisfy the following condition: $$ (a + b \sqrt{3})^n = c + d \sqrt{3}$$

Thought it was an interesting problem, haven't come up with a solution yet.

Initially wanted to post the question in StackOverflow but I thought it was more math heavy.

Answer 1

This is similar to having multiplication in complex numbers $$(x+yi)(u+vi)=(xu-yv)+(xv+yu)i$$ Just instead of imaginary $i$ you have $\sqrt{3}$. So $$(x+y\sqrt{3})(u+v\sqrt{3})=(xu+3yv)+(xv+yu)\sqrt{3}$$ Now basically abstracting this idea to pairs of integers, you have $$(x,y)\cdot(u,v)=(xu+3yv,xv+yu)$$ Using this "$\cdot$" $n$ times correctly (actually $n-1$ times), you can calculate $n$-th power of a number. Notice that there are only basic arithmetic operations involved.

Efficience

Since you wanted also efficient algorithm, you can speed this up by using fast exponentiation. Basic idea is that instead of calculating $x$,$x^2$,$x^3$,etc, you just calculate \begin{align} x^2 &= x \cdot x \\ x^4 &= x^2 \cdot x^2 \\ x^8 &= x^4 \cdot x^4 \\ &\vdots \\ \end{align} and then combine the results correctly. This results on average in $\log_2{n}$ multiplication steps as compared to $n$ steps when using naive approach. There are other tricks to speed exponentiation up, suggest you to check them Fast exponentiation algorithm - How to arrive at it?, https://en.wikipedia.org/wiki/Exponentiation_by_squaring.

Algorithm Pseudocode

To be even more specific, lets construct one such algorithm. Let's pick for example this fast exponentiation algorithm:

Function exp-by-squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp-by-squaring(x * x,  n / 2);
    else if n is odd  then return x * exp-by-squaring(x * x, (n - 1) / 2);

Now replacing $x$ with pair of numbers $a,b$, and similarly the multiplication with the one described above, we get:

Function exp-by-squaring(a, b, n)
    if n = 0  then return  (1,0);
    else if n is even  then return exp-by-squaring(a*a+3b*b, 2ab,  n / 2);
    else if n is odd  then 
        (c,d) = exp-by-squaring(a*a+3b*b, 2ab, (n - 1) / 2);
        return (ac+3bd,ad+bc);

This by the way shows how you can calculate powers in general, you just need to have multiplication defined. Even in cases where it first looks like the problem is only solvable by recursions, this trick allows to skip many steps.

Python example

Now if you turn this into python (or any programming language you like), you can play with it:

def exp(a, b, n):
  if n == 0: 
    return (1,0)
  elif n % 2 == 0:
    return exp(a*a+3*b*b, 2*a*b,  n / 2)    
  elif n % 2 == 1:
    (c,d) = exp(a*a+3*b*b, 2*a*b, (n - 1) / 2)
    return (a*c+3*b*d,a*d+b*c)

For example

print exp(1,1,20)

yields

(268377088, 154947584)

And indeed, $(1+\sqrt{3})^{20} = 268377088+154947584\sqrt{3}$

Also notice there were only $5$ multiplications done, compared to naive $19$:

\begin{align} (1+\sqrt{3})^2 &= (1+\sqrt{3}) \cdot (1+\sqrt{3})\\ (1+\sqrt{3})^4 &= (1+\sqrt{3})^2 \cdot (1+\sqrt{3})^2\\ (1+\sqrt{3})^8 &= (1+\sqrt{3})^4 \cdot (1+\sqrt{3})^4\\ (1+\sqrt{3})^{16} &= (1+\sqrt{3})^8 \cdot (1+\sqrt{3})^8\\ (1+\sqrt{3})^{20} &= (1+\sqrt{3})^4 \cdot (1+\sqrt{3})^{16}\\ \end{align}

Answer 2

Hint: let $(a+b\sqrt{3})^n = c_n+d_n \sqrt{3}$. Then $(a+b\sqrt{3})^{n+1} = (a c_n + 3 b d_n) +(a d_n + b c_n)\sqrt{3}$ which gives the double recurrence $c_{n+1}=a c_n + 3 b d_n, d_{n+1}=a d_n + b c_n$ with $c_1=a, d_1=b$, that can easily be turned into a workable algorithm.

Answer 3

Consider this as a recursion:

$(a_n+b_n\sqrt{3})=(a+b\sqrt{3})^n = (a+b\sqrt{3})(a+b\sqrt{3})^{n-1} = (a+b\sqrt{3})(a_{n-1}+b_{n-1}\sqrt{3}) = aa_{n-1}+3bb_{n-1}+(ab_{n-1}+a_{n-1}b)\sqrt{3}$

Note that you can consider these as elements of a $\mathbb Q$-vector space with the base vectors $1$ and $\sqrt{3}$. With regard to this basis we can write thre recursion as:

$$\begin{pmatrix} a_n \\ b_n \end{pmatrix} = \underbrace{\begin{pmatrix}a & 3b \\ b & a \end{pmatrix}}_{=:M}\begin{pmatrix}a_{n-1}\\ b_{n-1}\end{pmatrix} = \begin{pmatrix}a & 3b \\ b & a \end{pmatrix}^n \begin{pmatrix} 1 \\ 0\end{pmatrix}$$

Now the $n$-th power of $M$ can efficiently be computed if you first diagonalize $M$ to $M=TDT^{-1}$ Then $M^n = TDT^-1TDT^-1 \cdots TDT^{-1} = TD^nT^{-1}$. Then $D^n$ is just the $n$-th power of the diagonal matrix $D$ which is easy to compute as you just have to take the entries of $D$ to the power of $n$.