(wrong string) ée

From: <git_AT_suckless.org>
Date: Fri, 29 Jul 2016 12:35:15 +0200 (CEST)

commit f9fac01b221cd41af5352d95a45ba43b47460a41
Author: Mattias Andrée <maandree_AT_kth.se>
AuthorDate: Fri Jul 29 12:34:29 2016 +0200
Commit: Mattias Andrée <maandree_AT_kth.se>
CommitDate: Fri Jul 29 12:34:29 2016 +0200

    Add exercise: [HMP32] Modular tetration
    
    Signed-off-by: Mattias Andrée <maandree_AT_kth.se>

diff --git a/doc/exercises.tex b/doc/exercises.tex
index 01dfb39..7828cf8 100644
--- a/doc/exercises.tex
+++ b/doc/exercises.tex
_AT_@ -232,7 +232,7 @@ rather than
 
 
 
-\item {[$\RHD$M15]} \textbf{Modular left-shift}
+\item {[\textit{$\RHD$M15}]} \textbf{Modular left-shift}
 
 Implement a function that calculates
 $2^a \text{ mod } b$, using \texttt{zmod} and
_AT_@ -242,7 +242,7 @@ parameters are unique pointers.
 
 
 
-\item {[$\RHD$08]} \textbf{Modular left-shift, extended}
+\item {[\textit{$\RHD$08}]} \textbf{Modular left-shift, extended}
 
 {\small\textit{You should already have solved
 ``Modular left-shift'' before you solve this
_AT_@ -253,7 +253,7 @@ to accept negative $b$ and non-unique pointers.
 
 
 
-\item {[13]} \textbf{The totient}
+\item {[\textit{13}]} \textbf{The totient}
 
 The totient of $n$ is the number of integer $a$,
 $0 < a < n$ that are relatively prime to $n$.
_AT_@ -271,6 +271,25 @@ and $\varphi(1) = 1$.
 
 
 
+\item {[\textit{HMP32}]} \textbf{Modular tetration}
+
+Implement the function
+
+\vspace{-1em}
+\begin{alltt}
+ void modtetra(z_t r, z_t b, unsigned long n, z_t m);
+\end{alltt}
+\vspace{-1em}
+
+\noindent
+which calculates $r = {}^n{}b \text{ mod } m$, where
+${}^0{}b = 1$, ${}^1{}b = b$, ${}^2{}b = b^b$,
+${}^3{}b = b^{b^b}$, ${}^b{}b = b^{b^{b^b}}$, and so on.
+You can assume $b > 0$ and $m > 0$. You can also assume
+\texttt{r}, \texttt{b}, and \texttt{m} are mutually
+unique pointers.
+
+
 \end{enumerate}
 
 
_AT_@ -621,7 +640,8 @@ need to evaluate $2^{2^{64}}$.
 
 \vspace{-1em}
 \begin{alltt}
-void modlsh(z_t r, z_t a, z_t b)
+void
+modlsh(z_t r, z_t a, z_t b)
 \{
     z_t t, at;
     size_t s = zbits(b);
_AT_@ -679,5 +699,107 @@ then, $\varphi(n) = \varphi|n|$.
 
 
 
+\item \textbf{Modular tetration}
+
+Let \texttt{totient} be Euler's totient function.
+It is described in the problem ``The totient''.
+
+We need two help function: \texttt{tetra(r, b, n)}
+which calculated $r = {}^n{}b$, and \texttt{cmp\_tetra(a, b, n)}
+which is compares $a$ to ${}^n{}b$.
+
+\vspace{-1em}
+\begin{alltt}
+void
+tetra(z_t r, z_t b, unsigned long n)
+\{
+ zsetu(r, 1);
+ while (n--)
+ pow(r, b, r);
+\}
+\end{alltt}
+\vspace{-1em}
+
+\vspace{-1em}
+\begin{alltt}
+int
+cmp_tetra(z_t a, z_t b, unsigned long n)
+\{
+ z_t B;
+ int cmp;
+
+ if (!n || !zcmpu(b, 1))
+ return zcmpu(a, 1);
+ if (n == 1)
+ return zcmp(a, b);
+ if (zcmp(a, b) >= 0)
+ return +1;
+
+ zinit(B);
+ zsetu(B, 1);
+ while (n) \{
+ zpow(B, b, B);
+ if (zcmp(a, B) < 0) \{
+ zfree(B);
+ return -1;
+ \}
+ \}
+ cmp = zcmp(a, B);
+ zfree(B);
+ return cmp;
+
+\}
+\end{alltt}
+\vspace{-1em}
+
+\texttt{tetra} can generate unmaintainably huge
+numbers. Will however only call \texttt{tetra}
+when this is not the case.
+
+\vspace{-1em}
+\begin{alltt}
+void
+modtetra(z_t r, z_t b, unsigned long n, z_t m)
+\{
+ z_t t, temp;
+
+ if (n <= 1) \{
+ if (n)
+ zsetu(r, zcmpu(m, 1));
+ else
+ zmod(r, b, m);
+ return;
+ \}
+
+ zmod(r, b, m);
+ if (zcmpu(r, 1) <= 0)
+ return;
+
+ zinit(t);
+ zinit(temp);
+
+ t = totient(m);
+ zgcd(temp, b, m);
+
+ if (!zcmpu(temp, 1)) \{
+ modtetra(temp, b, n - 1, t);
+ zmodpow(r, r, temp, m);
+ \} else if (cmp_tetra(t, b, n - 1) > 0) \{
+ temp = tetra(b, n - 1);
+ zpowmod(r, r, temp, m);
+ \} else \{
+ modtetra(temp, b, n - 1, t);
+ zmodpow(temp, r, temp, m);
+ zmodpow(r, r, t, m);
+ zmodmul(r, r, temp, m);
+ \}
+
+ zfree(temp);
+ zfree(t);
+\}
+\end{alltt}
+\vspace{-1em}
+
+
 
 \end{enumerate}
Received on Fri Jul 29 2016 - 12:35:15 CEST