## digitalmars.D - Should % ever "overflow"?

• Andrei Alexandrescu (8/8) Jun 24 2016 In a checked environment, division may "overflow", e.g. -6 / 2u must be
• deadalnix (5/13) Jun 24 2016 Most reasonable is
• jmh530 (12/15) Jun 24 2016 Example:
• Smoke (24/41) Jun 25 2016 This proves nothing.
• deadalnix (6/7) Jun 25 2016 This isn't a proof, this is a definition. This is the definition
• Smoke (5/13) Jun 25 2016 Again, no proof at all and inaccurate. Not every programming
• Guillaume Boucher (8/11) Jun 25 2016 Depends on the definition.
• Timon Gehr (9/18) Jun 24 2016 Well, actually, lhs % 0 should be equal to lhs... :-)
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
In a checked environment, division may "overflow", e.g. -6 / 2u must be
typed as uint but is not representable properly one.

How about remainder? I suppose one can make the argument that remainder
should never overflow (save for rhs == 0), because it could be defined
with either a positive or negative denominator (which is not part of the
result).

What's the most reasonable behavior?

Andrei

Jun 24 2016
On Friday, 24 June 2016 at 20:33:45 UTC, Andrei Alexandrescu
wrote:
In a checked environment, division may "overflow", e.g. -6 / 2u
must be typed as uint but is not representable properly one.

How about remainder? I suppose one can make the argument that
remainder should never overflow (save for rhs == 0), because it
could be defined with either a positive or negative denominator
(which is not part of the result).

What's the most reasonable behavior?

Andrei

Most reasonable is

numerator = quotient * divisor + remainder

Which means it can be negative.

Jun 24 2016
jmh530 <john.michael.hall gmail.com> writes:
On Friday, 24 June 2016 at 20:43:38 UTC, deadalnix wrote:
Most reasonable is

numerator = quotient * divisor + remainder

Which means it can be negative.

Example:

void main()
{
int x1 = 2;
int x2 = -2;
uint x3 = 2;

assert(-7 % x1 == -1);
assert(-7 % x2 == -1);
assert(-7 % x3 == -1); //fails
}

Jun 24 2016
On Friday, 24 June 2016 at 20:43:38 UTC, deadalnix wrote:
On Friday, 24 June 2016 at 20:33:45 UTC, Andrei Alexandrescu
wrote:
In a checked environment, division may "overflow", e.g. -6 /
2u must be typed as uint but is not representable properly one.

How about remainder? I suppose one can make the argument that
remainder should never overflow (save for rhs == 0), because
it could be defined with either a positive or negative
denominator (which is not part of the result).

What's the most reasonable behavior?

Andrei

Most reasonable is

numerator = quotient * divisor + remainder

Which means it can be negative.

This proves nothing.

Wiki:

For a ***positive integer n***, two integers a and b are said to
be congruent modulo n, written:

a ≡ b ( mod n ) , {\displaystyle a\equiv b{\pmod {n}},\,}
a\equiv b{\pmod {n}},\,

if their difference a − b is an integer multiple of n (or n
divides a − b). The number n is called the modulus of the
congruence.

For any "negative" remainder, all one has to do is subtract one
from the divisor:

quotient*(divisor - 1 + 1) + remainder
= quotient*new_divisor + pos_remainder

where new_divisor = divisor - 1, pos_remainder = quotient +
remainder

There are problems with allowing the remainder to be negative and
it is generally best to restrict it to positive values.

e.g., 129 = 2*52 + 25 OR 3*52 - 27.

In the second case, we have 129/52i = 3? Basically by restricting
to positive integers, we have a more natural interpretation and
relationship to floor and ceil functions and we don't have to
worry about it being negative(think of using in in an array
indexing scheme),

Jun 25 2016
On Saturday, 25 June 2016 at 23:01:00 UTC, "Smoke" Adams wrote:
This proves nothing.

This isn't a proof, this is a definition. This is the definition
that is used by all programming languages out there and all CPUs.
It isn't going to change because someone on the internet think he
has a better definition that provide no clear advantage over the
current one.

Jun 25 2016
On Sunday, 26 June 2016 at 00:31:29 UTC, deadalnix wrote:
On Saturday, 25 June 2016 at 23:01:00 UTC, "Smoke" Adams wrote:
This proves nothing.

