1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
\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 overflows 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.
\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}
TODO % zpow zpowu zmodpow zmodpowu
\newpage
\section{Sign manipulation}
\label{sec:Sign manipulation}
TODO % zabs zneg
|
