www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Should % ever "overflow"?

reply 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
next sibling parent reply deadalnix <deadalnix gmail.com> writes:
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
next sibling parent 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
prev sibling next sibling parent reply "Smoke" Adams <SA2432 gmail.com> writes:
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
parent reply deadalnix <deadalnix gmail.com> writes:
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
parent reply "Smoke" Adams <SA2432 gmail.com> writes:
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 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
parent reply deadalnix <deadalnix gmail.com> writes:
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 
 this. Please don't make up facts to support your "definitions" 
 and desires. Having a negative modulo is just ignorant.


Languages:
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
parent reply "Smoke" Adams <SA2432 gmail.com> writes:
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 
 this. Please don't make up facts to support your "definitions" 
 and desires. Having a negative modulo is just ignorant.


 Languages:
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
next sibling parent reply 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
parent 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
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
On Sunday, 26 June 2016 at 04:25:07 UTC, "Smoke" Adams wrote:

 Languages:
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
parent 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
prev sibling parent reply 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
next sibling parent 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
prev sibling parent 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
prev sibling parent 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