This isn't a proof, this is a definition. This is the
definition that is used by all programming languages out there
and all CPUs. It isn't going to change because someone on the
internet think he has a better definition that provide no clear

Again, no proof at all and inaccurate. Not every programming
language or cpu does this. Please don't make up facts to support
your "definitions" and desires. Having a negative modulo is just
ignorant.

Jun 25 2016
On Sunday, 26 June 2016 at 02:05:53 UTC, "Smoke" Adams wrote:
On Sunday, 26 June 2016 at 00:31:29 UTC, deadalnix wrote:
On Saturday, 25 June 2016 at 23:01:00 UTC, "Smoke" Adams wrote:
This proves nothing.

This isn't a proof, this is a definition. This is the
definition that is used by all programming languages out there
and all CPUs. It isn't going to change because someone on the
internet think he has a better definition that provide no
clear advantage over the current one.

Again, no proof at all

Either can't read or you can't think. Which is it ?

and inaccurate. Not every programming language or cpu does
and desires. Having a negative modulo is just ignorant.

Languages:
C#: https://msdn.microsoft.com/en-us/library/0w4e0fzs.aspx
Java:
https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3
C11:
http://www.open-std.org/jtc1/sc22/wg14/www/docs/C99RationaleV5.10.pdf (See
6.5.5 for update on % operator, mentioning, example at 7.20.6).
Python2: https://docs.python.org/2/reference/expressions.html
Python3: https://docs.python.org/3/reference/expressions.html

CPUs:
Arm7(eeabi):
https://github.com/wayling/xboot-clone/blob/master/src/arch/arm/lib/gcc/__aeabi_idivmod.S
Arm7(Darwin):
http://opensource.apple.com//source/clang/clang-163.7.1/src/projects/compiler-rt/lib/arm/modsi3.S
Mips:
http://www.mrc.uidaho.edu/mrc/people/jff/digital/MIPSir.html (See
DIV instruction)
X86: http://x86.renejeschke.de/html/file_module_x86_id_137.html

Now I'm sure there are a weird CPU that isn't produced since the
80s and that D will never support that do it in some other way,
but for all platforms that matter today, this isn't the case.

This is not MY definition, this is the definition everybody
except you uses? Even PHP get this right
(http://php.net/manual/en/language.operators.arithmetic.php).

Now champion, what do you have supporting your definition ?

Jun 25 2016
On Sunday, 26 June 2016 at 03:54:28 UTC, deadalnix wrote:
On Sunday, 26 June 2016 at 02:05:53 UTC, "Smoke" Adams wrote:
On Sunday, 26 June 2016 at 00:31:29 UTC, deadalnix wrote:
On Saturday, 25 June 2016 at 23:01:00 UTC, "Smoke" Adams
wrote:
This proves nothing.

This isn't a proof, this is a definition. This is the
definition that is used by all programming languages out
there and all CPUs. It isn't going to change because someone
on the internet think he has a better definition that provide
no clear advantage over the current one.

Again, no proof at all

Either can't read or you can't think. Which is it ?

and inaccurate. Not every programming language or cpu does
and desires. Having a negative modulo is just ignorant.

Languages:
C#: https://msdn.microsoft.com/en-us/library/0w4e0fzs.aspx
Java:
https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3
C11:
http://www.open-std.org/jtc1/sc22/wg14/www/docs/C99RationaleV5.10.pdf (See
6.5.5 for update on % operator, mentioning, example at 7.20.6).
Python2: https://docs.python.org/2/reference/expressions.html
Python3: https://docs.python.org/3/reference/expressions.html

CPUs:
Arm7(eeabi):
https://github.com/wayling/xboot-clone/blob/master/src/arch/arm/lib/gcc/__aeabi_idivmod.S
Arm7(Darwin):
http://opensource.apple.com//source/clang/clang-163.7.1/src/projects/compiler-rt/lib/arm/modsi3.S
Mips:
http://www.mrc.uidaho.edu/mrc/people/jff/digital/MIPSir.html
(See DIV instruction)
X86: http://x86.renejeschke.de/html/file_module_x86_id_137.html

Now I'm sure there are a weird CPU that isn't produced since
the 80s and that D will never support that do it in some other
way, but for all platforms that matter today, this isn't the
case.

