commit 0703ea9ea4155d59d1356713789c60f5e6e8c7a6
parent bfa14f9a8d313d69f14ffba45ea9b41abbd6d641
Author: Mattias Andrée <maandree@kth.se>
Date: Wed, 11 May 2016 18:22:11 +0200
Always satisfy n=qd+r to avoid confusion
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
7 files changed, 26 insertions(+), 53 deletions(-)
diff --git a/doc/arithmetic.tex b/doc/arithmetic.tex
@@ -4,7 +4,8 @@
In this chapter, we will learn how to perform basic
arithmetic with libzahl: addition, subtraction,
multiplication, division, modulus, exponentiation,
-and sign manipulation.
+and sign manipulation. \secref{sec:Division} is of
+special importance.
\vspace{1cm}
\minitoc
diff --git a/doc/refsheet.tex b/doc/refsheet.tex
@@ -47,18 +47,18 @@ Unless specified otherwise, returns are {\tt void} and all parameters are of typ
\entry{zadd(a, b, c)} {$a \gets b + c$} {}
\entry{zsub(a, b, c)} {$a \gets b - c$} {}
\entry{zmul(a, b, c)} {$a \gets b \cdot c$} {}
-\entry{zmodmul(a, b, c, d)} {$a \gets b \cdot c \mod d$} {$0 \le a < \ab{d}$}
+\entry{zmodmul(a, b, c, d)} {$a \gets b \cdot c \mod d$} {$0 \le a~\mbox{sgn}~bc < \ab{d}$}
\entry{zdiv(a, b, c)} {$a \gets b / c$} {rounded towards zero}
\entry{zdivmod(a, b, c, d)} {$a \gets c / d$} {rounded towards zero}
-\entry{zdivmod(a, b, c, d)} {$b \gets c \mod d$} {$0 \le b < \ab{d}$}
-\entry{zmod(a, b, c)} {$a \gets b \mod c$} {$0 \le a < \ab{c}$}
+\entry{zdivmod(a, b, c, d)} {$b \gets c \mod d$} {$0 \le b~\mbox{sgn}~c < \ab{d}$}
+\entry{zmod(a, b, c)} {$a \gets b \mod c$} {$0 \le a~\mbox{sgn}~b < \ab{c}$}
%\entry{zdiv\_exact(a, b, c)} {$a \gets b / c$} {assumes $c \vert d$}
\entry{zsqr(a, b)} {$a \gets b^2$} {}
\entry{zmodsqr(a, b, c)} {$a \gets b^2 \mod c$} {$0 \le a < \ab{c}$}
\entry{zsqr(a, b)} {$a \gets b^2$} {}
\entry{zpow(a, b, c)} {$a \gets b^c$} {}
\entry{zpowu(a, b, c)} {$a \gets b^c$} {{\tt c} is an \ullong{}}
-\entry{zmodpow(a, b, c, d)} {$a \gets b^c \mod d$} {$0 \le a < \ab{d}$}
+\entry{zmodpow(a, b, c, d)} {$a \gets b^c \mod d$} {$0 \le a~\mbox{sgn}~b^c < \ab{d}$}
\entry{zmodpowu(a, b, c, d)} {$a \gets b^c \mod d$} {ditto, {\tt c} is an \ullong{}}
\entry{zabs(a, b)} {$a \gets \ab{b}$} {}
\entry{zneg(a, b)} {$a \gets -b$} {}
diff --git a/man/zdivmod.3 b/man/zdivmod.3
@@ -30,34 +30,6 @@ gets
Mod
.IR divisor .
.P
-Be aware,
-.I remainder
-gets
-.RI | dividend |
-Mod
-.RI | divisor |,
-this means that it is only guaranteed to be true that
-.I dividend
-=
-.I quotient
-⋅
-.I divisor
-+
-.IR remainder
-if
-.I dividend
-and
-.I divisor
-are both non-negative.
-It is up to the user, to make the necessary adjustment to
-.I remainder
-to make this true or to satisfy any desired property. This
-exceptional behaviour has been choosen because it is the
-simplies, works just fine if you are working with natural
-numbers only, and there are two many ways to define
-modulus; this one is advantages when you want to make
-adjustments, it is straight-forward.
-.P
It is safe to call
.B zdivmod
with non-unique parameters,
diff --git a/man/zmod.3 b/man/zmod.3
@@ -24,22 +24,15 @@ Mod
.P
The result
.RI ( remainder )
-is always non-negative. To be more precise,
-a Mod b = |a| Mod |b| for all integers a
+is negative if and only if the
+.I dividend
+is negative. To be more precise,
+a Mod b = (|a| Mod |b|) sgn a for all integers a
and b.
.P
It is safe to call
.B zmod
with non-unique parameters.
-.SH RATIONALE
-There are many ways to define modulus with
-negative integers. You have to select how the
-signness is selected, and when to invert
-(in respect to modulated addition) the remainder.
-The simplest way to implement modulus is to
-ignore the sign of the operands. This solution
-also makes it very easy for those that which
-to write a wrapper that changes the definition.
.SH SEE ALSO
.BR zdivmod (3),
.BR zstr (3),
diff --git a/src/zdivmod.c b/src/zdivmod.c
@@ -67,9 +67,10 @@ done:
void
zdivmod(z_t a, z_t b, z_t c, z_t d)
{
- int sign, cmpmag;
+ int c_sign, sign, cmpmag;
- sign = zsignum(c) * zsignum(d);
+ c_sign = zsignum(c);
+ sign = c_sign * zsignum(d);
if (unlikely(!sign)) {
if (check(!zzero(c))) {
@@ -87,7 +88,6 @@ zdivmod(z_t a, z_t b, z_t c, z_t d)
SET_SIGNUM(b, 0);
} else {
SET(b, c);
- SET_SIGNUM(b, 1);
SET_SIGNUM(a, 0);
}
return;
@@ -95,4 +95,6 @@ zdivmod(z_t a, z_t b, z_t c, z_t d)
zdivmod_impl(a, b, c, d);
SET_SIGNUM(a, sign);
+ if (zsignum(b) > 0)
+ SET_SIGNUM(b, c_sign);
}
diff --git a/test-generate.py b/test-generate.py
@@ -1,11 +1,16 @@
#!/usr/bin/env python3
# See LICENSE file for copyright and license details.
-import random
+import sys, random
def mod(a, b):
- return abs(a) % abs(b)
+ r = (abs(a) % abs(b)) * (-1 if a < 0 else 1)
+ q = div(a, b)
+ if a != q * b + r:
+ print('zdivmod does not satisfly n = qd + r', file = sys.stderr)
+ sys.exit(1)
+ return r
def div(a, b): # Python's division is floored, not truncated.
r = abs(a) // abs(b)
diff --git a/test.c b/test.c
@@ -590,10 +590,10 @@ main(void)
zseti(a, -7);
zseti(b, 3);
zmod(c, a, b);
- assert(zcmpi(c, 1), == 0);
+ assert(zcmpi(c, -1), == 0);
zseti(b, -3);
zmod(c, a, b);
- assert(zcmpi(c, 1), == 0);
+ assert(zcmpi(c, -1), == 0);
zseti(a, 7);
zseti(b, 3);
@@ -608,11 +608,11 @@ main(void)
zseti(b, 3);
zdivmod(d, c, a, b);
assert(zcmpi(d, -2), == 0);
- assert(zcmpi(c, 1), == 0);
+ assert(zcmpi(c, -1), == 0);
zseti(b, -3);
zdivmod(d, c, a, b);
assert(zcmpi(d, 2), == 0);
- assert(zcmpi(c, 1), == 0);
+ assert(zcmpi(c, -1), == 0);
zseti(a, 10);
zseti(b, -1);
