[M3devel] integer division/mod questions?

Wed Jan 20 11:09:33 CET 2010

C specifies truncated division.

Antony Hosking | Associate Professor | Computer Science | Purdue University
305 N. University Street | West Lafayette | IN 47907 | USA
Office +1 765 494 6001 | Mobile +1 765 427 5484

On 19 Jan 2010, at 21:59, Jay K wrote:

> 
> That paper also suggests a more efficient algorithm we should probably adopt:
> 
> 
> /* Floored division */
> long divF( long D, long d )
> {
> long q = D/d;
> long r = D%d;
> if ((r> 0 && d < 0) || (r < 0 && d> 0)) q = q-1;
> return q;
> }
> 
> 
> long modF( long D, long d )
> {
> long r = D%d;
> if ((r> 0 && d < 0) || (r < 0 && d> 0)) r = r+d;
> return r;
> }
> 
> 
> Though the condition should be perhaps the equivalent (r < 0) != (d < 0)
> or (r < 0) ^ (d < 0)
> 
> 
> We'd probably want to be sure the / followed by % got optimized into just one divide though.
> 
> 
> or maybe what I have is fine.
> As long as the inputs are the same sign, the current code does just one / or one %. It is only for mixed sign inputs that you need more care.
> I am assuming C never "rounds", but either truncates or "floors".
> e.g. 1/2 in the face of rounding is 1.
> 
> 
> Integer division probably not a big concern anyway, esp. with any negative numbers. The main place I ever see division/mod used is hash tables, and the numbers are always positive (I rarely see negative numbers used anywhere in "systems" programming actually -- file sizes, array indices, array sizes..all positive; "math" needs floating point often...)
> 
> 
> - Jay
> 
> 
> ----------------------------------------
>> From: jay.krell at cornell.edu
>> To: rodney_bates at lcwb.coop; m3devel at elegosoft.com
>> Date: Wed, 20 Jan 2010 02:45:43 +0000
>> Subject: Re: [M3devel] integer division/mod questions?
>> 
>> 
>>> 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/8fa44102/attachment-0002.html>