Re: Should % ever "overflow"?
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
Re: Should % ever "overflow"?
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.
Re: Should % ever "overflow"?
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.
Re: Should % ever "overflow"?
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.
Re: Should % ever "overflow"?
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
Re: Should % ever "overflow"?
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.
Re: Should % ever "overflow"?
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 ?
Re: Should % ever "overflow"?
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.
Re: Should % ever "overflow"?
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.
Re: Should % ever "overflow"?
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.
Re: Should % ever "overflow"?
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.
Re: Should % ever "overflow"?
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),
Re: Should % ever "overflow"?
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.)
Re: Should % ever "overflow"?
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
}
Re: Should % ever "overflow"?
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.
Should % ever "overflow"?
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
