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: 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
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: 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
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:
 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
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