[M3devel] integer division/mod questions?
Jay K
jay.krell at cornell.edu
Wed Jan 20 12:31:18 CET 2010
Actually I think the new mod/div functions are still a little
risky for negative div or mod negative.
They'd more reliable/predictable/portable if if they used unsigned
numbers.
The reason I started looking at this stuff is because I was
reading about gcc assuming signed overflow won't occur
and then making optimizations with that assumption.
You can ask it to warn when it does so.
I thought this might break the new but unused m3_add and
such. The warning triggered for the existing div (but not mod) functions.
So I set about rewriting them to use unsigned math, which
is the recommendation here -- because its overflow is
well defined by the C standard -- and then comparing
mine with the previous/current code..and noticed wrong behavior
in the previous/current.
- Jay
From: jay.krell at cornell.edu
To: hosking at cs.purdue.edu
Date: Wed, 20 Jan 2010 11:27:17 +0000
CC: m3devel at elegosoft.com
Subject: Re: [M3devel] integer division/mod questions?
No, not overflow examples.
LONG_MIN divided by any negative number was a negative number.
But I believe it should be positive.
I don't believe e.g. LONG_MIN DIV -2 is something involving overflow.
The result is representable.
LONG_MIN mod negative numbers also had the wrong sign.
You don't really have to view a diff.
I left the old functions m3_mod, m3_div, present, renamed
to m3_mod_old, m3_div_old.
So you can see both versions.
The new versions don't look particularly like the old ones.
The "proof" to me is the behavior per testing.
There is test code in there as well, under #if 0.
I did various testing on Darwin/x86, Darwin/amd64, NT386, Solaris/sparc32, Linux/x86.
Mostly on Darwin/x86 though.
Both with gcc (4.0.1) and gcc-4.2.
Old:
static long __cdecl m3_div_old
ANSI(( long b, long a))
KR((b, a) long b; long a;)
{
register long c;
if ((a == 0) && (b != 0)) { c = 0;
} else if (a > 0) { c = (b >= 0) ? (a) / (b) : -1 - (a-1) / (-b);
} else /* a < 0 */ { c = (b >= 0) ? -1 - (-1-a) / (b) : (-a) / (-b);
}
return c;
}
long __cdecl m3_mod_old
ANSI(( long b, long a))
KR((b, a) long b; long a;)
{
register long c;
if ((a == 0) && (b != 0)) { c = 0;
} else if (a > 0) { c = (b >= 0) ? a % b : b + 1 + (a-1) % (-b);
} else /* a < 0 */ { c = (b >= 0) ? b - 1 - (-1-a) % (b) : - ((-a) % (-b));
}
return c;
}
"new" or "current":
long __cdecl m3_div
ANSI(( long b, long a))
KR((b, a) long b; long a;)
{
typedef long ST; /* signed type */
typedef ulong UT; /* unsigned type */
int aneg = (a < 0);
int bneg = (b < 0);
if (aneg == bneg || a == 0 || b == 0)
return (a / b);
else
{
/* round negative result down by rounding positive result up
unsigned math is much better defined, see gcc -Wstrict-overflow=4 */
UT ua = (aneg ? M3_POS(UT, a) : (UT)a);
UT ub = (bneg ? M3_POS(UT, b) : (UT)b);
return -(ST)((ua + ub - 1) / ub);
}
}
long __cdecl m3_mod
ANSI(( long b, long a))
KR((b, a) long b; long a;)
{
typedef long ST; /* signed type */
typedef ulong UT; /* unsigned type */
int aneg = (a < 0);
int bneg = (b < 0);
if (aneg == bneg || a == 0 || b == 0)
return (a % b);
else
{
UT ua = (aneg ? M3_POS(UT, a) : (UT)a);
UT ub = (bneg ? M3_POS(UT, b) : (UT)b);
a = (ST)(ub - 1 - (ua + ub - 1) % ub);
return (bneg ? -a : a);
}
}
In the case of div, I believe my code is clear and I understand it.
But perhaps could be more efficient.
In the case of mod, I don't know what is going on actually.
I just made it look something like old and tested it.
- Jay
> From: hosking at cs.purdue.edu
> Date: Wed, 20 Jan 2010 05:07:45 -0500
> To: jay.krell at cornell.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] integer division/mod questions?
>
> These are all overflow examples correct? In which case the meaning is undefined?
>
> But certainly, 0 DIV -1 should be 0.
>
> I haven't had a chance to diff the previous code with your new code, but in the long time the previous code was in place there had never been a complaint that DIV was buggy. In the overflow cases surely we are allowed to go with whatever the hardware produces, so long as the code is efficient for non-overflow situations? I suppose one thing to ensure is that the compile-time evaluation (TInt) and the run-time evaluations are consistent, otherwise there will be confusion.
>
> On 19 Jan 2010, at 21:45, Jay K wrote:
>
> >
> >> There is a positive zero and a negative zero, and which one you get
> >
> >
> > Rodney you reminded me of something I forgot to ask:
> >
> >
> > Is 0 div -1 = 0 or -1?
> >
> >
> > In particular, in floating point, 0 / -1 is presumably -0 and 0 / 1 is presumably +0. Modula-3 is specified as returning the largest integer not greater than the floating point result. So the question then is, is 0> -0? Or are they equal? Integer-wise, there is no -0.
> > If 0> -0, then 0 div -1 should equal -1 instead of 0.
> >
> >
> > My current code I believe returns 0 for 0 div anything.
> > And I believe "the mod formula" holds as correct, since my testing checks that. I'll have to double double check.
> >
> >
> > The previous code probably also but I'll have to double check.
> > The previous code isn't necessarily the definition of correct though, since it was pretty clearly wrong for some cases.
> >
> >
> > Which is imply the question: Everyone agrees with me that the previous code was wrong? In particular, for LONG_MIN div negative, it was giving negative results, but I believe the result should be positive. Mod had a similar problem.
> >
> >
> > Nice if anyone can reproduce the problem with K&R + long long as well.
> > I don't like making changes here without some kind of independent confirmation, though I'm also pretty sure of myself..a contradiction I realize.
> >
> >
> > The previous code and I believe the current code are inconsistent as to when it would "trap", depending on compiler and optimization level. I assume that is ok for now, though in future we might want to make it predictable and honor the FloatMode stuff, but until that time, "unpredictable" is ok.
> >
> >
> > In particular, LONG_MIN div or mod -1 can trap.
> >
> >
> > div clearly has little choice. Mod I have to think about -- mod should be zero, right? LONG_MIN "evenly" divides by -1, the answer can't be represented, but the remainder can (it is zero). So maybe we should special case that to ensure it doesn't trap.
> >
> >
> > (anywhere I say "LONG_MIN", INT64_MIN has similar problem)
> >
> >
> >
> > - Jay
> >
> >
> > ----------------------------------------
> >> Date: Tue, 19 Jan 2010 18:39:22 -0600
> >> From: rodney_bates at lcwb.coop
> >> To: m3devel at elegosoft.com
> >> Subject: Re: [M3devel] integer division/mod questions?
> >>
> >>
> >>
> >> hendrik at topoi.pooq.com wrote:
> >>> On Sun, Jan 17, 2010 at 10:44:53AM +0000, Jay K wrote:
> >>>> -2147483648 div 2147483647 ?
> >>>> -2147483648 mod 2147483647 ?
> >>>>
> >>>> quotient = -1, remainer = -1 seems reasonable.
> >>>> 2147483647 * -1 + -1 == -2147483648
> >>>>
> >>>
> >>> There are two kinds of binary integer arithmetic -- two's complement
> >>> and one's complement. In my experience, two's complement machines tend
> >>> to have the remainder being the same sign as the dividend; one's
> >>> complement machines semm to have a remainder the same sign as the
> >>> divisor.
> >>>
> >>> One's complement machines are all but extinct these days.
> >>
> >> Tony, you were concerned about showing your age, but 20 years is but an
> >> evening past. I remember programming ones-complement arithmetic
> >> in assembly language, definitely more decades ago than two.
> >> And that was not my first job.
> >>
> >> There is a positive zero and a negative zero, and which one you get
> >> can depend on the operation and operand values that produced the
> >> result, so you have to check for both of them, often with two
> >> separate conditional branches.
> >>
> >> Anyone remember nines- or tens-complement arithmetic on decimal
> >> machines? Electromechanical accounting machines?
> >>
> >>
> >>>
> >>>> However, Modula-3 specifies div as rounding down, so
> >>>>
> >>>> -2147483648 div 2147483647 == -2
> >>>>
> >>>> and then
> >>>>
> >>>> http://www.modula3.com/cm3/doc/reference/arithmetic.html
> >>>>
> >>>> The value x DIV y is the floor of
> >>>> the quotient of x and y; that is, the maximum integer
> >>>> not exceeding the real number z such that z * y = x.
> >>>> For integers x and y, the value of x MOD y is
> >>>> defined to be x - y * (x DIV y).
> >>>>
> >>>>
> >>>> This means that for positive y, the value of x MOD y
> >>>> lies in the interval [0 .. y-1], regardless of
> >>>> the sign of x. For negative y, the value of
> >>>> x MOD y lies in the interval [y+1 .. 0], regardless
> >>>> of the sign of x.
> >>>
> >>> And this is consistent with MOD producing a canonical representative of
> >>> an equivalence class modulo y. It's what's wanted for a lot of
> >>> algorithms. What it returns for negative y isn't as important, but
> >>> it is important to have positive MODuli for positive y no matter what
> >>> the sign of x is.
> >>>
> >>> But it's not what most two's-complement processors produce naturally.
> >>> Having a MODulo operation that is mathematically well-behaved takes
> >>> extra effort on these machines.
> >>>
> >>> And it's also important to have a remainder that corresponds to the
> >>> division operator. On two's complement machines you have to either
> >>> * use extra instructions to correct the result of the divide
> >>> instruction to correspond to the mathematically desirable MOD
> >>> operator, or
> >>> * Have a separate remainder operation that does correspond to
> >>> division.
> >>>
> >>> On one's complement machines MOD will have the same effect as remainder.
> >>> On two's complement, different.
> >>>
> >>> -- hendrik
> >>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20100120/5a443bbb/attachment-0002.html>
More information about the M3devel
mailing list