f775f6b68e9589799d74deec2d41decb37dfc755
1 %%% -*-latex-*-
3 \section{Low-level details: MPX}
4 \label{sec:mpx}
7 \subsection{Data types for low-level arithmetic}
9 The header file \hdr{<catacomb/mpw.h>} defines two types, \code{mpw} and
10 \code{mpd}, and a collection of macros describing them.
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}.
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.
28 A few macros useful for manipulating \code{mpw}s are defined.
30 \subsubsection{The \code{MPW} macro}
31 \label{fn:MPW}
33 \fsec{Synopsis}
35 \begin{listinglist}
36 |#include <catacomb/mpw.h>| \\
37 |mpw MPW(|$x$|);|
38 \end{listinglist}
40 \fsec{Returns}
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)|.
45 \subsubsection{The \code{MPWS} macro}
46 \label{fn:MPWS}
48 \fsec{Synopsis}
50 \begin{listinglist}
51 |#include <catacomb/mpw.h>| \\
52 |size_t MPWS(size_t |$n$|);|
53 \end{listinglist}
55 \fsec{Returns}
57 The number of bytes occupied by an array of $n$ \code{mpw}s (i.e., $n \cdot 58 |sizeof(mpw)|$).
60 \subsubsection{The \code{MPW_RQ} macro}
61 \label{fn:MPW-RQ}
63 \fsec{Synopsis}
65 \begin{listinglist}
66 |#include <catacomb/mpw.h>| \\
67 |size_t MPW_RQ(size_t |$\sz$|);|
68 \end{listinglist}
70 \fsec{Returns}
72 The number of \code{mpw}s required to represent a multiprecision integer
73 occupying $\sz$ octets in an external representation.
76 \subsection{Low-level multiprecision integer representation}
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.
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).
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.
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}$.
107 \subsection{Low-level macros}
108 \label{sec:mpx-macro}
110 The following macros perform various simple operations useful for
111 manipulating multiprecision integers at the MPX level.
113 \subsubsection{The \code{MPX_SHRINK} macro}
114 \label{fn:MPX-SHRINK}
116 \fsec{Synopsis}
118 \begin{listinglist}
119 |#include <catacomb/mpx.h>| \\
120 |MPX_SHRINK(const mpw *|$v$|, const mpw *|$\vl$|);|
121 \end{listinglist}
123 \fsec{Description}
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.
130 \subsubsection{The \code{MPX_BITS} macro}
131 \label{fn:MPX-BITS}
133 \fsec{Synopsis}
135 \begin{listinglist}
136 |#include <catacomb/mpx.h>| \\
137 |MPX_BITS(unsigned long |$b$|, const mpw *|$v$|, const mpw *|$\vl$|);|
138 \end{listinglist}
140 \fsec{Description}
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}}.$
148 \subsubsection{The \code{MPX_OCTETS} macro}
149 \label{fn:MPX-OCTETS}
151 \fsec{Synopsis}
153 \begin{listinglist}
154 |#include <catacomb/mpx.h>| \\
155 |MPX_OCTETS(size_t |$o$|,|
156 |const mpw *|$v$|, const mpw *|$\vl$|);|
157 \end{listinglist}
159 \fsec{Description}
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}.
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.
170 \subsubsection{The \code{MPX_COPY} macro}
171 \label{fn:MPX-COPY}
173 \fsec{Synopsis}
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}
181 \fsec{Description}
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.
188 \subsubsection{The \code{MPX_ZERO} macro}
189 \label{fn:MPX-ZERO}
191 \fsec{Synopsis}
193 \begin{listinglist}
194 |#include <catacomb/mpx.h>| \\
195 |MPX_ZERO(mpw *|$v$|, mpw *|$\vl$|);|
196 \end{listinglist}
198 \fsec{Description}
200 Sets the integer $\mp(v .. \vl)$ to zero.
204 \label{sec:mpx-io}
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.
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 .$
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.
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.
230 \subsubsection{The \code{mpx_storel} function}
231 \label{fn:mpx-storel}
233 \fsec{Synopsis}
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}
241 \fsec{Description}
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).
250 \fsec{Synopsis}
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}
258 \fsec{Description}
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).
264 \subsubsection{The \code{mpx_storeb} function}
265 \label{fn:mpx-storeb}
267 \fsec{Synopsis}
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}
275 \fsec{Description}
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).
284 \fsec{Synopsis}
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}
292 \fsec{Description}
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).
299 \subsection{Bit shifting operations}
300 \label{sec:mpx-shift}
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.
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.
314 \subsubsection{The \code{mpx_lsl} function}
315 \label{fn:mpx-lsl}
317 \fsec{Synopsis}
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}
327 \fsec{Description}
329 Stores in $\dv .. \dvl$ the result of shifting $\mp(\av .. \avl)$ left by $n$
330 bits (i.e., multiplying it by $2^n$).
332 \subsubsection{The \code{mpx_lsr} function}
333 \label{fn:mpx-lsr}
335 \fsec{Synopsis}
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}
345 \fsec{Description}
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).
351 \subsection{Low level arithmetic}
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.)
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.
365 \subsubsection{The \code{mpx_2c} function}
366 \label{fn:mpx-2c}
368 \fsec{Synopsis}
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}
376 \fsec{Description}
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.
381 \subsubsection{The \code{mpx_ucmp} function and \code{MPX_UCMP} macro}
382 \label{fn:mpx-ucmp}
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}
395 \fsec{Description}
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.
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$.
406 \fsec{Returns}
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$.
412 The macro \code{MPX_UCMP} returns a nonzero result if $a 413 \mathrel{\synt{rel-op}} b$ is true, and zero if false.
418 \fsec{Synopsis}
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}
429 \fsec{Description}
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.} %
440 \fsec{Synopsis}
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}
448 \fsec{Description}
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$.
453 The macro \code{MPX_UADDN} performs exactly the same operation, but uses
454 inline code rather than calling a function.
456 \subsubsection{The \code{mpx_usub} function}
457 \label{fn:mpx-usub}
459 \fsec{Synopsis}
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}
470 \fsec{Description}
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.} %
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.
484 \subsubsection{The \code{mpx_usubn} function and \code{MPX_USUBN} macro}
485 \label{fn:mpx-usubn}
487 \fsec{Synopsis}
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}
495 \fsec{Description}
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$.
500 The macro \code{MPX_USUBN} performs exactly the same operation, but uses
501 inline code rather than calling a function.
503 \subsubsection{The \code{mpx_umul} function}
504 \label{fn:mpx-umul}
506 \fsec{Synopsis}
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}
517 \fsec{Description}
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.
523 \subsubsection{The \code{mpx_umuln} function and \code{MPX_UMULN} macro}
524 \label{fn:mpx-umuln}
526 \fsec{Synopsis}
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}
538 \fsec{Description}
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$.
546 The macro \code{MPX_UMULN} performs exactly the same operation, but uses
547 inline code rather than calling a function.
549 \subsubsection{The \code{mpx_umlan} function and \code{MPX_UMLAN} macro}
550 \label{fn:mpx-umlan}
552 \fsec{Synopsis}
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}
564 \fsec{Description}
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.
572 The macro \code{MPX_UMLAN} performs exactly the same operation, but uses
573 inline code rather than calling a function.
575 \subsubsection{The \code{mpx_usqr} function}
576 \label{fn:mpx-usqr}
578 \fsec{Synopsis}
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}
586 \fsec{Description}
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.
592 Squaring a number is approximately twice as fast as multiplying a number by
593 itself.
595 \subsubsection{The \code{mpx_udiv} function}
596 \label{fn:mpx-udiv}
598 \fsec{Synopsis}
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}
609 \fsec{Description}
611 Calculates the quotient and remainder when one multiprecision integer is
612 divided by another.
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$.
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
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$,