3471ebd1 |
1 | %%% -*-latex-*- |
2 | |
3 | \section{Low-level details: MPX} |
4 | \label{sec:mpx} |
5 | |
6 | |
7 | \subsection{Data types for low-level arithmetic} |
8 | |
9 | The header file \hdr{<catacomb/mpw.h>} defines two types, \code{mpw} and |
10 | \code{mpd}, and a collection of macros describing them. |
11 | |
12 | The `multiprecision word' type, \code{mpw}, is an unsigned integer type whose |
13 | representation uses \code{MPW_BITS}. The largest value representable in an |
14 | \code{mpw} is $\code{MPW_MAX} = 2^{\code{MPW_BITS}} - 1$. |
15 | The value of \code{MPW_BITS} is at least 16. Note that, on some |
16 | architectures, an \code{mpw} may be capable of representing values larger |
17 | than \code{MPW_MAX}. The expression \code{MPW($x$)} returns the value of $x |
18 | \bmod \code{MPW_MAX}$ cast to type \code{mpw}. |
19 | |
20 | The `multiprecision doubleword' type, \code{mpd}, is an unsigned integer type |
21 | with at least double the width of \code{mpw}. Hence, an \code{mpd} is |
22 | capable of representing the product of two \code{mpw}s, and is useful when |
23 | performing multiplications and divisions. The constants \code{MPD_BITS} and |
24 | \code{MPD_MAX} are defined to be the number of bits used in the |
25 | representation of an \code{mpd} and the largest value representable in an |
26 | \code{mpd} respectively. |
27 | |
28 | A few macros useful for manipulating \code{mpw}s are defined. |
29 | |
30 | \subsubsection{The \code{MPW} macro} |
31 | \label{fn:MPW} |
32 | |
33 | \fsec{Synopsis} |
34 | |
35 | \begin{listinglist} |
36 | |#include <catacomb/mpw.h>| \\ |
37 | |mpw MPW(|$x$|);| |
38 | \end{listinglist} |
39 | |
40 | \fsec{Returns} |
41 | |
42 | The value of $x \bmod 2^{\code{MPW_BITS}}$, as an \code{mpw}. This is a |
43 | frequently used abbreviation for |(mpw)(|$x$| & MPW_MAX)|. |
44 | |
45 | \subsubsection{The \code{MPWS} macro} |
46 | \label{fn:MPWS} |
47 | |
48 | \fsec{Synopsis} |
49 | |
50 | \begin{listinglist} |
51 | |#include <catacomb/mpw.h>| \\ |
52 | |size_t MPWS(size_t |$n$|);| |
53 | \end{listinglist} |
54 | |
55 | \fsec{Returns} |
56 | |
674cd11e |
57 | The number of bytes occupied by an array of $n$~\code{mpw}s (i.e., $n \cdot |
3471ebd1 |
58 | |sizeof(mpw)|$). |
59 | |
60 | \subsubsection{The \code{MPW_RQ} macro} |
61 | \label{fn:MPW-RQ} |
62 | |
63 | \fsec{Synopsis} |
64 | |
65 | \begin{listinglist} |
66 | |#include <catacomb/mpw.h>| \\ |
67 | |size_t MPW_RQ(size_t |$\sz$|);| |
68 | \end{listinglist} |
69 | |
70 | \fsec{Returns} |
71 | |
72 | The number of \code{mpw}s required to represent a multiprecision integer |
674cd11e |
73 | occupying $\sz$~octets in an external representation. |
3471ebd1 |
74 | |
75 | |
76 | \subsection{Low-level multiprecision integer representation} |
77 | |
78 | The low-level multiprecision definitions are exported in the header file |
79 | \hdr{<catacomb/mpx.h>}. This header includes \hdr{<catacomb/mpw.h>}, so |
80 | there's usually no need to include it explicitly. |
81 | |
82 | A multiprecision integer is represented as an array of \code{mpw}s, |
83 | least-significant first. The array's bounds are described by a a pair of |
84 | pointers to the array's \emph{base} (i.e., its first element) and |
85 | \emph{limit} (i.e., the location immediately following its last element). |
86 | |
87 | Let $v$ be the base and $\vl$ the limit of a multiprecision integer array. |
674cd11e |
88 | The array itself is notated as~$v .. \vl$. The array's size in words may be |
3471ebd1 |
89 | computed as $\vl - v$ in the normal C fashion. The integer represented by |
90 | the array, denoted $\mp(v .. \vl)$, is defined to be |
91 | \[ |
92 | \mp(v .. \vl) = |
93 | \sum_{0 \le i < \vl - v} |
94 | 2^{\code{MPW_BITS} \cdot i} v[i] |
95 | \] |
96 | If the array is empty (i.e., $v = \vl$) then the number is zero. If the |
97 | array is empty, or the final word is nonzero, then the representation is said |
98 | to be \emph{shrunken}. Shrunken representations are more efficient, since |
99 | the arithmetic algorithms don't need to consider high-order words which make |
100 | no difference to the final result anyway. |
101 | |
102 | Whenever a result is too large to be represented in the memory allocated for |
674cd11e |
103 | it, high-order bits are discarded. Thus, a result written to an array of |
104 | $k$~words is reduced modulo $2^{\code{MPW_BITS} \cdot k}$. |
3471ebd1 |
105 | |
106 | |
107 | \subsection{Low-level macros} |
108 | \label{sec:mpx-macro} |
109 | |
110 | The following macros perform various simple operations useful for |
111 | manipulating multiprecision integers at the MPX level. |
112 | |
113 | \subsubsection{The \code{MPX_SHRINK} macro} |
114 | \label{fn:MPX-SHRINK} |
115 | |
116 | \fsec{Synopsis} |
117 | |
118 | \begin{listinglist} |
119 | |#include <catacomb/mpx.h>| \\ |
120 | |MPX_SHRINK(const mpw *|$v$|, const mpw *|$\vl$|);| |
121 | \end{listinglist} |
122 | |
123 | \fsec{Description} |
124 | |
674cd11e |
125 | The \code{MPX_SHRINK} macro reduces the limit~$\vl$ of a multiprecision |
126 | integer array so that either $v = \vl$ or~$\vl[-1] \ne 0$. The argument~$\vl$ must be an lvalue, since the macro writes the result back when it |
3471ebd1 |
127 | finishes. |
128 | |
129 | \subsubsection{The \code{MPX_BITS} macro} |
130 | \label{fn:MPX-BITS} |
131 | |
132 | \fsec{Synopsis} |
133 | |
134 | \begin{listinglist} |
135 | |#include <catacomb/mpx.h>| \\ |
136 | |MPX_BITS(unsigned long |$b$|, const mpw *|$v$|, const mpw *|$\vl$|);| |
137 | \end{listinglist} |
138 | |
139 | \fsec{Description} |
140 | |
141 | Determines the smallest number of bits which could represent the number |
674cd11e |
142 | $\mp(v .. \vl)$, and writes the answer to~$b$, which must therefore be an |
3471ebd1 |
143 | lvalue. The result is zero if the number is zero; otherwise $b$ is the |
144 | largest integer such that |
145 | \[ \mp(v .. \vl) \ge 2^{(b - 1) \bmod \code{MPW_BITS}}.\] |
146 | |
147 | \subsubsection{The \code{MPX_OCTETS} macro} |
148 | \label{fn:MPX-OCTETS} |
149 | |
150 | \fsec{Synopsis} |
151 | |
152 | \begin{listinglist} |
153 | |#include <catacomb/mpx.h>| \\ |
154 | |MPX_OCTETS(size_t |$o$|,| |
155 | |const mpw *|$v$|, const mpw *|$\vl$|);| |
156 | \end{listinglist} |
157 | |
158 | \fsec{Description} |
159 | |
160 | Determines the smallest number of octets which could represent the number |
674cd11e |
161 | $\mp(v .. \vl)$, and writes the answer to~$o$, which must therefore be an |
3471ebd1 |
162 | lvalue. This is useful for determining appropriate buffer sizes for the |
163 | results of \code{mpx_storel} and \code{mpx_storeb}. |
164 | |
674cd11e |
165 | The result $o$ can be calculated from the number of bits~$b$ reported by |
3471ebd1 |
166 | \code{MPX_BITS} as $o = \lceil b / 8 \rceil$; the algorithm used by |
167 | \code{MPX_OCTETS} is more efficient than this, however. |
168 | |
169 | \subsubsection{The \code{MPX_COPY} macro} |
170 | \label{fn:MPX-COPY} |
171 | |
172 | \fsec{Synopsis} |
173 | |
174 | \begin{listinglist} |
175 | |#include <catacomb/mpx.h>| \\ |
176 | |MPX_COPY(mpw *|$\dv$|, mpw *|$\dvl$|,| |
177 | |const mpw *|$\av$|, const mpw *|$\avl$|);| |
178 | \end{listinglist} |
179 | |
180 | \fsec{Description} |
181 | |
182 | Copies a multiprecision integer from the source array $\av .. \avl$ to the |
183 | destination array $\dv .. \dvl$. If the destination array is large enough, |
184 | the result is equal to the source; otherwise, high-order bits are discarded |
185 | as usual. |
186 | |
187 | \subsubsection{The \code{MPX_ZERO} macro} |
188 | \label{fn:MPX-ZERO} |
189 | |
190 | \fsec{Synopsis} |
191 | |
192 | \begin{listinglist} |
193 | |#include <catacomb/mpx.h>| \\ |
194 | |MPX_ZERO(mpw *|$v$|, mpw *|$\vl$|);| |
195 | \end{listinglist} |
196 | |
197 | \fsec{Description} |
198 | |
199 | Sets the integer $\mp(v .. \vl)$ to zero. |
200 | |
201 | |
202 | \subsection{Transfer formats: loading and storing} |
203 | \label{sec:mpx-io} |
204 | |
205 | The MPX layer can translate between internal representations of integers as |
206 | arrays of \code{mpw}s and external formats where integers are stored as |
207 | arrays of octets. Both little- and big-endian orders are supported. |
208 | |
209 | If $a_0, a_1, \ldots, a_{k - 1}$ is an array of $k$ octets, with |
210 | $0 \le a_i < 256$ for all $0 \le i < k$, then the number $n$ represented by |
211 | $a$ in little-endian byte order is |
212 | \[ n = \sum_{0 \le i < k} 256^i a_i .\] |
213 | Similarly, the number $n'$ represented by $a$ in big-endian byte order is |
214 | \[ n' = \sum_{0 \le i < k} 256^{k - i - 1} a_i .\] |
215 | |
216 | If, in a store operation, the destination octet array is not large enough to |
217 | represent the number to be stored, high-order octets are discarded; hence, |
218 | the number is reduced modulo $2^{8k}$, where $k$ is the size of the |
219 | destination array in octets. |
220 | |
221 | Two useful macros help when working out how much memory is needed for |
222 | translation between internal and transfer formats for multiprecision |
223 | integers. The macro \code{MPX_OCTETS} (page~\pageref{fn:MPX-OCTETS}) |
224 | calculates the smallest octet array size which can represent a multiprecision |
225 | integer. The macro \code{MPW_RQ} (page~\pageref{fn:MPW-RQ}) calculates the |
226 | smallest \code{mpw} array which can represent a multiprecision integer held |
227 | in an octet array of a particular size. |
228 | |
229 | \subsubsection{The \code{mpx_storel} function} |
230 | \label{fn:mpx-storel} |
231 | |
232 | \fsec{Synopsis} |
233 | |
234 | \begin{listinglist} |
235 | |#include <catacomb/mpx.h>| \\ |
236 | |void mpx_storel(const mpw *|$v$|, const mpw *|$\vl$|,| |
237 | |void *|$p$|, size_t |$\sz$|);| |
238 | \end{listinglist} |
239 | |
240 | \fsec{Description} |
241 | |
674cd11e |
242 | Stores the number held in the array $v .. \vl$ to the array of $\sz$~octets |
243 | starting at address~$p$ in little-endian byte order (i.e., least significant |
3471ebd1 |
244 | byte first). |
245 | |
246 | \subsubsection{The \code{mpx_loadl} function} |
247 | \label{fn:mpx-loadl} |
248 | |
249 | \fsec{Synopsis} |
250 | |
251 | \begin{listinglist} |
252 | |#include <catacomb/mpx.h>| \\ |
253 | |void mpx_loadl(mpw *|$v$|, mpw *|$\vl$|,| |
254 | |const void *|$p$|, size_t |$\sz$|);| |
255 | \end{listinglist} |
256 | |
257 | \fsec{Description} |
258 | |
674cd11e |
259 | Loads into the array $v .. \vl$ the number represented in the array of |
260 | $\sz$~octets starting at address~$p$ in little-endian byte order (i.e., least |
3471ebd1 |
261 | significant byte first). |
262 | |
263 | \subsubsection{The \code{mpx_storeb} function} |
264 | \label{fn:mpx-storeb} |
265 | |
266 | \fsec{Synopsis} |
267 | |
268 | \begin{listinglist} |
269 | |#include <catacomb/mpx.h>| \\ |
270 | |void mpx_storeb(const mpw *|$v$|, const mpw *|$\vl$|,| |
271 | |void *|$p$|, size_t |$\sz$|);| |
272 | \end{listinglist} |
273 | |
274 | \fsec{Description} |
275 | |
674cd11e |
276 | Stores the number held in the array $v .. \vl$ to the array of $\sz$~octets |
277 | starting at address~$p$ in big-endian byte order (i.e., least significant |
3471ebd1 |
278 | byte last). |
279 | |
280 | \subsubsection{The \code{mpx_loadb} function} |
281 | \label{fn:mpx-loadb} |
282 | |
283 | \fsec{Synopsis} |
284 | |
285 | \begin{listinglist} |
286 | |#include <catacomb/mpx.h>| \\ |
287 | |void mpx_loadb(mpw *|$v$|, mpw *|$\vl$|,| |
288 | |const void *|$p$|, size_t |$\sz$|);| |
289 | \end{listinglist} |
290 | |
291 | \fsec{Description} |
292 | |
674cd11e |
293 | Loads into the array $v .. \vl$ the number represented in the array of |
294 | $\sz$~octets starting at address $p$ in big-endian byte order (i.e., least |
3471ebd1 |
295 | significant byte last). |
296 | |
297 | |
298 | \subsection{Bit shifting operations} |
299 | \label{sec:mpx-shift} |
300 | |
301 | The MPX layer provides functions for efficient multiplication and division of |
302 | multiprecision integers by powers of two, performed simply by shifting the |
303 | binary representation left or right by a number of bits. Shifts by one bit |
304 | and by a multiple of \code{MPW_BITS} are particularly fast. |
305 | |
306 | There are two shift functions, one for left shifts (multiplications) and one |
307 | for right shifts (divisions). Each function is passed an array containing |
308 | the number to be shifted, a destination array for the result (which may be |
309 | the source array), and the number of bits to be shifted as an unsigned |
310 | integer. |
311 | |
312 | |
313 | \subsubsection{The \code{mpx_lsl} function} |
314 | \label{fn:mpx-lsl} |
315 | |
316 | \fsec{Synopsis} |
317 | |
318 | \begin{listinglist} |
319 | \begin{tabbing} |
320 | |#include <catacomb/mpx.h>| \\ |
321 | |void mpx_lsl(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
322 | \>|const mpw *|$\av$|, const mpw *|$\avl$|, size_t |$n$|);| |
323 | \end{tabbing} |
324 | \end{listinglist} |
325 | |
326 | \fsec{Description} |
327 | |
674cd11e |
328 | Stores in $\dv .. \dvl$ the result of shifting $\mp(\av .. \avl)$ left by |
329 | $n$~bits (i.e., multiplying it by~$2^n$). |
3471ebd1 |
330 | |
331 | \subsubsection{The \code{mpx_lsr} function} |
332 | \label{fn:mpx-lsr} |
333 | |
334 | \fsec{Synopsis} |
335 | |
336 | \begin{listinglist} |
337 | \begin{tabbing} |
338 | |#include <catacomb/mpx.h>| \\ |
339 | |void mpx_lsr(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
340 | \>|const mpw *|$\av$|, const mpw *|$\avl$|, size_t |$n$|);| |
341 | \end{tabbing} |
342 | \end{listinglist} |
343 | |
344 | \fsec{Description} |
345 | |
346 | Stores in $\dv .. \dvl$ the result of shifting $\mp(\av .. \avl)$ right by |
674cd11e |
347 | $n$~bits (i.e., dividing it by~$2^n$, rounding towards zero). |
3471ebd1 |
348 | |
349 | |
674cd11e |
350 | \subsection{Low-level arithmetic} |
3471ebd1 |
351 | |
352 | The remaining functions perform standard arithmetic operations on large |
353 | integers. The form for the arguments is fairly well-standardized: |
354 | destination arrays are given first, followed by the source arrays in the |
355 | conventional order. (This ordering reflects the usual order in a C |
356 | assignment expression, the \code{strcpy} and \code{memcpy} functions, and the |
357 | order of operands in many assembly languages.) |
358 | |
359 | Some functions allow the destination array to be the same as one (or both) |
360 | source arrays; others forbid this. Under no circumstances may the |
361 | destination partially overlap the sources. |
362 | |
363 | |
364 | \subsubsection{The \code{mpx_2c} function} |
365 | \label{fn:mpx-2c} |
366 | |
367 | \fsec{Synopsis} |
368 | |
369 | \begin{listinglist} |
370 | |#include <catacomb/mpx.h>| \\ |
371 | |void mpx_2c(mpw *|$\dv$|, mpw *|$\dvl$|,| |
372 | |const mpw *|$v$|, const mpw *|$\vl$|);| |
373 | \end{listinglist} |
374 | |
375 | \fsec{Description} |
376 | |
377 | Computes the two's complement of the number $\mp(v .. \vl)$ and stores it in |
378 | $\dv .. \dvl$. The two arrays $v .. \vl$ and $\dv .. \dvl$ may be the same. |
379 | |
380 | \subsubsection{The \code{mpx_ucmp} function and \code{MPX_UCMP} macro} |
381 | \label{fn:mpx-ucmp} |
382 | |
383 | \fsec{Synopsis} |
384 | \begin{listinglist} |
385 | \begin{tabbing} |
386 | |#include <catacomb/mpx.h>| \\ |
387 | |int mpx_ucmp(|\=|const mpw *|$\av$|, const mpw *|$\avl$|,| \\ |
388 | \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| \\ |
389 | |int MPX_UCMP(|\=|const mpw *|$\av$|, const mpw *|$\avl$|, |\synt{rel-op}|,| |
390 | \\ \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| |
391 | \end{tabbing} |
392 | \end{listinglist} |
393 | |
394 | \fsec{Description} |
395 | |
396 | The function \code{mpx_ucmp} performs an unsigned comparison of two unsigned |
674cd11e |
397 | multiprecision integers $a$ and~$b$, passed in the arrays $\av .. \avl$ and |
3471ebd1 |
398 | $\bv .. \bvl$ respectively. |
399 | |
400 | The macro \code{MPX_UCMP} provides a slightly more readable interface for |
401 | comparing integers. The \synt{rel-op} may be any C relational operator |
402 | (e.g., |!=|, or |<=|). The macro tests whether |
403 | $a \mathrel{\synt{rel-op}} b$. |
404 | |
405 | \fsec{Returns} |
406 | |
407 | The function \code{mpx_ucmp} returns a value less then, equal to, or |
408 | greater than zero depending on whether $a$ is less than, equal to or greater |
674cd11e |
409 | than~$b$. |
3471ebd1 |
410 | |
411 | The macro \code{MPX_UCMP} returns a nonzero result if $a |
412 | \mathrel{\synt{rel-op}} b$ is true, and zero if false. |
413 | |
414 | \subsubsection{The \code{mpx_uadd} function} |
415 | \label{fn:mpx-uadd} |
416 | |
417 | \fsec{Synopsis} |
418 | |
419 | \begin{listinglist} |
420 | \begin{tabbing} |
421 | |#include <catacomb/mpx.h>| \\ |
422 | |void mpx_uadd(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| |
423 | |const mpw *|$\av$|, const mpw *|$\avl$|,| \\ |
424 | \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| |
425 | \end{tabbing} |
426 | \end{listinglist} |
427 | |
428 | \fsec{Description} |
429 | |
430 | Adds two multiprecision integers. The sum of the two arguments |
431 | $\mp(\av .. \avl) + \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$. The |
432 | destination array may be equal to either or both source arrays.\footnote{% |
433 | Adding a number to itself is a poor way of doubling. A call to |
434 | \code{mpx_lsl} (page~\pageref{fn:mpx-lsl}) is much more efficient.} % |
435 | |
436 | \subsubsection{The \code{mpx_uaddn} function and \code{MPX_UADDN} macro} |
437 | \label{fn:mpx-uaddn} |
438 | |
439 | \fsec{Synopsis} |
440 | |
441 | \begin{listinglist} |
442 | |#include <catacomb/mpx.h>| \\ |
443 | |void mpx_uaddn(mpw *|$\dv$|, mpw *|$\dvl$|, mpw |$n$|);| \\ |
444 | |void MPX_UADDN(mpw *|$\dv$|, mpw *|$\dvl$|, mpw |$n$|);| |
445 | \end{listinglist} |
446 | |
447 | \fsec{Description} |
448 | |
674cd11e |
449 | The function \code{mpx_uaddn} adds a small integer~$n$ (expressed as a single |
3471ebd1 |
450 | \code{mpw}) to the multiprecision integer held in $\dv .. \dvl$. |
451 | |
452 | The macro \code{MPX_UADDN} performs exactly the same operation, but uses |
453 | inline code rather than calling a function. |
454 | |
455 | \subsubsection{The \code{mpx_usub} function} |
456 | \label{fn:mpx-usub} |
457 | |
458 | \fsec{Synopsis} |
459 | |
460 | \begin{listinglist} |
461 | \begin{tabbing} |
462 | |#include <catacomb/mpx.h>| \\ |
463 | |void mpx_usub(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| |
464 | |const mpw *|$\av$|, const mpw *|$\avl$|,| \\ |
465 | \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| |
466 | \end{tabbing} |
467 | \end{listinglist} |
468 | |
469 | \fsec{Description} |
470 | |
471 | Subtracts one multiprecision integer from another. The difference of the two |
472 | arguments $\mp(\av .. \avl) - \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$. |
473 | The destination array may be equal to either or both source |
474 | arrays.\footnote{% |
475 | Subtracting a number from itself is a particularly poor way of clearing an |
476 | integer to zero. A call to \code{MPX_ZERO} (page~\pageref{fn:MPX-ZERO}) is |
477 | much more efficient.} % |
478 | |
479 | Because overly large results are truncated to fit the destination array, if |
480 | the second argument is larger than the first, a two's-complement result is |
481 | obtained. |
482 | |
483 | \subsubsection{The \code{mpx_usubn} function and \code{MPX_USUBN} macro} |
484 | \label{fn:mpx-usubn} |
485 | |
486 | \fsec{Synopsis} |
487 | |
488 | \begin{listinglist} |
489 | |#include <catacomb/mpx.h>| \\ |
490 | |void mpx_usubn(mpw *|$\dv$|, mpw *|$\dvl$|, mpw |$n$|);| \\ |
491 | |void MPX_USUBN(mpw *|$\dv$|, mpw *|$\dvl$|, mpw |$n$|);| |
492 | \end{listinglist} |
493 | |
494 | \fsec{Description} |
495 | |
674cd11e |
496 | The function \code{mpx_usubn} subtracts a small integer~$n$ (expressed as a |
3471ebd1 |
497 | single \code{mpw}) from the multiprecision integer held in $\dv .. \dvl$. |
498 | |
499 | The macro \code{MPX_USUBN} performs exactly the same operation, but uses |
500 | inline code rather than calling a function. |
501 | |
502 | \subsubsection{The \code{mpx_umul} function} |
503 | \label{fn:mpx-umul} |
504 | |
505 | \fsec{Synopsis} |
506 | |
507 | \begin{listinglist} |
508 | \begin{tabbing} |
509 | |#include <catacomb/mpx.h>| \\ |
510 | |void mpx_umul(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| |
511 | |const mpw *|$\av$|, const mpw *|$\avl$|,| \\ |
512 | \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| |
513 | \end{tabbing} |
514 | \end{listinglist} |
515 | |
516 | \fsec{Description} |
517 | |
518 | Multiplies two multiprecision integers. The product of the two arguments |
519 | $\mp(\av .. \avl) \times \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$. The |
520 | destination array may not be equal to either source array. |
521 | |
522 | \subsubsection{The \code{mpx_umuln} function and \code{MPX_UMULN} macro} |
523 | \label{fn:mpx-umuln} |
524 | |
525 | \fsec{Synopsis} |
526 | |
527 | \begin{listinglist} |
528 | \begin{tabbing} |
529 | |#include <catacomb/mpx.h>| \\ |
530 | |void mpx_umuln(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
531 | \> |const mpw *|$\av$|, const mpw *|$\avl$|, mpw |$n$|);| \\ |
532 | |void MPX_UMULN(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
533 | \> |const mpw *|$\av$|, const mpw *|$\avl$|, mpw |$n$|);| |
534 | \end{tabbing} |
535 | \end{listinglist} |
536 | |
537 | \fsec{Description} |
538 | |
539 | The function \code{mpx_umuln} multiplies the multiprecision integer passed in |
674cd11e |
540 | $\av .. \avl$ by a small integer~$n$ (expressed as a single \code{mpw}), |
3471ebd1 |
541 | writing the product $n \cdot \mp(\av .. \avl)$ to the destination array $\dv |
542 | .. \dvl$. The destination array may be equal to the source array $\av |
543 | .. \avl$. |
544 | |
545 | The macro \code{MPX_UMULN} performs exactly the same operation, but uses |
546 | inline code rather than calling a function. |
547 | |
548 | \subsubsection{The \code{mpx_umlan} function and \code{MPX_UMLAN} macro} |
549 | \label{fn:mpx-umlan} |
550 | |
551 | \fsec{Synopsis} |
552 | |
553 | \begin{listinglist} |
554 | \begin{tabbing} |
555 | |#include <catacomb/mpx.h>| \\* |
556 | |void mpx_umlan(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\* |
557 | \> |const mpw *|$\av$|, const mpw *|$\avl$|, mpw |$n$|);| \\ |
558 | |void MPX_UMLAN(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
559 | \> |const mpw *|$\av$|, const mpw *|$\avl$|, mpw |$n$|);| |
560 | \end{tabbing} |
561 | \end{listinglist} |
562 | |
563 | \fsec{Description} |
564 | |
565 | The function \code{mpx_umlan} multiplies the multiprecision integer passed in |
674cd11e |
566 | $\av .. \avl$ by a small integer~$n$ (expressed as a single \code{mpw}), and |
3471ebd1 |
567 | adds it to the value already stored in the destination array $\dv .. \dvl$. |
568 | The destination array may be equal to the source array $\av .. \avl$, |
569 | although this isn't very useful. |
570 | |
571 | The macro \code{MPX_UMLAN} performs exactly the same operation, but uses |
572 | inline code rather than calling a function. |
573 | |
574 | \subsubsection{The \code{mpx_usqr} function} |
575 | \label{fn:mpx-usqr} |
576 | |
577 | \fsec{Synopsis} |
578 | |
579 | \begin{listinglist} |
580 | |#include <catacomb/mpx.h>| \\ |
581 | |void mpx_usqr(mpw *|$\dv$|, mpw *|$\dvl$|,| |
582 | |const mpw *|$\av$|, const mpw *|$\avl$|);| |
583 | \end{listinglist} |
584 | |
585 | \fsec{Description} |
586 | |
587 | Squares a multiprecision integer. The result $\mp(\av .. \avl)^2$ is stored |
588 | in $\dv .. \dvl$. The destination array may not be equal to the source |
589 | array. |
590 | |
591 | Squaring a number is approximately twice as fast as multiplying a number by |
592 | itself. |
593 | |
594 | \subsubsection{The \code{mpx_udiv} function} |
595 | \label{fn:mpx-udiv} |
596 | |
597 | \fsec{Synopsis} |
598 | |
599 | \begin{listinglist} |
600 | \begin{tabbing} |
601 | |#include <catacomb/mpx.h>| \\ |
602 | |void mpx_udiv(|\=|mpw *|$\qv$|, mpw *|$\qvl$|, mpw *|$\rv$|, mpw *|$\rvl$|,| |
603 | \\ \>|const mpw *|$\dv$|, const mpw *|$\dvl$|,| |
604 | |mpw *|$\mathit{sv}$|, mpw *|$\mathit{svl}$|);| |
605 | \end{tabbing} |
606 | \end{listinglist} |
607 | |
608 | \fsec{Description} |
609 | |
610 | Calculates the quotient and remainder when one multiprecision integer is |
611 | divided by another. |
612 | |
613 | The calling convention is slightly strange. The dividend and divisor are |
614 | passed in the arrays $\rv .. \rvl$ and $\dv .. \dvl$ respectively. The |
615 | quotient is written to the array $\qv .. \qvl$; the remainder is left in $\rv |
616 | .. \rvl$. |
617 | |
618 | The division function requires some workspace. The `scratch' array |
619 | $\mathit{sv} .. \mathit{svl}$ must be at least one word longer than the |
620 | divisor array $\dv .. \dvl$. The scratch array'sfinal contents are not |
621 | useful. Also, the remainder array $\rv .. \rvl$ must have at least two |
622 | words' headroom. |
623 | |
624 | \unverb\| |
625 | Given a dividend $x$ and a divisor $y$, the function calculates a quotient |
626 | $q$ and remainder $r$ such that $q = \lfloor x / y \rfloor$ and $x = qy + r$. |
627 | In particular, this definition implies that $r$ has the same sign as $y$, |
628 | which is a useful property when performing modular reductions. |
629 | \shortverb\| |
630 | |
631 | %%% Local Variables: |
632 | %%% mode: latex |
633 | %%% TeX-master: "catacomb" |
634 | %%% End: |