= Fast doubling for Lucas sequences
= Lucas fast doubling
{c}
{synonym}
<Lucas sequences> satisfy
$$
U_{2n}=U_nV_n,\qquad V_{2n}=V_n^2-2Q^n,\qquad U_{2n+1}=U_{n+1}^2-QU_n^2.
$$
These identities follow from the root formulas for the <Lucas U-sequence> and <Lucas V-sequence>, or from their recurrence, so they are <polynomial> identities valid over a <commutative ring>. They compute terms with doubled indices from terms with about half the index.
A division-free algorithm carries $(U_n,U_{n+1})$. Put $a=U_n$, $b=U_{n+1}$, $c=a(2b-Pa)$ and $d=b^2-Qa^2$. For an even target return $(c,d)$; for an odd target return $(d,Pd-Qc)$. Starting from $(U_0,U_1)=(0,1)$ and following the binary digits of the target uses $O(\log n)$ <ring> operations. At $(P,Q)=(1,-1)$ this is the usual <Fibonacci> doubling method, and it also works in <modular arithmetic>.
Back to article page
