## 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
- deadalnix (26/40) Jun 25 2016 Languages:
- Smoke (16/59) Jun 25 2016 Your a moron. I guess you think just because everyone believes in
- Shachar Shemesh (16/16) Jun 25 2016 What deadalnix (how did you choose a nickname that is more difficult to
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (11/14) Jun 26 2016 I don't think the performance issue is relevant. It was relevant
- deadalnix (21/65) Jun 25 2016 Except for mathematica, these are all irrelevant. The claim is
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (11/14) Jun 26 2016 Well, the CPU does not define it. It is just that C botchered it
- Guillaume Boucher (8/11) Jun 25 2016 Depends on the definition.
- Timon Gehr (3/15) Jun 25 2016 I agree, but unfortunately signed integer division in D follows C's
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (4/6) Jun 26 2016 Or even better, use euclidean division, then the reminder always
- Timon Gehr (9/18) Jun 24 2016 Well, actually, lhs % 0 should be equal to lhs... :-)

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? AndreiMost reasonable is numerator = quotient * divisor + remainder Which means it can be negative.

Jun 24 2016

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: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),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? AndreiMost reasonable is numerator = quotient * divisor + remainder Which means it can be negative.

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: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.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 02:05:53 UTC, "Smoke" Adams wrote:On Sunday, 26 June 2016 at 00:31:29 UTC, deadalnix wrote:Either can't read or you can't think. Which is it ?On Saturday, 25 June 2016 at 23:01:00 UTC, "Smoke" Adams wrote:Again, no proof at allThis 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.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

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: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.On Sunday, 26 June 2016 at 00:31:29 UTC, deadalnix wrote:Either can't read or you can't think. Which is it ?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.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

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

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 negativeI 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: 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.comExcept 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) :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.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.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

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

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

On 26.06.2016 02:54, Guillaume Boucher wrote:On Friday, 24 June 2016 at 20:43:38 UTC, deadalnix wrote:I agree, but unfortunately signed integer division in D follows C's convention.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

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

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