diff options
| author | Mattias Andrée <maandree@kth.se> | 2016-07-27 03:58:35 +0200 |
|---|---|---|
| committer | Mattias Andrée <maandree@kth.se> | 2016-07-27 03:58:35 +0200 |
| commit | b8f83987b190e282fd25c24e1c251678ad757765 (patch) | |
| tree | f16f3a696f36bcb47bc348746f60aa01782ae5b2 /doc/exercises.tex | |
| parent | Exercise solutions: the return type should be on the line above the function name, like in the rest of the manual (diff) | |
| download | libzahl-b8f83987b190e282fd25c24e1c251678ad757765.tar.gz libzahl-b8f83987b190e282fd25c24e1c251678ad757765.tar.bz2 libzahl-b8f83987b190e282fd25c24e1c251678ad757765.tar.xz | |
Add exercice: [▶10] Modular powers of 2
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat (limited to '')
| -rw-r--r-- | doc/exercises.tex | 17 |
1 files changed, 17 insertions, 0 deletions
diff --git a/doc/exercises.tex b/doc/exercises.tex index e004f0a..83b79f8 100644 --- a/doc/exercises.tex +++ b/doc/exercises.tex @@ -38,6 +38,14 @@ which calculates $r = a \dotminus b = \max \{ 0,~ a - b \}$. +\item {[$\RHD$\textit{10}]} \textbf{Modular powers of 2} + +What is the advantage of using \texttt{zmodpow} +over \texttt{zbset} or \texttt{zlsh} in combination +with \texttt{zmod}? + + + \item {[\textit{M10}]} \textbf{Convergence of the Lucas Number ratios} Find an approximation for @@ -219,6 +227,15 @@ void monus(z_t r, z_t a, z_t b) \end{alltt} +\item \textbf{Modular powers of 2} + +\texttt{zbset} and \texttt{zbit} requires $\Theta(n)$ +memory to calculate $2^n$. \texttt{zmodpow} only +requires $\mathcal{O}(\min \{n, \log m\})$ memory +to calculate $2^n \text{ mod } m$. $\Theta(n)$ +memory complexity becomes problematic for very +large $n$. + \item \textbf{Convergence of the Lucas Number ratios} |