Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Modulus returns negative numbers #448

Closed
hoisie opened this issue Dec 21, 2009 · 6 comments
Closed

Modulus returns negative numbers #448

hoisie opened this issue Dec 21, 2009 · 6 comments

Comments

@hoisie
Copy link
Contributor

hoisie commented Dec 21, 2009

What steps will reproduce the problem?
1. In go, -16 % 7 returns -2. 

What is the expected output? What do you see instead?
Most other places (python, ruby, the google search box) returns 5

What is your $GOOS?  $GOARCH?
linux/amd64

Which revision are you using?  (hg identify)
cd893740a338+ tip
@hoisie
Copy link
Contributor Author

hoisie commented Dec 21, 2009

Comment 1:

Although both are technically right, it would be more useful (in a mathematical sense) 
if something mod a positive number is also positive

@rsc
Copy link
Contributor

rsc commented Dec 21, 2009

Comment 2:

This is spelled out in quite a bit of detail at
http://golang.org/doc/go_spec.html#Arithmetic_operators
Go has the nice property that -a/b == -(a/b).
You want the property that a%b == (-a)%b.
Unfortunately, these are contradictory.
It's interesting that Python (and others)
truncate away from zero: the standard C behavior
is to truncate toward zero.
Robert may have more to add.

Owner changed to r...@golang.org.

Status changed to WontFix.

@griesemer
Copy link
Contributor

Comment 3:

There are several possible definitions for % that satisfy the property
(a / b) * b + a % b == a
http://portal.acm.org/citation.cfm?id=128862 discusses various options in detail. 
Specifically, the Euclidian definition of the modulo operation is particularly useful in 
many contexts and also would permit more optimizations (strength reduction when 
the divisor is a power of two is always possible, not just when the dividend is 
positive).
There are a several reasons for the current definition:
- the current semantics for % is directly available as a result from x86 architectures
- it would be confusing to change the meaning of the elementary operator % and not 
change its name
- it's fairly easy to compute another modulus from the % result
Note that % computes the "remainder" as opposed to the "modulus". A definition of 
the "modulus" according to the Euclidian definition would make a lot of sense. In 
contrast, the remainder is simply what remains left after the division.

@gopherbot
Copy link

Comment 4 by jpetkau:

Already closed, so I suppose there's not much point adding to this, but this issue 
(broken integer division and modulus) is a pet peeve of mine, and I was disappointed 
to find it in Go.
> the current semantics for % is directly available as a result from x86 
architectures
Unfortunately true, but:
> it's fairly easy to compute another modulus from the % result
Sort of. There are two ways to do it: doing an extra (expensive) division
    ((m % n) + n) % n;
or doing an extra (expensive) conditional
    temp = m % n
    if temp < 0: temp += n
Hopefully the compiler will see that it can do a conditional move in the second case, 
but it's not obvious.
> it would be confusing to change the meaning of the elementary operator % and not 
change its name
Confusing to existing Go users for a little while, but there aren't many of them yet.  
Users from other languages will expect different behavior; Python, for example, 
truncates integer division toward negative infinity and thus % / remainder / modulus 
are all the same thing.
The real problem with the current behavior is that it's literally useless. I defy you 
(= whoever reads this) to come up with *any* example where round-toward-zero is 
actually the desired behavior (by which I mean, it translates into simpler code.) 
There are basically only three cases that actually occur in practice:
1. (very common) The divisor is known to be positive, so the behavior doesn't matter
2. (occasional) Negative numbers have to be handled specially anyway, so the behavior 
doesn't matter.
3. (common) Modulus is the desired behavior, and dealing with negative remainders is 
a pain.
For example: how do you adjust an array index with wraparound?
  array[(i+step) % arraysize] vs. array[(i+step+arraysize) % arraysize] vs. 
array[((i+step)%arraysize+arraysize)%arraysize].
  Note that the second example is correct for small steps but breaks when they get 
big enough.
Or date arithmetic:
  (weekday + delta_days) % 7 vs. ((weekday + delta_days) % 7) + delta_days) % 7 vs. 
the incredible buggy hacks that people actually come up with
And since this is already turning into a rant, float-to-int conversion has the same 
problem (truncate toward zero). And you can't claim that it's better on x86--in fact 
you have to jump through terrible hoops to do it, messing with the rounding modes and 
all. (Ok, not so much these days, since SSE2 finally baked this abomination into 
silicon. But it's still shameful.)
If it really is too late to change the language, could there perhaps be some 
additions to the Math package, with standard implementations of the sane behavior, 
and some expectation that the compiler would know about them and compile them into 
the appropriate instructions? E.g.
div(i1,i2) // integer division with round to -inf
mod(i1,i2) // modulus, with div(i1,i2)*i2 + mod(i1,i2) == i1
ifloor(float) // convert float to int, rounding toward -inf
iceil(float) // convert float to int, rounding toward +inf
iround(float) // convert float to int, using ieee round-to-nearest
itrunc(float) // convert float to int, rounding toward zero

@rsc
Copy link
Contributor

rsc commented Feb 4, 2010

Comment 5:

Please use the mailing list for discussions.

@griesemer
Copy link
Contributor

Comment 6:

Providing this functionality in the math package seems reasonable. Note that the 
bignum package provides both Quo and Rem (corresponding to / and %) as well as Div 
and Mod (which follow the Euclidean definition, which arguably is the most useful 
definition for division and modulo of integers and which satisfies your requirements).
(I have argued myself for div and mod operators as you suggest, but unfortunately lost 
that battle.)

This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

4 participants