[M3devel] integer division/mod questions?

Wed Jan 20 12:21:00 CET 2010

Only lately with C99.

Prior to that it was unspecified.

 - Jay

From: hosking at cs.purdue.edu
Date: Wed, 20 Jan 2010 05:09:33 -0500
To: jay.krell at cornell.edu
CC: m3devel at elegosoft.com
Subject: Re: [M3devel] integer division/mod questions?

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  +1 765 494 6001  | Mobile  +1 765 427 5484  +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/5060991a/attachment-0002.html>