🔒 Locked

Integer division by negatives

Started by Aprosenf Nov 2, 2005 at 12:25 AM 4 replies 1.5k views

Original Post

Nov 2, 2005 at 12:25 AM

I'm designing a circuit that performs integer division on 32-bit 2's-complement numbers, and I'm curious on what the standards are for integer division with negative operands. For example, what should the results of 7 / (-3), (-7) / 3, and (-7) / (-3) be? Similarly, what should the results of 7 % (-3), (-7) % 3, and (-7) % (-3) be? On my computer, I get +/-2 for all of the quotients and +/-1 for all of the remainders, but there are a few mathematical points of note: However you choose to define integer division, you should have for all a, b (b != 0) that a == (a / b) * b + (a % b). In analysis, when we divide one number a by another positive number b, there are unique numbers q, r such that a = qb + r, q is an integer, and 0 <= r < b. So, you could make the argument that (-7) / 3 should be -3 and (-7) % 3 should be +2. However, for negative dividends, you obviously cannot satisfy 0 <= r < b, so the natural extensions are b < r <= 0 or 0 <= r < |b|. Personally, I prefer to always have a positive remainder, but choosing to do division that way also has some problems: for example, (-a) / b != -(a / b) if a, b > 0. Thoughts?

Raduprv

Nov 2, 2005 at 12:30 AM

If one of the operands is negative, then the result is negative. If both are negative or positve, the result is positive.
They teach those things in the 7th grade or something :D

Zipster

Nov 2, 2005 at 2:33 AM

I now submit to you the longest discussion of the modulus operation with regards to negative numbers that I've ever read. Oh and believe me I've read many! A quotable quote:

Quote:
So what's the conclusion? There are basically two models, reasonably distinguished in Ada terms as Remainder and Mod; the C++ "%" operator is really Remainder, not Mod, despite what it's often called. Actually, its behavior for negative numbers is not even defined officially; like many things in C, it's left to be processor-dependent because C does not define how a processor should handle integer division. Just by chance, all compilers I know truncate integers toward zero, and therefore treat "%" as remainder, following the precedent of FORTRAN.

Depending on how your circuit implements division, I'd just take the absolute values of both the inputs, do the division, and then negate the output if either of the inputs were negative. 2's-complement form is great for addition, but I don't know if it also lends itself naturally to multiplication and division involving negative numbers.

Aprosenf

Nov 2, 2005 at 9:42 PM

Quote:
Original post by Raduprv
If one of the operands is negative, then the result is negative. If both are negative or positve, the result is positive.
They teach those things in the 7th grade or something :D

Yes, I'm well aware of that. The issue was not what the sign of the result should be, the issue is whether we should add/subtract one to the quotient in order to make it consistent with the remainder operation.

Quote:
Original post by Zipster
I now submit to you the longest discussion of the modulus operation with regards to negative numbers that I've ever read. Oh and believe me I've read many! A quotable quote:

Quote:
So what's the conclusion? There are basically two models, reasonably distinguished in Ada terms as Remainder and Mod; the C++ "%" operator is really Remainder, not Mod, despite what it's often called. Actually, its behavior for negative numbers is not even defined officially; like many things in C, it's left to be processor-dependent because C does not define how a processor should handle integer division. Just by chance, all compilers I know truncate integers toward zero, and therefore treat "%" as remainder, following the precedent of FORTRAN.

Depending on how your circuit implements division, I'd just take the absolute values of both the inputs, do the division, and then negate the output if either of the inputs were negative. 2's-complement form is great for addition, but I don't know if it also lends itself naturally to multiplication and division involving negative numbers.

Thanks for the link, that was a good read. I think I'm going to go by your suggestion and simply compute |a| / |b| and then negate the result if necessary. 2's-complement is very convenient for for addition, subtraction, and multiplication (with a few weird things in the upper bits for negative numbers), but as far as I can tell, it does not work very well with division.

Neophyte

Nov 3, 2005 at 6:02 AM

Quote:
Original post by Anonymous Poster
Quote:
Original post by Raduprv
If one of the operands is negative, then the result is negative.

I know I'm just nitpicking but...

Friendly Revision: "Iff one of the operands is negative, then the result is negative."

I know I'm just nitpicking but...

Friendly Revision: "Iff onee of the operands is negative, then the result is negative."

(See Exactly One)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.