| Subject: | integer division result off by one in some cases |
In integer arithmetic, a quotient and remainder pair should obey the
condition: quotient * denominator + remainder == numerator.
The Math::BigInt documentation states this fact and mentions in
particular, how integer quotients are rounded (towards minus infinity)
and how remainders are chosen (between zero and the denominator) out of
a residue class to match with this condition.
However, as of Math-BigInt-1.998, this is not correctly implemented.
Quotients seem to be rounded towards zero, which means that negative
division results are off by one if the remainder is not zero.
The test script I have attached fails in cases 2 and 3.
Curiously, in the bdiv paragraph of the CAVEATS section, the text
describes what should happen but the numerical examples are neither
consistent with the text nor the implementation:
1 / 4 => ( 0, 1) # correct
1 / -4 => (-1,-3) # correct but not as implemented
-3 / 4 => (-1, 1) # correct but not as implemented
-3 / -4 => ( 0,-3) # correct
-11 / 2 => (-5,1) # wrong but as implemented
11 /-2 => (-5,-1) # wrong but as implemented
The behaviour seems to be independent of the math library in use. I
checked with GMP, FastCalc and Calc.
To fix the problem, bdiv should be revised to round integer quotients
with floor rather than truncate semantics and -5 should be replaced by
-6 in the examples.
-Martin
| Subject: | div.t |
#!/usr/bin/perl
# check whether integer bdiv and bmuladd are complementary
# n should be equal to d * (n / d) + (n % d)
use strict;
use warnings;
use Test::More tests => 4;
use Math::BigInt;
sub check {
my ($n, $d) = map { Math::BigInt->new($_) } @_;
my ($q, $r) = $n->copy->bdiv($d);
my $n2 = $d * $q + $r;
is $n2, $n, sprintf q["%3s = %2s * %2s + %2s"], $n, $d, $q, $r;
}
check( 22, 5);
check( 22, -5);
check(-22, 5);
check(-22, -5);