This is not MY definition, this is the definition everybody
except you uses? Even PHP get this right
(http://php.net/manual/en/language.operators.arithmetic.php).

Now champion, what do you have supporting your definition ?

Your a moron. I guess you think just because everyone believes in
Santa Clause it means he exists?

http://mathworld.wolfram.com/Congruence.html
https://en.wikipedia.org/wiki/Modulo_operation
https://en.wikipedia.org/wiki/Modular_arithmetic
http://stackoverflow.com/questions/1082917/mod-of-negative-number-is-melting-my-brain
https://www.securecoding.cert.org/confluence/pages/viewpage.action?pageId=6422581
http://www.mathworks.com/help/matlab/ref/mod.html?requestedDomain=www.mathworks.com

It's one thing to claim that the sign of the modulo is the same
as the sign of the divisor, but entirely different to claim the
modulo should be negative.

Of course, I don't expect a neanderthal like yourself to
understand that. Have fun lemming.

Oh, hey, I'm going to define that your an idiot! Thanks for
agreeing with me.

Jun 25 2016
Shachar Shemesh <shachar weka.io> writes:
What deadalnix (how did you choose a nickname that is more difficult to
write than your given name anyway?) said was that the definition of %
only makes sense if, for every n and every m:
(n/m)+(n%m)=n

What this means is that, if n/m is rounded up for negative numbers, n%m
must be negative.

Since n/m and n%m are, usually, implemented by the CPU's hardware,
performance dictates that we do whatever it is that the CPU is doing. On
most modern CPUs, n/m rounds up for negative results, and n%m is negative.

So, we can do it your way. This would mean:
1. Losing performance for every division and modulus that *might* be
negative
and
2. Being different than other programming languages out there

or we can do what we're doing.

Shachar

Jun 25 2016
Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 26 June 2016 at 05:28:53 UTC, Shachar Shemesh wrote:
So, we can do it your way. This would mean:
1. Losing performance for every division and modulus that
*might* be negative

I don't think the performance issue is relevant. It was relevant
when it was left implementation defined in C, but it is no longer
the case so it was defined to be consistent with signed integer
division in C-99. The sane thing to do from a system programming
point of view is to have strong typing and 3 versions:

1. "x % y" only defined on unsigned integers
2. rem(x,y) for reminder from truncated division
3. mod(x,y) for reminder from floored division

Unfortunately implictly casting ints to uints is a very bad idea
when you want a reasonably safe type-system.

Jun 26 2016
On Sunday, 26 June 2016 at 04:25:07 UTC, "Smoke" Adams wrote:
Languages:
C#: https://msdn.microsoft.com/en-us/library/0w4e0fzs.aspx
Java:
https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3
C11:
http://www.open-std.org/jtc1/sc22/wg14/www/docs/C99RationaleV5.10.pdf (See
6.5.5 for update on % operator, mentioning, example at 7.20.6).
Python2: https://docs.python.org/2/reference/expressions.html
Python3: https://docs.python.org/3/reference/expressions.html

CPUs:
Arm7(eeabi):
https://github.com/wayling/xboot-clone/blob/master/src/arch/arm/lib/gcc/__aeabi_idivmod.S
Arm7(Darwin):
http://opensource.apple.com//source/clang/clang-163.7.1/src/projects/compiler-rt/lib/arm/modsi3.S
Mips:
http://www.mrc.uidaho.edu/mrc/people/jff/digital/MIPSir.html
(See DIV instruction)
X86: http://x86.renejeschke.de/html/file_module_x86_id_137.html

Now I'm sure there are a weird CPU that isn't produced since
the 80s and that D will never support that do it in some other
way, but for all platforms that matter today, this isn't the
case.

