<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Thanks Hendrik. I didn't realize the relationship to one's complement.<BR>
In my little experimentation:<BR>
C modulo, which I assume is machine modulo, returns the sign of the first parameter.<BR>
Modula-3 specifies it to have the sign of the second parameter.<BR>
The "formula" appears to hold either way.<BR>
But I'd have to double check.<BR>
<BR>
<BR>
Hand.c used "tricks" to implement div and mod.<BR>
My replacement functions are clear for div but still tricky for mod.<BR>
I don't understand the tricks.<BR>
In fact I just guessed and wrote something similar to the original, but different.<BR>
<BR>
<BR>
One goal was to avoid dependency on signed arithmetic overflow, though<BR>
I compromised somewhat, I think. That is, I'm not sure if negative / negative<BR>
and negative mod negative in C depend on overflow.<BR>
What gcc was telling me is the "trick" in the old div function did depend<BR>
on modulo. Ultimately I'm not sure if this dependency was even a problem or not,<BR>
as the bug at least for div tended to occur more with unoptimized compilation.<BR>
Optimization actually tended to fix the bug. But it did vary with compilers.<BR>
Specifically dividing and moding LONG_MIN (or INT64_MIN) by negative numbers<BR>
produced a result with the wrong sign. There was probably also a problem<BR>
with K&R style. The "crash" or "trap" was appropriate.<BR>
<BR>
<BR>
I was *actually* wondering if depency on overflow would be a problem<BR>
for the other functions I added, but apparently not.<BR>
Still I might consider writing them to use only unsigned, or deleting them.<BR>
<BR>
<BR>
One of my implied questions is:<BR> Do people believe my changes are correct?<BR>
Please look at them.<BR>
Esp. mod.<BR>
<BR>
<BR>
- Jay<BR><BR> <BR>> Date: Sun, 17 Jan 2010 15:39:42 -0500<BR>> From: hendrik@topoi.pooq.com<BR>> To: m3devel@elegosoft.com<BR>> Subject: Re: [M3devel] integer division/mod questions?<BR>> <BR>> On Sun, Jan 17, 2010 at 11:08:15AM -0500, Tony Hosking wrote:<BR>> > On 17 Jan 2010, at 05:50, Jay K wrote:<BR>> > <BR>> > > I think I missed a sign.<BR>> > > <BR>> > > -2147483648 - 2147483647 * -2<BR>> > > actually -2147483648 + 2 * 2147483647<BR>> > > actually 2147483646<BR>> > > <BR>> > > which agrees.<BR>> > > <BR>> > > so <BR>> > > <BR>> > > -2147483648 div 2147483647 = -2 <BR>> > > -2147483648 mod 2147483647 = 2147483646 <BR>> > > <BR>> > > -2 * 2147483647 + 2147483646 = -2147483648<BR>> > > <BR>> > > I'll make sure m3_mod works this way if it doesn't already.<BR>> > > Presumably we are stuck with these rules.<BR>> > <BR>> > Yep. I seem to remember reading some rationale somewhere sometime somehow, but I forget where when how. Anyone?<BR>> <BR>> It gives results that satisfy important mathematical identities, such as<BR>> <BR>> (a + m) MOD m = a MOD m<BR>> <BR>> which makes it easier to reason about the correctness of algorithms and <BR>> program transformations.<BR>> <BR>> -- hendrik<BR> </body>
</html>