path: root/doc/arithmetic.tex

\chapter{Arithmetic}
\label{chap:Arithmetic}

In this chapter, we will learn how to perform basic
arithmetic with libzahl: addition, subtraction,
multiplication, division, modulus, exponentiation,
and sign manipulation. \secref{sec:Division} is of
special importance.

\vspace{1cm}
\minitoc


\newpage
\section{Addition}
\label{sec:Addition}

To calculate the sum of two terms, we perform
addition using {\tt zadd}.

\vspace{1em}
$r \gets a + b$
\vspace{1em}

\noindent
is written as

\begin{alltt}
   zadd(r, a, b);
\end{alltt}

libzahl also provides {\tt zadd\_unsigned} which
has slightly lower overhead. The calculates the
sum of the absolute values of two integers.

\vspace{1em}
$r \gets \lvert a \rvert + \lvert b \rvert$
\vspace{1em}

\noindent
is written as

\begin{alltt}
   zadd_unsigned(r, a, b);
\end{alltt}

\noindent
{\tt zadd\_unsigned} has lower overhead than
{\tt zadd} because it does not need to inspect
or change the sign of the input, the low-level
function that performs the addition inherently
calculates the sum of the absolute values of
the input.

In libzahl, addition is implemented using a
technique called ripple-carry. It is derived
from that observation that

\vspace{1em}
$f : \textbf{Z}_n, \textbf{Z}_n \rightarrow \textbf{Z}_n$
\\ \indent
$f : a, b \mapsto a + b + 1$
\vspace{1em}

\noindent
only wraps at most once, that is, the
carry cannot exceed 1. CPU:s provide an
instruction specifically for performing
addition with ripple-carry over multiple words,
adds twos numbers plus the carry from the
last addition. libzahl uses assembly to
implement this efficiently. If however, an
assembly implementation is not available for
the on which machine it is running, libzahl
implements ripple-carry less efficiently
using compiler extensions that check for
overflow. In the event that neither an
assembly implementation is available nor
the compiler is known to support this
extension, it is implemented using inefficient
pure C code. This last resort manually
predicts whether an addition will overflow;
this could be made more efficent, but never
using the highest bit, in each character,
except to detect overflow. This optimisation
is however not implemented because it is
not deemed important enough and would
be detrimental to libzahl's simplicity.

{\tt zadd} and {\tt zadd\_unsigned} support
in-place operation:

\begin{alltt}
   zadd(a, a, b);
   zadd(b, a, b);           \textcolor{c}{/* \textrm{should be avoided} */}
   zadd_unsigned(a, a, b);
   zadd_unsigned(b, a, b);  \textcolor{c}{/* \textrm{should be avoided} */}
\end{alltt}

\noindent
Use this whenever possible, it will improve
your performance, as it will involve less
CPU instructions for each character-addition
and it may be possible to eliminate some
character-additions.


\newpage
\section{Subtraction}
\label{sec:Subtraction}

TODO % zsub zsub_unsigned


\newpage
\section{Multiplication}
\label{sec:Multiplication}

TODO % zmul zmodmul


\newpage
\section{Division}
\label{sec:Division}

TODO % zdiv zmod zdivmod


\newpage
\section{Exponentiation}
\label{sec:Exponentiation}

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_{k \in \textbf{Z}_{+} ~:~ \left \lfloor \frac{b}{2^k} \hspace*{-1ex} \mod 2 \right \rfloor = 1}
    a^{2^k}
\]

\noindent
This is a natural extension to the
observations\footnote{The first of course being
that any non-negative number can be expressed
with the binary positional system. The latter
should be fairly self-explanatory.}

\vspace{-1em}
\[ \hspace*{-0.4cm}
    \forall b \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, f \gets 1, a$
    \WHILE{$b \neq 0$}
      \STATE $r \gets r \cdot f$ {\bf unless} $2 \vert b$
      \STATE $f \gets f^2$ \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, f \gets 1, a$
    \WHILE{$b \neq 0$}
      \STATE $r \gets r \cdot f \hspace*{-1ex}~ \mod m$ \textbf{unless} $2 \vert b$
      \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
1 and 0 depending of whether the base is 1
or not 1.


\newpage
\section{Sign manipulation}
\label{sec:Sign manipulation}

libzahl provides two functions for manipulating
the sign of integers:

\begin{alltt}
   void zabs(z_t r, z_t a);
   void zneg(z_t r, z_t a);
\end{alltt}

{\tt zabs} stores the absolute value of {\tt a}
in {\tt r}, that is, it creates a copy of
{\tt a} to {\tt r}, unless {\tt a} and {\tt r}
are the same reference, and then removes its sign;
if the value is negative, it becomes positive.

\vspace{1em}
\(
    r \gets \lvert a \rvert =
    \left \lbrace \begin{array}{rl}
        -a & \quad \textrm{if}~a \le 0 \\
        +a & \quad \textrm{if}~a \ge 0 \\
    \end{array} \right .
\)
\vspace{1em}

{\tt zneg} stores the negated of {\tt a}
in {\tt r}, that is, it creates a copy of
{\tt a} to {\tt r}, unless {\tt a} and {\tt r}
are the same reference, and then flips sign;
if the value is negative, it becomes positive,
if the value is positive, it becomes negative.

\vspace{1em}
\(
    r \gets -a
\)
\vspace{1em}

Note that there is no function for

\vspace{1em}
\(
    r \gets -\lvert a \rvert =
    \left \lbrace \begin{array}{rl}
         a & \quad \textrm{if}~a \le 0 \\
        -a & \quad \textrm{if}~a \ge 0 \\
    \end{array} \right .
\)
\vspace{1em}

\noindent
calling {\tt zabs} followed by {\tt zneg}
should be sufficient for most users:

\begin{alltt}
   #define my_negabs(r, a)  (zabs(r, a), zneg(r, r))
\end{alltt}