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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
\chapter{Number theory}
\label{chap:Number theory}
In this chapter, you will learn about the
number theoretic functions in libzahl.
\vspace{1cm}
\minitoc
\newpage
\section{Odd or even}
\label{sec:Odd or even}
There are four functions available for testing
the oddness and evenness of an integer:
\begin{alltt}
int zodd(z_t a);
int zeven(z_t a);
int zodd_nonzero(z_t a);
int zeven_nonzero(z_t a);
\end{alltt}
\noindent
{\tt zodd} returns 1 if {\tt a} contains an
odd value, or 0 if {\tt a} contains an even
number. Conversely, {\tt zeven} returns 1 if
{\tt a} contains an even value, or 0 if {\tt a}
contains an odd number. {\tt zodd\_nonzero} and
{\tt zeven\_nonzero} behave exactly like {\tt zodd}
and {\tt zeven}, respectively, but assumes that
{\tt a} contains a non-zero value, if not
undefined behaviour is invoked, possibly in the
form of a segmentation fault; they are thus
sligtly faster than {\tt zodd} and {\tt zeven}.
It is discouraged to test the returned value
against 1, we should always test against 0,
treating all non-zero value as equivalent to 1.
For clarity, we use also avoid testing that
the returned value is zero, for example, rather
than {\tt !zeven(a)} we write {\tt zodd(a)}.
\newpage
\section{Signum}
\label{sec:Signum}
There are two functions available for testing
the sign of an integer, one of the can be used
to retrieve the sign:
\begin{alltt}
int zsignum(z_t a);
int zzero(z_t a);
\end{alltt}
\noindent
{\tt zsignum} returns $-1$ if $a < 0$,
$0$ if $a = 0$, and $+1$ if $a > 0$, that is,
\vspace{1em}
\( \displaystyle{
\mbox{sgn}~a = \left \lbrace \begin{array}{rl}
-1 & \textrm{if}~ a < 0 \\
0 & \textrm{if}~ a = 0 \\
+1 & \textrm{if}~ a > 0
\end{array} \right .
}\)
\vspace{1em}
\noindent
It is discouraged to compare the returned value
against $-1$ and $+1$; always compare against 0,
for example:
\begin{alltt}
if (zsignum(a) > 0) "positive";
if (zsignum(a) >= 0) "non-negative";
if (zsignum(a) == 0) "zero";
if (!zsignum(a)) "zero";
if (zsignum(a) <= 0) "non-positive";
if (zsignum(a) < 0) "negative";
if (zsignum(a)) "non-zero";
\end{alltt}
\noindent
However, when we are doing arithmetic with the
signum, we may relay on the result never being
any other value than $-1$, $0$, and $+0$.
For example:
\begin{alltt}
zset(sgn, zsignum(a));
zadd(b, sgn);
\end{alltt}
{\tt zzero} returns 0 if $a = 0$ or 1 if
$a \neq 0$. Like with {\tt zsignum}, avoid
testing the returned value against 1, rather
test that the returned value is not 0. When
however we are doing arithmetic with the
result, we may relay on the result never
being any other value than 0 or 1.
\newpage
\section{Greatest common divisor}
\label{sec:Greatest common divisor}
There is no single agreed upon definition
for the greatest common divisor of two
integer, that cover non-positive integers.
In libzahl we define it as
\vspace{1em}
\( \displaystyle{
\gcd(a, b) = \left \lbrace \begin{array}{rl}
-k & \textrm{if}~ a < 0, b < 0 \\
b & \textrm{if}~ a = 0 \\
a & \textrm{if}~ b = 0 \\
k & \textrm{otherwise}
\end{array} \right .
}\),
\vspace{1em}
\noindent
where $k$ is the largest integer that divides
both $\lvert a \rvert$ and $\lvert b \rvert$. This
definion ensures
\vspace{1em}
\( \displaystyle{
{a \over \gcd(a, b)} \left \lbrace \begin{array}{rl}
> 0 & \textrm{if}~ a < 0, b < 0 \\
< 0 & \textrm{if}~ a < 0, b > 0 \\
= 1 & \textrm{if}~ b = 0, a \neq 0 \\
= 0 & \textrm{if}~ a = 0, b \neq 0 \\
\in \textbf{N} & \textrm{otherwise if}~ a \neq 0, b \neq 0
\end{array} \right .
}\),
\vspace{1em}
\noindent
and analogously for $b \over \gcd(a,\,b)$. Note however,
the convension $\gcd(0, 0) = 0$ is adhered. Therefore,
before dividing with $\gcd{a, b}$ you may want to check
whether $\gcd(a, b) = 0$. $\gcd(a, b)$ is calculated
with {\tt zgcd(a, b)}.
{\tt zgcd} calculates the greatest common divisor using
the Binary GCD algorithm.
\vspace{1em}
\hspace{-2.8ex}
\begin{minipage}{\linewidth}
\begin{algorithmic}
\IF{$ab = 0$}
\RETURN $a + b$
\ELSIF{$a < 0$ \AND $b < 0$}
\RETURN $-\gcd(\lvert a \rvert, \lvert b \rvert)$
\ENDIF
\STATE $s \gets \max s : 2^s \vert a, b$
\STATE $u, v \gets \lvert a \rvert \div 2^s, \lvert b \rvert \div 2^s$
\WHILE{$u \neq v$}
\IF{$u > v$}
\STATE $u \leftrightarrow v$
\ENDIF
\STATE $v \gets v - u$
\STATE $v \gets v \div 2^x$, where $x = \max x : 2^x \vert v$
\ENDWHILE
\RETURN $u \cdot 2^s$
\end{algorithmic}
\end{minipage}
\vspace{1em}
\noindent
$\max x : 2^x \vert z$ is returned by {\tt zlsb(z)}
\psecref{sec:Boundary}.
\newpage
\section{Primality test}
\label{sec:Primality test}
TODO % zptest
|