This is not MY definition, this is the definition everybody
except you uses? Even PHP get this right
(http://php.net/manual/en/language.operators.arithmetic.php).

Now champion, what do you have supporting your definition ?

http://mathworld.wolfram.com/Congruence.html
https://en.wikipedia.org/wiki/Modulo_operation
https://en.wikipedia.org/wiki/Modular_arithmetic
http://stackoverflow.com/questions/1082917/mod-of-negative-number-is-melting-my-brain
https://www.securecoding.cert.org/confluence/pages/viewpage.action?pageId=6422581
http://www.mathworks.com/help/matlab/ref/mod.html?requestedDomain=www.mathworks.com

Except for mathematica, these are all irrelevant. The claim is
that programming languages and CPU define % in some way, not that
mathematician do it the same way.

Please read this again (you may want to use you finger to make
sure you) :

This isn't a proof, this is a definition. This is the
definition that is used by all programming languages out
there and all CPUs. It isn't going to change because someone
on the internet think he has a better definition that
provide no clear advantage over the current one.

You mention you had information supporting that this was not
true. It is very easy to debunk. You could for instance provide a
link to a CPU that do NOT do the % operation that way. I was able
to demonstrate to you that all major CPUs and many major
languages do it that way (see there is a claim and evidence to
support it, it is how arguing works). The best you've been able
to present is a DSL (mathematica) and no CPU.

Bonus points for the stackoverflow question, which isn't a spec
and supports my point: languages and CPU do it that way. Once
again, it is to wonder if you actually understand what you are
responding to.

Of course, I don't expect a neanderthal like yourself to
understand that. Have fun lemming.

Oh, hey, I'm going to define that your an idiot! Thanks for
agreeing with me.

I see I've hurt your feelings. That's ok, you'll survive. Next
time, try make sure to understand the difference between a
definition and a proof, and I won't have to point to you, and
your feeling won't be hurt next time.

Jun 25 2016
Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 26 June 2016 at 05:44:53 UTC, deadalnix wrote:
Except for mathematica, these are all irrelevant. The claim is
that programming languages and CPU define % in some way, not
that mathematician do it the same way.

Well, the CPU does not define it. It is just that C botchered it
by leaving "%" implementation defined up til 1999, where they
went with the truncated reminder and not the floored modulo
operator. In system level programming you usually need the modulo
(reminder for floored division) and not the C-style reminder
(reminder from truncated division):

https://en.wikipedia.org/wiki/Modulo_operation

Interestingly Simula, Ada, Fortran, Common Lisp and other high
level languages provids both "rem(x,y)" and "mod(x,y)", which is
the right thing to do.

Jun 26 2016
Guillaume Boucher <guillaume.boucher.d gmail.com> writes:
On Friday, 24 June 2016 at 20:43:38 UTC, deadalnix wrote:
Most reasonable is

numerator = quotient * divisor + remainder

Which means it can be negative.

Depends on the definition.

If division truncates towards negative infinity, the remainder
will always be nonegative (in case of a positive divisor).

I personally find rounding towards negative infinity the most
practical; every time I used modulo, I wanted the result to be in
the range [0, divisor).  Python does it this way and I find it
very convenient.

Jun 25 2016
Timon Gehr <timon.gehr gmx.ch> writes:
On 26.06.2016 02:54, Guillaume Boucher wrote:
On Friday, 24 June 2016 at 20:43:38 UTC, deadalnix wrote:
Most reasonable is

numerator = quotient * divisor + remainder

Which means it can be negative.

Depends on the definition.

If division truncates towards negative infinity, the remainder will
always be nonegative (in case of a positive divisor).

I personally find rounding towards negative infinity the most practical;
every time I used modulo, I wanted the result to be in the range [0,
divisor).  Python does it this way and I find it very convenient.

I agree, but unfortunately signed integer division in D follows C's
convention.

Jun 25 2016
Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 26 June 2016 at 00:54:04 UTC, Guillaume Boucher wrote:
If division truncates towards negative infinity, the remainder
will always be nonegative (in case of a positive divisor).

Or even better, use euclidean division, then the reminder always
remains non-negative:

https://en.wikipedia.org/wiki/Euclidean_division

Jun 26 2016
Timon Gehr <timon.gehr gmx.ch> writes:
On 24.06.2016 22:33, Andrei Alexandrescu wrote:
In a checked environment, division may "overflow", e.g. -6 / 2u must be
typed as uint but is not representable properly one.

How about remainder? I suppose one can make the argument that remainder
should never overflow (save for rhs == 0),

Well, actually, lhs % 0 should be equal to lhs... :-)

Division by the trivial ideal {0} leaves the ring structure intact, so
modular arithmetic modulo 0 is just regular arithmetic.

(But of course, the hardware traps, so it makes sense to just copy that
behavior.)

because it could be defined
with either a positive or negative denominator (which is not part of the
result).

What's the most reasonable behavior?
...

It should be consistent with whatever '/' does: a/b*b + a%b == a.

If this cannot be satisfied, it should 'overflow'. (As deadalnix also
suggested.)

Jun 24 2016