[M3devel] integer division/mod questions?

[Jay K]

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
>>>