 |
Add exercice: [▶10] Modular powers of 2 - libzahl - big integer library |
 |
git clone git://git.suckless.org/libzahl |
 |
Log |
|
Files |
|
Refs |
|
README |
|
LICENSE |
|
--- |
|
commit b8f83987b190e282fd25c24e1c251678ad757765 |
|
parent faaa7dc980a80895b703775d18132eb6db105021 |
|
Author: Mattias Andrée <[email protected]> |
|
Date: Wed, 27 Jul 2016 03:58:35 +0200 |
|
|
|
Add exercice: [▶10] Modular powers of 2 |
|
|
|
Signed-off-by: Mattias Andrée <[email protected]> |
|
|
|
Diffstat: |
|
M doc/exercises.tex | 17 +++++++++++++++++ |
|
|
|
1 file changed, 17 insertions(+), 0 deletions(-) |
|
--- |
|
diff --git 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} |
|
