# libzahl

big integer library
git clone git://git.suckless.org/libzahl

commit 802b2b18704f1b04ab3c3195d49333a546dc0ff4
parent 63bc4e141d2f28fcd11187413966235151a92c84
Author: Mattias Andrée <maandree@kth.se>
Date:   Mon, 25 Jul 2016 15:13:29 +0200

Add exercise: [30] Powers of the golden ratio

Signed-off-by: Mattias Andrée <maandree@kth.se>

Diffstat:
 M doc/exercises.tex | 38 ++++++++++++++++++++++++++++++++++++++
1 file changed, 38 insertions(+), 0 deletions(-)

diff --git a/doc/exercises.tex b/doc/exercises.tex @@ -188,6 +188,14 @@ than or equal to a preselected number. +\item {[\textit{30}]} \textbf{Powers of the golden ratio} + +Implement function that returns $\varphi^n$ rounded +to the nearest integer, where $n$ is the input and +$\varphi$ is the golden ratio. + + + \end{enumerate} @@ -477,5 +485,35 @@ the set of pseudoprimes. +\item \textbf{Powers of the golden ratio} + +This was an information gathering exercise. +For $n \ge 1$, $L_n = [\varphi^n]$, where +$L_n$ is the $n^\text{th}$ Lucas number. + +$$\displaystyle{ + L_n \stackrel{\text{\tiny{def}}}{\text{=}} \left \{ \begin{array}{ll} + 2 & \text{if} ~ n = 0 \\ + 1 & \text{if} ~ n = 1 \\ + L_{n - 1} + L_{n + 1} & \text{otherwise} + \end{array} \right . +}$$ + +\noindent +but for efficiency and briefness, we will use +\texttt{lucas} from \secref{sec:Lucas numbers}. + +\vspace{-1em} +\begin{alltt} +void golden_pow(z_t r, z_t p) +\{ + if (zsignum(p) <= 0) + zsetu(r, zzero(p)); + else + lucas(r, p); +\} +\end{alltt} + + \end{enumerate}