path: root/doc/exercises.tex

\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 $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$.
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}