8

A document about the precursor to ANDF (Architecture Neutral Distribution Format) mentions that two of its integer division/remainder primitives "are those generally implemented directly by processor instructions giving the sign of the remainder the same as the sign of the quotient" (it would be more precise to say that the sign of the non-zero remainder is positive if signs of the dividend and the divisor match, and negative otherwise). The other two primitives implement the case where the sign of remainder is the same as the sign of divisor.

Was this a misstatement (intending "dividend", as in x86), or there really was a CPU implementing this peculiar kind of integer division? None of the programming languages define their modulo operation to make the remainder to follow the sign of the quotient.

After some thought, I'm convinced that "the sign of the quotient" was a mistake in the document.

Using dimensional analysis, consider moving N ft North (positive) of South (negative) making K ft steps while facing North or South. The result is N/K full steps, where the sign of the result determines whether the steps were forwards (positive) or backwards (negative). The remainder of the distance could be either always in the same direction as were the full steps (the sign of the remainder follows the sign of the dividend), or always forwards (the sign of the remainder follows the sign of the divisor), or always to the North (the remainder is always positive). The obvious opposites are also possible but less useful.

However, the situation when the remainder of the distance would be to the North if the steps were forwards, and to the South if they were backwards, or vice versa, doesn't make sense.

Improve this question
10
  • 1
    Integer division by negative divisors is pretty rare. I suspect the documentation is erroneous, but I'm hard-pressed to think situations where code which divides by a negative number would be interested the remainder except to observe whether it was equal to zero (or, for that matter, where code would want a negative remainder in the positive divisor case). By comparison, many things like periodic-scheduling algorithms can benefit from a division operator which guarantees remainder >= 0.
    – supercat
    Jun 23, 2017 at 20:18
  • @supercat Curiously, the "Modulo operation" wiki page shows that "positive always" is fairly rare in programming languages.
    – Leo B.
    Jun 23, 2017 at 20:53
  • It is rare. In almost every case where it matters, the positive-always behavior will be more useful but making an operator always return positive would increase the cost of the more common cases where either behavior would be equally useful. That having been said, I would think a programming language which wants to favor optimizations for speed should have operators that allow a compiler to choose between the two behaviors in Unspecified (no guarantee of consistency) fashion. For some divisors (e.g. power of 2), computing an always-positive modulus would be cheaper than a...
    – supercat
    Jun 23, 2017 at 21:13
  • ...remainder that matches the sign of the dividend. Having separate operators for a specific useful behavior and for "either is fine" behavior would allow some straightforward efficiency improvements that would otherwise be much harder or impossible.
    – supercat
    Jun 23, 2017 at 21:16
  • 1
    @hobbs: Integer division can uphold (n+d)/d==(n/d)+1 or (-n)/d==-(n/d), but if the remainder is non-zero it can't uphold both. To my mind, the former property is more useful than the latter. Most of the code I've seen that uses signed integer division in cases which involve non-zero remainders ends up having to handle positive and negative cases separately, but a floored division operator could eliminate that need (e.g. in Python, which has such an operator, the rounded average of x+y+z is (x+y+z+1)//3). As for the guarantee you mention, the only use I can think of for it...
    – supercat
    Jul 2, 2017 at 19:13

1 Answer 1

Reset to default
2

It is relatively easy to show that the sentence

The operators div2 and rem2 are those generally implemented directly by processor instructions giving the sign of the remainder the same as the sign of the quotient.

is self contradictory. Processors giving the sign of the remainder the same as the sign of the quotient are hard to find. So hard that I found none.

For instance, Blaauw and Brooks's Computer architecture, history and evolution is usually a very good source to find out the design spaces explored by historical computers. They have a quite precise description of 28 architectures of historical importance (from Zuse to the 8080), and they have chapters describing each design choice in which they don't hesitate to use other examples if they are relevant. Yet on the subject of the sign of the remainder, they give no variation at all. They just state that the customary approach is to have the sign of the remainder be the sign of the dividend. They signal that some have proposed to use the sign of the divisor instead, but they give no examples of processors following that proposition (BTW, the only one I'm aware is Knuth's MMIX and that's an artificial one).

I also looked at the manuals of some other processors too recent to have been considered by Blaauw and Brooks. All of those which had dividing instructions(*) were using the customary sign-of-remainder-is-sign-of-dividend algorithm.

It is for sure possible that I've missed a processor using the sign of quotient algorithm. But considering that that algorithm seems to offer no interesting properties (sign of dividend has lot of sign symmetries, sign of divisor and always positive have a periodic remainder), I consider that improbable.

In summary:

  • the original statement is self contradictory

  • the only remainder algorithm for remainder's sign which can be considered as generally implemented is the sign of dividend (I've yet to find one processor which provided something else)

  • it is unlikely that they desired to provide an uncommon operation as having the sign of the remainder the same as the sign of the quotient does not offer interesting properties.

(*) I've not looked in details what kind of result was provided by those having division-assist instructions.

Improve this answer
3
  • 3
    I don't see how the sentence is self-contradictory.
    – Leo B.
    Jun 30, 2017 at 18:43
  • @LeoB., the sentence states two things (rem2 is the instruction generally implemented directly by processor instructions, rem2 gives the sing of the remainder the same sign as the quotient) which can be both true at the same time. That seems self-contradictory to me.
    – AProgrammer
    Jul 7, 2017 at 8:44
  • 3
    In principle, the deduction "there is a common processor instruction that gives the sign of remainder the same as the quotient" can be true (who knows, maybe on Alpha Centauri their religion dictates that it should be so); it's only in our reality that the deduction is a false statement. So the sentence is contrary to reality, but not self-contradictory.
    – Leo B.
    Jul 7, 2017 at 15:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .