(wrong string) ée

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

commit f1b60d7365ca1437efd3f6f8c05d2cdc46bd24b6
Author: Mattias Andrée <maandree_AT_kth.se>
AuthorDate: Thu May 12 01:14:52 2016 +0200
Commit: Mattias Andrée <maandree_AT_kth.se>
CommitDate: Thu May 12 01:17:07 2016 +0200

    More on exponentiation by squaring
    
    Signed-off-by: Mattias Andrée <maandree_AT_kth.se>

diff --git a/doc/arithmetic.tex b/doc/arithmetic.tex
index 6835c43..45097e2 100644
--- a/doc/arithmetic.tex
+++ b/doc/arithmetic.tex
_AT_@ -187,9 +187,62 @@ 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
+ \left ( a^{2^i} \right )^{\left \lfloor {\displaystyle{b \over 2^i}} \hspace*{-1ex} \mod 2 \right \rfloor}
 \]
 
+\noindent
+This is a natural extension to the observations
+
+\vspace{-1em}
+\[ \hspace*{-0.4cm}
+ \forall n \in \textbf{Z}_{+} \exists B \subset \textbf{Z}_{+} : b = \sum_{i \in B} 2^i
+ ~~~~ \textrm{and} ~~~~
+ a^{\sum x} = \prod a^x.
+\]
+
+\noindent
+The algorithm can be expressed in psuedocode as
+
+\vspace{1em}
+\hspace{-2.8ex}
+\begin{minipage}{\linewidth}
+\begin{algorithmic}
+ \STATE $r \gets 1$
+ \STATE $f \gets a$
+ \WHILE{$b \neq 0$}
+ \IF{$b \equiv 1 ~(\textrm{Mod}~ 2)$}
+ \STATE $r \gets r \cdot f$
+ \ENDIF
+ \STATE $f \gets f^2$ \qquad \textcolor{c}{\{$f \gets f \cdot f$\}}
+ \STATE $b \gets \lfloor b / 2 \rfloor$
+ \ENDWHILE
+ \RETURN $r$
+\end{algorithmic}
+\end{minipage}
+\vspace{1em}
+
+\noindent
+Modular exponentiation ($a^b \mod m$) by squaring can be
+expressed as
+
+\vspace{1em}
+\hspace{-2.8ex}
+\begin{minipage}{\linewidth}
+\begin{algorithmic}
+ \STATE $r \gets 1$
+ \STATE $f \gets a$
+ \WHILE{$b \neq 0$}
+ \IF{$b \equiv 1 ~(\textrm{Mod}~ 2)$}
+ \STATE $r \gets r \cdot f \hspace*{-1ex}~ \mod m$
+ \ENDIF
+ \STATE $f \gets f^2 \hspace*{-1ex}~ \mod m$
+ \STATE $b \gets \lfloor b / 2 \rfloor$
+ \ENDWHILE
+ \RETURN $r$
+\end{algorithmic}
+\end{minipage}
+\vspace{1em}
+
 {\tt zmodpow} does \emph{not} calculate the
 modular inverse if the exponent is negative,
 rather, you should expect the result to be
Received on Thu May 12 2016 - 01:25:14 CEST