<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Actually I think the new mod/div functions are still a little<BR>
risky for negative div or mod negative.<BR>
They'd more reliable/predictable/portable if if they used unsigned<BR>
numbers.<BR>
<BR>
<BR>
The reason I started looking at this stuff is because I was<BR>
reading about gcc assuming signed overflow won't occur<BR>
and then making optimizations with that assumption.<BR>
You can ask it to warn when it does so.<BR>I thought this might break the new but unused m3_add and<BR>
such. The warning triggered for the existing div (but not mod) functions.<BR>
So I set about rewriting them to use unsigned math, which<BR>
is the recommendation here -- because its overflow is<BR>
well defined by the C standard -- and then comparing<BR>
mine with the previous/current code..and noticed wrong behavior<BR>
in the previous/current.<BR>
<BR>
- Jay<BR>
<BR><BR> <BR>
<HR id=stopSpelling>
From: jay.krell@cornell.edu<BR>To: hosking@cs.purdue.edu<BR>Date: Wed, 20 Jan 2010 11:27:17 +0000<BR>CC: m3devel@elegosoft.com<BR>Subject: Re: [M3devel] integer division/mod questions?<BR><BR>
<STYLE>
.ExternalClass .ecxhmmessage P
{padding:0px;}
.ExternalClass body.ecxhmmessage
{font-size:10pt;font-family:Verdana;}
</STYLE>
No, not overflow examples.<BR> <BR> <BR>LONG_MIN divided by any negative number was a negative number.<BR> But I believe it should be positive.<BR> I don't believe e.g. LONG_MIN DIV -2 is something involving overflow.<BR> The result is representable.<BR> LONG_MIN mod negative numbers also had the wrong sign.<BR> <BR> <BR>You don't really have to view a diff.<BR>I left the old functions m3_mod, m3_div, present, renamed<BR>to m3_mod_old, m3_div_old.<BR> <BR> <BR>So you can see both versions.<BR>The new versions don't look particularly like the old ones.<BR>The "proof" to me is the behavior per testing.<BR>There is test code in there as well, under #if 0.<BR>I did various testing on Darwin/x86, Darwin/amd64, NT386, Solaris/sparc32, Linux/x86.<BR>Mostly on Darwin/x86 though.<BR>Both with gcc (4.0.1) and gcc-4.2.<BR> <BR> <BR>Old:<BR> <BR>static long __cdecl m3_div_old<BR> ANSI(( long b, long a))<BR> KR((b, a) long b; long a;)<BR>{<BR> register long c;<BR> <BR> if ((a == 0) && (b != 0)) { c = 0;<BR> } else if (a > 0) { c = (b >= 0) ? (a) / (b) : -1 - (a-1) / (-b);<BR> } else /* a < 0 */ { c = (b >= 0) ? -1 - (-1-a) / (b) : (-a) / (-b);<BR> }<BR> return c;<BR>}<BR><BR> <BR>long __cdecl m3_mod_old<BR> ANSI(( long b, long a))<BR> KR((b, a) long b; long a;)<BR>{<BR> register long c;<BR> if ((a == 0) && (b != 0)) { c = 0;<BR> } else if (a > 0) { c = (b >= 0) ? a % b : b + 1 + (a-1) % (-b);<BR> } else /* a < 0 */ { c = (b >= 0) ? b - 1 - (-1-a) % (b) : - ((-a) % (-b));<BR> }<BR> return c;<BR>}<BR><BR> <BR>"new" or "current":<BR> <BR>long __cdecl m3_div<BR> ANSI(( long b, long a))<BR> KR((b, a) long b; long a;)<BR>{<BR> typedef long ST; /* signed type */<BR> typedef ulong UT; /* unsigned type */<BR> int aneg = (a < 0);<BR> int bneg = (b < 0);<BR> if (aneg == bneg || a == 0 || b == 0)<BR> return (a / b);<BR> else<BR> {<BR> /* round negative result down by rounding positive result up<BR> unsigned math is much better defined, see gcc -Wstrict-overflow=4 */<BR> UT ua = (aneg ? M3_POS(UT, a) : (UT)a);<BR> UT ub = (bneg ? M3_POS(UT, b) : (UT)b);<BR> return -(ST)((ua + ub - 1) / ub);<BR> }<BR>}<BR><BR> <BR>long __cdecl m3_mod<BR> ANSI(( long b, long a))<BR> KR((b, a) long b; long a;)<BR>{<BR> typedef long ST; /* signed type */<BR> typedef ulong UT; /* unsigned type */<BR> int aneg = (a < 0);<BR> int bneg = (b < 0);<BR> if (aneg == bneg || a == 0 || b == 0)<BR> return (a % b);<BR> else<BR> {<BR> UT ua = (aneg ? M3_POS(UT, a) : (UT)a);<BR> UT ub = (bneg ? M3_POS(UT, b) : (UT)b);<BR> a = (ST)(ub - 1 - (ua + ub - 1) % ub);<BR> return (bneg ? -a : a);<BR> }<BR>}<BR><BR> <BR>In the case of div, I believe my code is clear and I understand it.<BR>But perhaps could be more efficient.<BR> <BR> <BR>In the case of mod, I don't know what is going on actually.<BR>I just made it look something like old and tested it.<BR> <BR> <BR> - Jay<BR><BR> <BR>> From: hosking@cs.purdue.edu<BR>> Date: Wed, 20 Jan 2010 05:07:45 -0500<BR>> To: jay.krell@cornell.edu<BR>> CC: m3devel@elegosoft.com<BR>> Subject: Re: [M3devel] integer division/mod questions?<BR>> <BR>> These are all overflow examples correct? In which case the meaning is undefined?<BR>> <BR>> But certainly, 0 DIV -1 should be 0.<BR>> <BR>> 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.<BR>> <BR>> On 19 Jan 2010, at 21:45, Jay K wrote:<BR>> <BR>> > <BR>> >> There is a positive zero and a negative zero, and which one you get <BR>> > <BR>> > <BR>> > Rodney you reminded me of something I forgot to ask: <BR>> > <BR>> > <BR>> > Is 0 div -1 = 0 or -1?<BR>> > <BR>> > <BR>> > 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.<BR>> > If 0> -0, then 0 div -1 should equal -1 instead of 0.<BR>> > <BR>> > <BR>> > My current code I believe returns 0 for 0 div anything.<BR>> > And I believe "the mod formula" holds as correct, since my testing checks that. I'll have to double double check.<BR>> > <BR>> > <BR>> > The previous code probably also but I'll have to double check.<BR>> > The previous code isn't necessarily the definition of correct though, since it was pretty clearly wrong for some cases.<BR>> > <BR>> > <BR>> > 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.<BR>> > <BR>> > <BR>> > Nice if anyone can reproduce the problem with K&R + long long as well.<BR>> > 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.<BR>> > <BR>> > <BR>> > 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.<BR>> > <BR>> > <BR>> > In particular, LONG_MIN div or mod -1 can trap.<BR>> > <BR>> > <BR>> > 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.<BR>> > <BR>> > <BR>> > (anywhere I say "LONG_MIN", INT64_MIN has similar problem)<BR>> > <BR>> > <BR>> > <BR>> > - Jay<BR>> > <BR>> > <BR>> > ----------------------------------------<BR>> >> Date: Tue, 19 Jan 2010 18:39:22 -0600<BR>> >> From: rodney_bates@lcwb.coop<BR>> >> To: m3devel@elegosoft.com<BR>> >> Subject: Re: [M3devel] integer division/mod questions?<BR>> >> <BR>> >> <BR>> >> <BR>> >> hendrik@topoi.pooq.com wrote:<BR>> >>> On Sun, Jan 17, 2010 at 10:44:53AM +0000, Jay K wrote:<BR>> >>>> -2147483648 div 2147483647 ?<BR>> >>>> -2147483648 mod 2147483647 ?<BR>> >>>> <BR>> >>>> quotient = -1, remainer = -1 seems reasonable.<BR>> >>>> 2147483647 * -1 + -1 == -2147483648<BR>> >>>> <BR>> >>> <BR>> >>> There are two kinds of binary integer arithmetic -- two's complement<BR>> >>> and one's complement. In my experience, two's complement machines tend<BR>> >>> to have the remainder being the same sign as the dividend; one's<BR>> >>> complement machines semm to have a remainder the same sign as the<BR>> >>> divisor.<BR>> >>> <BR>> >>> One's complement machines are all but extinct these days.<BR>> >> <BR>> >> Tony, you were concerned about showing your age, but 20 years is but an<BR>> >> evening past. I remember programming ones-complement arithmetic<BR>> >> in assembly language, definitely more decades ago than two.<BR>> >> And that was not my first job.<BR>> >> <BR>> >> There is a positive zero and a negative zero, and which one you get<BR>> >> can depend on the operation and operand values that produced the<BR>> >> result, so you have to check for both of them, often with two<BR>> >> separate conditional branches.<BR>> >> <BR>> >> Anyone remember nines- or tens-complement arithmetic on decimal<BR>> >> machines? Electromechanical accounting machines?<BR>> >> <BR>> >> <BR>> >>> <BR>> >>>> However, Modula-3 specifies div as rounding down, so<BR>> >>>> <BR>> >>>> -2147483648 div 2147483647 == -2<BR>> >>>> <BR>> >>>> and then<BR>> >>>> <BR>> >>>> http://www.modula3.com/cm3/doc/reference/arithmetic.html<BR>> >>>> <BR>> >>>> The value x DIV y is the floor of<BR>> >>>> the quotient of x and y; that is, the maximum integer<BR>> >>>> not exceeding the real number z such that z * y = x.<BR>> >>>> For integers x and y, the value of x MOD y is<BR>> >>>> defined to be x - y * (x DIV y).<BR>> >>>> <BR>> >>>> <BR>> >>>> This means that for positive y, the value of x MOD y<BR>> >>>> lies in the interval [0 .. y-1], regardless of<BR>> >>>> the sign of x. For negative y, the value of<BR>> >>>> x MOD y lies in the interval [y+1 .. 0], regardless<BR>> >>>> of the sign of x.<BR>> >>> <BR>> >>> And this is consistent with MOD producing a canonical representative of<BR>> >>> an equivalence class modulo y. It's what's wanted for a lot of<BR>> >>> algorithms. What it returns for negative y isn't as important, but<BR>> >>> it is important to have positive MODuli for positive y no matter what<BR>> >>> the sign of x is.<BR>> >>> <BR>> >>> But it's not what most two's-complement processors produce naturally.<BR>> >>> Having a MODulo operation that is mathematically well-behaved takes<BR>> >>> extra effort on these machines.<BR>> >>> <BR>> >>> And it's also important to have a remainder that corresponds to the<BR>> >>> division operator. On two's complement machines you have to either<BR>> >>> * use extra instructions to correct the result of the divide<BR>> >>> instruction to correspond to the mathematically desirable MOD<BR>> >>> operator, or<BR>> >>> * Have a separate remainder operation that does correspond to<BR>> >>> division.<BR>> >>> <BR>> >>> On one's complement machines MOD will have the same effect as remainder.<BR>> >>> On two's complement, different.<BR>> >>> <BR>> >>> -- hendrik<BR>> >>> <BR>> <BR> </body>
</html>