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



\item {[\textit{10}]} \textbf{Fermat primality test}

$a^{p - 1} \equiv 1 ~(\text{Mod}~p) ~\forall~ 1 < a < p$
for all primes $p$ and for a few composites $p$,
which are know as pseudoprimes\footnote{If $p$ is composite
but passes the test for all $a$, $p$ is a Carmichael
number.}. Use this to implement a heuristic primality
tester. Try to mimic \texttt{zptest} as much as possible.
GNU~MP uses $a = 210$, but you don't have to. ($a$ is
called a base.)



\item {[\textit{11}]} \textbf{Lucas–Lehmer primality test}

The Lucas–Lehmer primality test can be used to determine
whether a Mersenne numbers $M_n = 2^n - 1$ is a prime (a
Mersenne prime). $M_n$ is a prime if and only if
$s_{n - 1} \equiv 0 ~(\text{Mod}~M_n)$, where

\( \displaystyle{
    s_i = \left \{ \begin{array}{ll}
      4 & \text{if} ~ i = 0 \\
      s_{i - 1}^2 - 2 & \text{otherwise}.
    \end{array} \right .
}\)

\noindent
The Lucas–Lehmer primality test requires that $n \ge 3$,
however $M_2 = 2^2 - 1 = 3$ is a prime. Implement a version
of the Lucas–Lehmer primality test that takes $n$ as the
input. For some more fun, when you are done, you can
implement a version that takes $M_n$ as the input.

For improved performance, instead of using \texttt{zmod},
you can use the recursive function
%
\( \displaystyle{
    k ~\mbox{Mod}~ 2^n - 1 =
    \left (
      (k ~\mbox{Mod}~ 2^n) + \lfloor k \div 2^n \rfloor
    \right ) ~\mbox{Mod}~ 2^n - 1,
}\)
%
where $k ~\mbox{Mod}~ 2^n$ is efficiently calculated
using \texttt{zand($k$, $2^n - 1$)}. (This optimisation
is not part of the difficulty rating of this problem.)



\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 calling \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}



\item \textbf{Fermat primality test}

Below is a simple implementation. It can be improved by
just testing against a fix base, such as $a = 210$, it
$t = 0$. It could also do an exhaustive test (all $a$
such that $1 < a < p$) if $t < 0$.

\vspace{-1em}
\begin{alltt}
enum zprimality ptest_fermat(z_t witness, z_t p, int t)
\{
    enum zprimality rc = PROBABLY_PRIME;
    z_t a, p1, p3, temp;
    int c;

    if ((c = zcmpu(p, 2)) <= 0) \{
        if (!c)
            return PRIME;
        if (witness && witness != p)
            zset(witness, p);
        return NONPRIME;
    \}

    zinit(a), zinit(p1), zinit(p3), zinit(temp);
    zsetu(temp, 3), zsub(p3, p, temp);
    zsetu(temp, 1), zsub(p1, p, temp);

    zsetu(temp, 2);
    while (t--) \{
        zrand(a, DEFAULT_RANDOM, UNIFORM, p3);
        zadd(a, a, temp);
        zmodpow(a, a, p1, p);
        if (zcmpu(a, 1)) \{
            if (witness)
                zswap(witness, a);
            rc = NONPRIME;
            break;
        \}
    \}

    zfree(temp), zfree(p3), zfree(p1), zfree(a);
    return rc;
\}
\end{alltt}



\item \textbf{Lucas–Lehmer primality test}

\vspace{-1em}
\begin{alltt}
enum zprimality ptest_llt(z_t n)
\{
    z_t s, M;
    int c;
    size_t p;

    if ((c = zcmpu(n, 2)) <= 0)
        return c ? NONPRIME : PRIME;

    if (n->used > 1) \{
        \textcolor{c}{/* \textrm{An optimised implementation would not need this} */}
        errno = ENOMEM;
        return (enum zprimality)(-1);
    \}

    zinit(s), zinit(M), zinit(2);

    p = (size_t)(n->chars[0]);
    zsetu(s, 1), zsetu(M, 0);
    zbset(M, M, p, 1), zsub(M, M, s);
    zsetu(s, 4);
    zsetu(two, 2);

    p -= 2;
    while (p--) \{
        zsqr(s, s);
        zsub(s, s, two);
        zmod(s, s, M);
    \}
    c = zzero(s);

    zfree(two), zfree(M), zfree(s);
    return c ? PRIME : NONPRIME;
\}
\end{alltt}

$M_n$ is composite if $n$ is composite, therefore,
if you do not expect prime-only values on $n$, the
performance can be improve by using some other
primality test (or this same test if $n$ is a
Mersenne number) to first check that $n$ is prime.



\end{enumerate}