[M3devel] integer division/mod questions?

[Jay K]

Thanks Hendrik. I didn't realize the relationship to one's complement.

In my little experimentation:

 C modulo, which I assume is machine modulo, returns the sign of the first parameter.

 Modula-3 specifies it to have the sign of the second parameter.

 The "formula" appears to hold either way.

  But I'd have to double check.

 

 

Hand.c used "tricks" to implement div and mod.

My replacement functions are clear for div but still tricky for mod.

I don't understand the tricks.

In fact I just guessed and wrote something similar to the original, but different.

 

 

One goal was to avoid dependency on signed arithmetic overflow, though

 I compromised somewhat, I think. That is, I'm not sure if negative / negative

  and negative mod negative in C depend on overflow.

  What gcc was telling me is the "trick" in the old div function did depend

  on modulo. Ultimately I'm not sure if this dependency was even a problem or not,

  as the bug at least for div tended to occur more with unoptimized compilation.

  Optimization actually tended to fix the bug. But it did vary with compilers.

  Specifically dividing and moding LONG_MIN (or INT64_MIN) by negative numbers

  produced a result with the wrong sign. There was probably also a problem

  with K&R style. The "crash" or "trap" was appropriate.

 

 

I was *actually* wondering if depency on overflow would be a problem

for the other functions I added, but apparently not.

Still I might consider writing them to use only unsigned, or deleting them.

 

 

One of my implied questions is:
  Do people believe my changes are correct?

  Please look at them.

  Esp. mod.

 

 

 - Jay

 
> Date: Sun, 17 Jan 2010 15:39:42 -0500
> From: hendrik at topoi.pooq.com
> To: m3devel at elegosoft.com
> Subject: Re: [M3devel] integer division/mod questions?
> 
> On Sun, Jan 17, 2010 at 11:08:15AM -0500, Tony Hosking wrote:
> > On 17 Jan 2010, at 05:50, Jay K wrote:
> > 
> > > I think I missed a sign.
> > > 
> > > -2147483648 - 2147483647 * -2
> > > actually -2147483648 + 2 * 2147483647
> > > actually 2147483646
> > > 
> > > which agrees.
> > > 
> > > so 
> > > 
> > > -2147483648 div 2147483647 = -2 
> > > -2147483648 mod 2147483647 = 2147483646 
> > > 
> > > -2 * 2147483647 + 2147483646 = -2147483648
> > > 
> > > I'll make sure m3_mod works this way if it doesn't already.
> > > Presumably we are stuck with these rules.
> > 
> > Yep. I seem to remember reading some rationale somewhere sometime somehow, but I forget where when how. Anyone?
> 
> It gives results that satisfy important mathematical identities, such as
> 
> (a + m) MOD m = a MOD m
> 
> which makes it easier to reason about the correctness of algorithms and 
> program transformations.
> 
> -- hendrik
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20100118/0791186c/attachment-0002.html>