chiark / gitweb /
More changes. Still embryonic.
[catacomb] / manual / mp-mpx.tex
CommitLineData
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
9The header file \hdr{<catacomb/mpw.h>} defines two types, \code{mpw} and
10\code{mpd}, and a collection of macros describing them.
11
12The `multiprecision word' type, \code{mpw}, is an unsigned integer type whose
13representation uses \code{MPW_BITS}. The largest value representable in an
14\code{mpw} is $\code{MPW_MAX} = 2^{\code{MPW_BITS}} - 1$.
15The value of \code{MPW_BITS} is at least 16. Note that, on some
16architectures, an \code{mpw} may be capable of representing values larger
17than \code{MPW_MAX}. The expression \code{MPW($x$)} returns the value of $x
18\bmod \code{MPW_MAX}$ cast to type \code{mpw}.
19
20The `multiprecision doubleword' type, \code{mpd}, is an unsigned integer type
21with at least double the width of \code{mpw}. Hence, an \code{mpd} is
22capable of representing the product of two \code{mpw}s, and is useful when
23performing multiplications and divisions. The constants \code{MPD_BITS} and
24\code{MPD_MAX} are defined to be the number of bits used in the
25representation of an \code{mpd} and the largest value representable in an
26\code{mpd} respectively.
27
28A 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
42The value of $x \bmod 2^{\code{MPW_BITS}}$, as an \code{mpw}. This is a
43frequently 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 57The 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
72The number of \code{mpw}s required to represent a multiprecision integer
674cd11e 73occupying $\sz$~octets in an external representation.
3471ebd1 74
75
76\subsection{Low-level multiprecision integer representation}
77
78The low-level multiprecision definitions are exported in the header file
79\hdr{<catacomb/mpx.h>}. This header includes \hdr{<catacomb/mpw.h>}, so
80there's usually no need to include it explicitly.
81
82A multiprecision integer is represented as an array of \code{mpw}s,
83least-significant first. The array's bounds are described by a a pair of
84pointers 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
87Let $v$ be the base and $\vl$ the limit of a multiprecision integer array.
674cd11e 88The array itself is notated as~$v .. \vl$. The array's size in words may be
3471ebd1 89computed as $\vl - v$ in the normal C fashion. The integer represented by
90the 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\]
96If the array is empty (i.e., $v = \vl$) then the number is zero. If the
97array is empty, or the final word is nonzero, then the representation is said
98to be \emph{shrunken}. Shrunken representations are more efficient, since
99the arithmetic algorithms don't need to consider high-order words which make
100no difference to the final result anyway.
101
102Whenever a result is too large to be represented in the memory allocated for
674cd11e 103it, 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
110The following macros perform various simple operations useful for
111manipulating 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 125The \code{MPX_SHRINK} macro reduces the limit~$\vl$ of a multiprecision
126integer 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 127finishes.
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
141Determines 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 143lvalue. The result is zero if the number is zero; otherwise $b$ is the
144largest 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
160Determines 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 162lvalue. This is useful for determining appropriate buffer sizes for the
163results of \code{mpx_storel} and \code{mpx_storeb}.
164
674cd11e 165The 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
182Copies a multiprecision integer from the source array $\av .. \avl$ to the
183destination array $\dv .. \dvl$. If the destination array is large enough,
184the result is equal to the source; otherwise, high-order bits are discarded
185as 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
199Sets the integer $\mp(v .. \vl)$ to zero.
200
201
202\subsection{Transfer formats: loading and storing}
203\label{sec:mpx-io}
204
205The MPX layer can translate between internal representations of integers as
206arrays of \code{mpw}s and external formats where integers are stored as
207arrays of octets. Both little- and big-endian orders are supported.
208
209If $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 .\]
213Similarly, 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
216If, in a store operation, the destination octet array is not large enough to
217represent the number to be stored, high-order octets are discarded; hence,
218the number is reduced modulo $2^{8k}$, where $k$ is the size of the
219destination array in octets.
220
221Two useful macros help when working out how much memory is needed for
222translation between internal and transfer formats for multiprecision
223integers. The macro \code{MPX_OCTETS} (page~\pageref{fn:MPX-OCTETS})
224calculates the smallest octet array size which can represent a multiprecision
225integer. The macro \code{MPW_RQ} (page~\pageref{fn:MPW-RQ}) calculates the
226smallest \code{mpw} array which can represent a multiprecision integer held
227in 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 242Stores the number held in the array $v .. \vl$ to the array of $\sz$~octets
243starting at address~$p$ in little-endian byte order (i.e., least significant
3471ebd1 244byte 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 259Loads 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 261significant 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 276Stores the number held in the array $v .. \vl$ to the array of $\sz$~octets
277starting at address~$p$ in big-endian byte order (i.e., least significant
3471ebd1 278byte 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 293Loads 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 295significant byte last).
296
297
298\subsection{Bit shifting operations}
299\label{sec:mpx-shift}
300
301The MPX layer provides functions for efficient multiplication and division of
302multiprecision integers by powers of two, performed simply by shifting the
303binary representation left or right by a number of bits. Shifts by one bit
304and by a multiple of \code{MPW_BITS} are particularly fast.
305
306There are two shift functions, one for left shifts (multiplications) and one
307for right shifts (divisions). Each function is passed an array containing
308the number to be shifted, a destination array for the result (which may be
309the source array), and the number of bits to be shifted as an unsigned
310integer.
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 328Stores 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
346Stores 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
352The remaining functions perform standard arithmetic operations on large
353integers. The form for the arguments is fairly well-standardized:
354destination arrays are given first, followed by the source arrays in the
355conventional order. (This ordering reflects the usual order in a C
356assignment expression, the \code{strcpy} and \code{memcpy} functions, and the
357order of operands in many assembly languages.)
358
359Some functions allow the destination array to be the same as one (or both)
360source arrays; others forbid this. Under no circumstances may the
361destination 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
377Computes 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
396The function \code{mpx_ucmp} performs an unsigned comparison of two unsigned
674cd11e 397multiprecision integers $a$ and~$b$, passed in the arrays $\av .. \avl$ and
3471ebd1 398$\bv .. \bvl$ respectively.
399
400The macro \code{MPX_UCMP} provides a slightly more readable interface for
401comparing 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
407The function \code{mpx_ucmp} returns a value less then, equal to, or
408greater than zero depending on whether $a$ is less than, equal to or greater
674cd11e 409than~$b$.
3471ebd1 410
411The 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
430Adds two multiprecision integers. The sum of the two arguments
431$\mp(\av .. \avl) + \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$. The
432destination 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 449The 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
452The macro \code{MPX_UADDN} performs exactly the same operation, but uses
453inline 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
471Subtracts one multiprecision integer from another. The difference of the two
472arguments $\mp(\av .. \avl) - \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$.
473The destination array may be equal to either or both source
474arrays.\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
479Because overly large results are truncated to fit the destination array, if
480the second argument is larger than the first, a two's-complement result is
481obtained.
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 496The function \code{mpx_usubn} subtracts a small integer~$n$ (expressed as a
3471ebd1 497single \code{mpw}) from the multiprecision integer held in $\dv .. \dvl$.
498
499The macro \code{MPX_USUBN} performs exactly the same operation, but uses
500inline 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
518Multiplies two multiprecision integers. The product of the two arguments
519$\mp(\av .. \avl) \times \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$. The
520destination 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
539The 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 541writing 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
545The macro \code{MPX_UMULN} performs exactly the same operation, but uses
546inline 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
565The 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 567adds it to the value already stored in the destination array $\dv .. \dvl$.
568The destination array may be equal to the source array $\av .. \avl$,
569although this isn't very useful.
570
571The macro \code{MPX_UMLAN} performs exactly the same operation, but uses
572inline 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
587Squares a multiprecision integer. The result $\mp(\av .. \avl)^2$ is stored
588in $\dv .. \dvl$. The destination array may not be equal to the source
589array.
590
591Squaring a number is approximately twice as fast as multiplying a number by
592itself.
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
610Calculates the quotient and remainder when one multiprecision integer is
611divided by another.
612
613The calling convention is slightly strange. The dividend and divisor are
614passed in the arrays $\rv .. \rvl$ and $\dv .. \dvl$ respectively. The
615quotient is written to the array $\qv .. \qvl$; the remainder is left in $\rv
616.. \rvl$.
617
618The division function requires some workspace. The `scratch' array
619$\mathit{sv} .. \mathit{svl}$ must be at least one word longer than the
620divisor array $\dv .. \dvl$. The scratch array'sfinal contents are not
621useful. Also, the remainder array $\rv .. \rvl$ must have at least two
622words' headroom.
623
624\unverb\|
625Given 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$.
627In particular, this definition implies that $r$ has the same sign as $y$,
628which is a useful property when performing modular reductions.
629\shortverb\|
630
631%%% Local Variables:
632%%% mode: latex
633%%% TeX-master: "catacomb"
634%%% End: