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