(wrong string) ée

From: <git_AT_suckless.org>
Date: Thu, 12 May 2016 01:25:14 +0200 (CEST)

commit fba103dca7a472eb58159d45ff8700736f89a136
Author: Mattias Andrée <maandree_AT_kth.se>
AuthorDate: Thu May 12 00:30:53 2016 +0200
Commit: Mattias Andrée <maandree_AT_kth.se>
CommitDate: Thu May 12 00:30:53 2016 +0200

    On exponentiation
    
    Signed-off-by: Mattias Andrée <maandree_AT_kth.se>

diff --git a/doc/arithmetic.tex b/doc/arithmetic.tex
index bd761c4..6835c43 100644
--- a/doc/arithmetic.tex
+++ b/doc/arithmetic.tex
_AT_@ -130,7 +130,71 @@ TODO % zdiv zmod zdivmod
 \section{Exponentiation}
 \label{sec:Exponentiation}
 
-TODO % zpow zpowu zmodpow zmodpowu
+Exponentiation refers to raising a number to
+a power. libzahl provides two functions for
+regular exponentiation, and two functions for
+modular exponentiation. libzahl also provides
+a function for raising a number to the second
+power, see \secref{sec:Multiplication} for
+more details on this. The functions for regular
+exponentiation are
+
+\begin{alltt}
+ void zpow(z_t power, z_t base, z_t exponent);
+ void zpowu(z_t, z_t, unsigned long long int);
+\end{alltt}
+
+\noindent
+They are identical, except {\tt zpowu} expects
+and intrinsic type as the exponent. Both functions
+calculate
+
+\vspace{1em}
+$power \gets base^{exponent}$
+\vspace{1em}
+
+\noindent
+The functions for modular exponentiation are
+\begin{alltt}
+ void zmodpow(z_t, z_t, z_t, z_t modulator);
+ void zmodpowu(z_t, z_t, unsigned long long int, z_t);
+\end{alltt}
+
+\noindent
+They are identical, except {\tt zmodpowu} expects
+and intrinsic type as the exponent. Both functions
+calculate
+
+\vspace{1em}
+$power \gets base^{exponent} \mod modulator$
+\vspace{1em}
+
+The sign of {\tt modulator} does not affect the
+result, {\tt power} will be negative if and only
+if {\tt base} is negative and {\tt exponent} is
+odd, that is, under the same circumstances as for
+{\tt zpow} and {\tt zpowu}.
+
+These four functions are implemented using
+exponentiation by squaring. {\tt zmodpow} and
+{\tt zmodpowu} are optimised, they modulate
+results for multiplication and squaring at
+every multiplication and squaring, rather than
+modulating every at the end. Exponentiation
+by modulation is a very simple algorithm which
+can be expressed as a simple formula
+
+\vspace{-1em}
+\[ \hspace*{-0.4cm}
+ a^b = \prod_{i = 0}^{\lceil \log_2 b \rceil}
+ a^{2^i} \left \lfloor {b \over 2^i} \hspace*{-1ex} \mod 2 \right \rfloor
+\]
+
+{\tt zmodpow} does \emph{not} calculate the
+modular inverse if the exponent is negative,
+rather, you should expect the result to be
+1 and 0 depending of whether the base is 1
+or not 1.
 
 
 \newpage
diff --git a/doc/libzahl.tex b/doc/libzahl.tex
index c417fff..83d74c4 100644
--- a/doc/libzahl.tex
+++ b/doc/libzahl.tex
_AT_@ -1,4 +1,4 @@
-\documentclass[11pt,b5paper,openright]{book}
+\documentclass[11pt,b5paper,openright,fleqn]{book}
 \special{papersize=176mm,250mm}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
Received on Thu May 12 2016 - 01:25:14 CEST