\chapter{Exercises} \label{chap:Exercises} % TODO % % All exercises should be group with a chapter % % ▶ Recommended % M Matematically oriented % HM Higher matematical education required % % 00 Immediate % 10 Simple % 20 Medium % 30 Moderately hard % 40 Term project % 50 Research project % % ⁺ High risk of undershoot difficulty \begin{enumerate}[label=\textbf{\arabic*}.] \item {[$\RHD$\textit{02}]} \textbf{Saturated subtraction} Implement the function \vspace{-1em} \begin{alltt} void monus(z_t r, z_t a, z_t b); \end{alltt} \vspace{-1em} \noindent which calculates $r = a \dotminus b = \max \{ 0,~ a - b \}$. \item {[\textit{M10}]} \textbf{Convergence of the Lucas Number ratios} Find an approximation for $\displaystyle{ \lim_{n \to \infty} \frac{L_{n + 1}}{L_n}}$, where $L_n$ is the $n^{\text{th}}$ Lucas Number \psecref{sec:Lucas numbers}. \( \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 . }\) \item {[\textit{M12${}^+$}]} \textbf{Factorisation of factorials} Implement the function \vspace{-1em} \begin{alltt} void factor_fact(z_t n); \end{alltt} \vspace{-1em} \noindent which prints the prime factorisation of $n!$ (the $n^{\text{th}}$ factorial). The function shall be efficient for all $n$ where all primes $p \le n$ can be found efficiently. You can assume that $n \ge 2$. You should not evaluate $n!$. \item {[\textit{M20}]} \textbf{Reverse factorisation of factorials} {\small\textit{You should already have solved ``Factorisation of factorials'' before you solve this problem.}} Implement the function \vspace{-1em} \begin{alltt} void unfactor_fact(z_t x, z_t *P, unsigned long long int *K, size_t n); \end{alltt} \vspace{-1em} \noindent which given the factorsation of $x!$ determines $x$. The factorisation of $x!$ is $\displaystyle{\prod_{i = 1}^{n} P_i^{K_i}}$, where $P_i$ is \texttt{P[i - 1]} and $K_i$ is \texttt{K[i - 1]}. \item {[$\RHD$\textit{M17}]} \textbf{Factorials inverted} Implement the function \vspace{-1em} \begin{alltt} void unfact(z_t x, z_t n); \end{alltt} \vspace{-1em} \noindent which given a factorial number $n$, i.e. on the form $x! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot x$, calculates $x = n!^{-1}$. You can assume that $n$ is a perfect factorial number and that $x \ge 1$. Extra credit if you can detect when the input, $n$, is not a factorial number. Such function would of course return an \texttt{int} 1 if the input is a factorial and 0 otherwise, or alternatively 0 on success and $-1$ with \texttt{errno} set to \texttt{EDOM} if the input is not a factorial. \item {[\textit{05}]} \textbf{Fast primality test} $(x + y)^p \equiv x^p + y^p ~(\text{Mod}~p)$ for all primes $p$ and for a few composites $p$, which are know as pseudoprimes. Use this to implement a fast primality tester. \end{enumerate} \chapter{Solutions} \label{chap:Solutions} \begin{enumerate}[label=\textbf{\arabic*}.] \item \textbf{Saturated subtraction} \vspace{-1em} \begin{alltt} void monus(z_t r, z_t a, z_t b) \{ zsub(r, a, b); if (zsignum(r) < 0) zsetu(r, 0); \} \end{alltt} \item \textbf{Convergence of the Lucas Number ratios} It would be a mistake to use bignum, and bigint in particular, to solve this problem. Good old mathematics is a much better solution. $$ \lim_{n \to \infty} \frac{L_{n + 1}}{L_n} = \lim_{n \to \infty} \frac{L_{n}}{L_{n - 1}} = \lim_{n \to \infty} \frac{L_{n - 1}}{L_{n - 2}} $$ $$ \frac{L_{n}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}} $$ $$ \frac{L_{n - 1} + L_{n - 2}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}} $$ $$ 1 + \frac{L_{n - 2}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}} $$ $$ 1 + \varphi = \frac{1}{\varphi} $$ So the ratio tends toward the golden ratio. \item \textbf{Factorisation of factorials} Base your implementation on \( \displaystyle{ n! = \prod_{p~\in~\textbf{P}}^{n} p^{k_p}, ~\text{where}~ k_p = \sum_{a = 1}^{\lfloor \log_p n \rfloor} \lfloor np^{-a} \rfloor. }\) There is no need to calculate $\lfloor \log_p n \rfloor$, you will see when $p^a > n$. \item \textbf{Reverse factorisation of factorials} $\displaystyle{x = \max_{p ~\in~ P} ~ p \cdot f(p, k_p)}$, where $k_p$ is the power of $p$ in the factorisation of $x!$. $f(p, k)$ is defined as: \vspace{1em} \hspace{-2.8ex} \begin{minipage}{\linewidth} \begin{algorithmic} \STATE $k^\prime \gets 0$ \WHILE{$k > 0$} \STATE $a \gets 0$ \WHILE{$p^a \le k$} \STATE $k \gets k - p^a$ \STATE $a \gets a + 1$ \ENDWHILE \STATE $k^\prime \gets k^\prime + p^{a - 1}$ \ENDWHILE \RETURN $k^\prime$ \end{algorithmic} \end{minipage} \vspace{1em} \item \textbf{Factorials inverted} Use \texttt{zlsb} to get the power of 2 in the prime factorisation of $n$, that is, the number of times $n$ is divisible by 2. If we write $n$ on the form $1 \cdot 2 \cdot 3 \cdot \ldots \cdot x$, every $2^\text{nd}$ factor is divisible by 2, every $4^\text{th}$ factor is divisible by $2^2$, and so on. From call \texttt{zlsb} we know how many times, $n$ is divisible by 2, but know how many of the factors are divisible by 2, but this can be calculated with the following algorithm, where $k$ is the number times $n$ is divisible by 2: \vspace{1em} \hspace{-2.8ex} \begin{minipage}{\linewidth} \begin{algorithmic} \STATE $k^\prime \gets 0$ \WHILE{$k > 0$} \STATE $a \gets 0$ \WHILE{$2^a \le k$} \STATE $k \gets k - 2^a$ \STATE $a \gets a + 1$ \ENDWHILE \STATE $k^\prime \gets k^\prime + 2^{a - 1}$ \ENDWHILE \RETURN $k^\prime$ \end{algorithmic} \end{minipage} \vspace{1em} \noindent Note that $2^a$ is efficiently calculated with, \texttt{zlsh}, but it is more efficient to use \texttt{zbset}. Now that we know $k^\prime$, the number of factors ni $1 \cdot \ldots \cdot x$ that are divisible by 2, we have two choices for $x$: $k^\prime$ and $k^\prime + 1$. To check which, we calculate $(k^\prime - 1)!!$ (the semifactoral, i.e. $1 \cdot 3 \cdot 5 \cdot \ldots \cdot (k^\prime - 1)$) naïvely and shift the result $k$ steps to the left. This gives us $k^\prime!$. If $x! \neq k^\prime!$, then $x = k^\prime + 1$ unless $n$ is not factorial number. Of course, if $x! = k^\prime!$, then $x = k^\prime$. \item \textbf{Fast primality test} If we select $x = y = 1$ we get $2^p \equiv 2 ~(\text{Mod}~p)$. This gives us \vspace{-1em} \begin{alltt} enum zprimality ptest_fast(z_t p) \{ z_t a; int c = zcmpu(p, 2); if (c <= 0) return c ? NONPRIME : PRIME; zinit(a); zsetu(a, 1); zlsh(a, a, p); zmod(a, a, p); c = zcmpu(a, 2); zfree(a); return c ? NONPRIME : PROBABLY_PRIME; \} \end{alltt} \end{enumerate}