Thread: BUG #5428: Discrepency in remainder on mod function.
The following bug has been logged online:
Bug reference: 5428
Logged by: Khee Chin
Email address: kheechin@gmail.com
PostgreSQL version: HEAD
Operating system: Debian
Description: Discrepency in remainder on mod function.
Details:
I'm not certain if this is a bug or an intended behavior.
I noticed a discrepency in calculating the remainders across pgsql (PG),
wolframalpha (W) and using Knuth's description of floored division
for the function a mod n,
--
where a (-4), n (-3),
P - -1
W - -1
K - -1
where a (-4), n (+3),
P - -1
W - +2
K - +2
where a (+4), n (-3),
P - +1
W - -2
K - -2
where a (+4), n (+3),
P - 1
W - 1
K - 1
Tracing the discrepency when either the dividend or divisor is negative, I
took a look at src/backend/utils/adt/ numeric.c , int8.c and int.c and made
the changes to the mod functions for int2/int4/int8/numeric to use Knuth's
description for floored divisions where the remainder will have the same
sign as the divisor. Attached is a proposed fix.
diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c
index 43508b7..7c87a3a 100644
--- a/src/backend/utils/adt/int.c
+++ b/src/backend/utils/adt/int.c
@@ -1084,7 +1084,13 @@ int4mod(PG_FUNCTION_ARGS)
/* No overflow is possible */
- PG_RETURN_INT32(arg1 % arg2);
+ /*
+ * Traditional arg1 % arg2 produces incorrect results in cases
where
+ * either arg1 or arg2 is negative. This uses Knuth's description
of floored
+ * division.
+ * a mod n = a - n * floor(a/n)
+ */
+ PG_RETURN_INT32(arg1 - arg2 * floor((double) arg1 / arg2));
}
Datum
@@ -1099,7 +1105,13 @@ int2mod(PG_FUNCTION_ARGS)
errmsg("division by zero")));
/* No overflow is possible */
- PG_RETURN_INT16(arg1 % arg2);
+ /*
+ * Traditional arg1 % arg2 produces incorrect results in cases
where
+ * either arg1 or arg2 is negative. This uses Knuth's description
of floored
+ * division.
+ * a mod n = a - n * floor(a/n)
+ */
+ PG_RETURN_INT16(arg1 - arg2 * floor((double) arg1 / arg2));
}
diff --git a/src/backend/utils/adt/int8.c b/src/backend/utils/adt/int8.c
index 3245181..5d1b36d 100644
--- a/src/backend/utils/adt/int8.c
+++ b/src/backend/utils/adt/int8.c
@@ -644,7 +644,13 @@ int8mod(PG_FUNCTION_ARGS)
errmsg("division by zero")));
/* No overflow is possible */
- PG_RETURN_INT64(arg1 % arg2);
+ /*
+ * Traditional arg1 % arg2 produces incorrect results in cases
where
+ * either arg1 or arg2 is negative. This uses Knuth's description
of floored
+ * division.
+ * a mod n = a - n * floor(a/n)
+ */
+ PG_RETURN_INT64(arg1 - arg2 * floor((double) arg1 / arg2));
}
diff --git a/src/backend/utils/adt/numeric.c
b/src/backend/utils/adt/numeric.c
index 5766a8b..9fd31c2 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -4876,17 +4876,20 @@ mod_var(NumericVar *var1, NumericVar *var2,
NumericVar *result)
init_var(&tmp);
- /* ---------
- * We do this using the equation
- * mod(x,y) = x - trunc(x/y)*y
- * div_var can be persuaded to give us trunc(x/y) directly.
- * ----------
- */
- div_var(var1, var2, &tmp, 0, false);
+ /*
+ * Traditional arg1 % arg2 produces incorrect results in cases
where
+ * either arg1 or arg2 is negative. This uses Knuth's description of
floored
+ * division.
+ * a mod n = a - n * floor(a/n)
+ */
+
+ div_var(var1, var2, &tmp, NUMERIC_MAX_DISPLAY_SCALE, true);
+
+ floor_var(&tmp,&tmp);
- mul_var(var2, &tmp, &tmp, var2->dscale);
+ mul_var(var2, &tmp, &tmp, var2->dscale);
- sub_var(var1, &tmp, result);
+ sub_var(var1, &tmp, result);
free_var(&tmp);
}
"Khee Chin" <kheechin@gmail.com> writes:
> I'm not certain if this is a bug or an intended behavior.
> I noticed a discrepency in calculating the remainders across pgsql (PG),
> wolframalpha (W) and using Knuth's description of floored division
We follow whatever the C compiler's idea of modulo is. This is somewhat
standardized, in fact, and I'm not excited about changing it.
Especially not by introducing roundoff-prone double arithmetic into what
had been an exact operation.
regards, tom lane
On Sat, Apr 17, 2010 at 5:11 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> "Khee Chin" <kheechin@gmail.com> writes:
>> I'm not certain if this is a bug or an intended behavior.
>
>> I noticed a discrepency in calculating the remainders across pgsql (PG),
>> wolframalpha (W) and using Knuth's description of floored division
>
> We follow whatever the C compiler's idea of modulo is. =C2=A0This is some=
what
> standardized, in fact, and I'm not excited about changing it.
> Especially not by introducing roundoff-prone double arithmetic into what
> had been an exact operation.
>
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0regards, tom lane
>
Hi Tom,
Thks for the reply. I understand your first point on following the C
compiler's idea of modulo is.
For archiving purposes, to address your second concern, I have
replaced the double arithmetic operation with this equation to address
the modulo in int2/4/8
a mod n =3D ((a % n) + n) % n
Regards,
Khee Chin.
diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c
index 43508b7..8b7ca05 100644
--- a/src/backend/utils/adt/int.c
+++ b/src/backend/utils/adt/int.c
@@ -1084,7 +1084,12 @@ int4mod(PG_FUNCTION_ARGS)
/* No overflow is possible */
- PG_RETURN_INT32(arg1 % arg2);
+ /*
+ * Traditional arg1 % arg2 in C produces incorrect results in
cases where
+ * either arg1 or arg2 is negative.
+ * a mod n =3D ((a % n) + n) % n
+ */
+ PG_RETURN_INT32(((arg1 % arg2) + arg2) % arg2);;
}
Datum
@@ -1099,7 +1104,12 @@ int2mod(PG_FUNCTION_ARGS)
errmsg("division by zero")));
/* No overflow is possible */
- PG_RETURN_INT16(arg1 % arg2);
+ /*
+ * Traditional arg1 % arg2 in C produces incorrect results in
cases where
+ * either arg1 or arg2 is negative.
+ * a mod n =3D ((a % n) + n) % n
+ */
+ PG_RETURN_INT16(((arg1 % arg2) + arg2) % arg2);
}
diff --git a/src/backend/utils/adt/int8.c b/src/backend/utils/adt/int8.c
index 3245181..57252da 100644
--- a/src/backend/utils/adt/int8.c
+++ b/src/backend/utils/adt/int8.c
@@ -644,7 +644,12 @@ int8mod(PG_FUNCTION_ARGS)
errmsg("division by zero")));
/* No overflow is possible */
- PG_RETURN_INT64(arg1 % arg2);
+ /*
+ * Traditional arg1 % arg2 in C produces incorrect results in
cases where
+ * either arg1 or arg2 is negative.
+ * a mod n =3D ((a % n) + n) % n
+ */
+ PG_RETURN_INT64(((arg1 % arg2) + arg2) % arg2);;
}
diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeri=
c.c
index 5766a8b..a9b86df 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -4876,17 +4876,20 @@ mod_var(NumericVar *var1, NumericVar *var2,
NumericVar *result)
init_var(&tmp);
- /* ---------
- * We do this using the equation
- * mod(x,y) =3D x - trunc(x/y)*y
- * div_var can be persuaded to give us trunc(x/y) directly.
- * ----------
- */
- div_var(var1, var2, &tmp, 0, false);
+ /*
+ * Traditional arg1 % arg2 in C produces incorrect results in
cases where
+ * either arg1 or arg2 is negative. This uses Knuth's
description of floored
+ * division.
+ * a mod n =3D a - n * floor(a/n)
+ */
+
+ div_var(var1, var2, &tmp, NUMERIC_MAX_DISPLAY_SCALE, true);
+
+ floor_var(&tmp,&tmp);
- mul_var(var2, &tmp, &tmp, var2->dscale);
+ mul_var(var2, &tmp, &tmp, var2->dscale);
- sub_var(var1, &tmp, result);
+ sub_var(var1, &tmp, result);
free_var(&tmp);
}