8 ms·

Doesn’t C just do whatever the underlying hardware does for modulo w negative numbers? I have always worked around this by adding N to numerator: r = (i +

Doesn’t C just do whatever the underlying hardware does for modulo w negative numbers? I have always worked around this by adding N to numerator: r = (i + N) % N which handles cases where i >= -N which is mostly what I run into when i is negative. I remember Ada having two different operators REM and MOD which I think is the best language choice.

Someone 5y ago
In C this used to be “implementation defined”. That changed in C99 and C++11 (https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages https://en.wikipedia.org/wiki/Modulo_operation#In_programmin..., note c) Nitpick: it never was “just do whatever the underlying hardware does”. C standards try hard to avoid mentioning hardware at all (and, as far as I know, succeed at that), and there’s plenty of hardware that doesn’t do mod in hardware, yet supports it in C.
- beervirus 5y ago
- gmiller123456 5y ago
  You make a good point, but I think he was more generalizing to actual implementations of C compilers. And that does align with my experience.
- alerighi 5y ago
  In C there are ton of things that are hardware dependent. For example the size of every data type is not specified, or the fact that char is signed or unsigned, the representation of signed integers (tough I don't think there still exist a platform that doesn't use 2's complement), ad a ton of other things.
  - deleted 5y ago
    [deleted]
  - quietbritishjim 5y ago
    I think there parent comment just meant that implementation dependent is technically not the same as hardware dependent. For example, the size of int is not specified by the standard, as you said. But it can still be different from the natural word size of the underlying hardware, if the compiler vendor chooses to make it so. Case in point is int on 64-bit platforms is usually 32-bit in practice. In Microsoft's compiler, even long int is 32-bit even on 64-bit hardware.
kevin_thibedeau 5y ago
> I remember Ada having two different operators REM and MOD Taken from Modula-2.
scotty79 5y ago
Not if i is less than -N. Modulo operator that wraps -1 to N-1 would be waay better.
deleted 5y ago
[deleted]
MobiusHorizons 5y ago
Btw that code won’t work in the general case (where i could be less than -N). For that case you should probably do r = ((i % N) + N) % N There may be faster ways, but that should at least be correct for all inputs.
- klodolph 5y ago
  Incorrect for N > INT_MAX/2.
  - MobiusHorizons 5y ago
    I'm not sure I follow. If defined as ``` int16_t mod(int16_t i, int16_t N) { return ((i % N) + N) % N; } ``` There do not seem to be any issues all the way up to INT16_MAX. Even with negative values of N, it produces the same value as python does (although I am not certain I understand what modulus means with a negative N)
    - klodolph 5y ago
      Let i=INT_MAX-1, N=INT_MAX. i%N is just i, and then (i%N)+N overflows. The result is undefined. Even on systems where it is defined, the typical result would be incorrect. It’s a bit weird that you chose int16_t for your example… it’s the kind of thing you might do if you were trying to make some point about different integer types, but you didn’t give a reason for using int16_t, so the point is lost. I can’t read your mind.
      - MobiusHorizons 5y ago
        I chose int16 just to make it easier to write an exhaustive search. That is where my assertion that the code works correctly comes from. The case you suppose makes sense, but for some reason does not produce incorrect results when I run it, for instance: N = INT16_MAX - 2: mod(32762, 32765) = 32762 mod(32763, 32765) = 32763 mod(32764, 32765) = 32764 mod(32765, 32765) = 0 mod(32766, 32765) = 1 mod(32767, 32765) = 2 I wonder if the compiler just used the full register. I'll have to check the disassembly.
masklinn 5y ago
> I remember Ada having two different operators REM and MOD which I think is the best language choice. According to Boute 1992, > The Ada Reference Manual complements integer division (/) with two functions mod and rem. The first of these violates the division rule so it doesn't so much have two different operators as one operator and one broken mess, and its one operator is the truncating division (C-style). Also a quick check of the Hyperspec (or, again, Boute 1992) shows there are not two but 4 definitions based on rounding quotients, I think none of which "always returns a positive number" (which Python also does not do, incidentally). There is a 5th definition, which Boute 1992 champions, for which the property asserted in the title holds.
pyjarrett 5y ago
Ada mod takes the sign of the second operand. I wouldn't even bother with this, I'd just use a modular type (i.e. unsigned). with Ada.Text_IO; procedure Main is -- Modular type (unsigned) which can take values of [0, 15]. type Nibble is mod 16; Value : Nibble := 0; begin -- Prints 0 3 6 9 12 15 2 5 8 11 14 1 4 7 10 13 ... for I in 0 .. 63 loop Ada.Text_IO.Put_Line (Value'Image); Value := Value + 3; end loop; end Main; Then make that type the index into my circular buffer and then I never need to worry about it. type Circular_Buffer is array (Nibble) of Integer; Buffer : Circular_Buffer;
strenholme 5y ago
In C99, the modulo operator is defined thusly: “If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a” Source: The draft C99 standard http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf PDF page 94, physical page 82. Yes, as someone who both gets open source bug reports and has sent out open source bug reports, what determines whether a behavior being looked at is a bug depends on what the relevant standards say.
- __s 5y ago
  Meanwhile, C89: https://port70.net/~nsz/c/c89/c89-draft.html#3.3.5 https://port70.net/~nsz/c/c89/c89-draft.html#3.3.5 > When integers are divided and the division is inexact, if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than the algebraic quotient or the smallest integer greater than the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a .
  - strenholme 5y ago
    Between C89 and C99, the standard was updated to require integer division to truncate towards 0. C99 draft standard: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf PDF page 94, physical page 82, “When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.” with a footnote: “This is often called ‘‘truncation toward zero’’” I wish % was a modulo instead of a remainder operation; this bug has bitten me more than once.

Someone 5y ago

In C this used to be “implementation defined”. That changed in C99 and C++11 (https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages https://en.wikipedia.org/wiki/Modulo_operation#In_programmin..., note c) Nitpick: it never was “just do whatever the underlying hardware does”. C standards try hard to avoid mentioning hardware at all (and, as far as I know, succeed at that), and there’s plenty of hardware that doesn’t do mod in hardware, yet supports it in C.

beervirus 5y ago
gmiller123456 5y ago
You make a good point, but I think he was more generalizing to actual implementations of C compilers. And that does align with my experience.
alerighi 5y ago
In C there are ton of things that are hardware dependent. For example the size of every data type is not specified, or the fact that char is signed or unsigned, the representation of signed integers (tough I don't think there still exist a platform that doesn't use 2's complement), ad a ton of other things.
- deleted 5y ago
  [deleted]
- quietbritishjim 5y ago
  I think there parent comment just meant that implementation dependent is technically not the same as hardware dependent. For example, the size of int is not specified by the standard, as you said. But it can still be different from the natural word size of the underlying hardware, if the compiler vendor chooses to make it so. Case in point is int on 64-bit platforms is usually 32-bit in practice. In Microsoft's compiler, even long int is 32-bit even on 64-bit hardware.

kevin_thibedeau 5y ago

> I remember Ada having two different operators REM and MOD Taken from Modula-2.

scotty79 5y ago

Not if i is less than -N. Modulo operator that wraps -1 to N-1 would be waay better.

deleted 5y ago

[deleted]

MobiusHorizons 5y ago

Btw that code won’t work in the general case (where i could be less than -N). For that case you should probably do r = ((i % N) + N) % N There may be faster ways, but that should at least be correct for all inputs.

klodolph 5y ago
Incorrect for N > INT_MAX/2.
- MobiusHorizons 5y ago
  I'm not sure I follow. If defined as ``` int16_t mod(int16_t i, int16_t N) { return ((i % N) + N) % N; } ``` There do not seem to be any issues all the way up to INT16_MAX. Even with negative values of N, it produces the same value as python does (although I am not certain I understand what modulus means with a negative N)
  - klodolph 5y ago
    Let i=INT_MAX-1, N=INT_MAX. i%N is just i, and then (i%N)+N overflows. The result is undefined. Even on systems where it is defined, the typical result would be incorrect. It’s a bit weird that you chose int16_t for your example… it’s the kind of thing you might do if you were trying to make some point about different integer types, but you didn’t give a reason for using int16_t, so the point is lost. I can’t read your mind.
    - MobiusHorizons 5y ago
      I chose int16 just to make it easier to write an exhaustive search. That is where my assertion that the code works correctly comes from. The case you suppose makes sense, but for some reason does not produce incorrect results when I run it, for instance: N = INT16_MAX - 2: mod(32762, 32765) = 32762 mod(32763, 32765) = 32763 mod(32764, 32765) = 32764 mod(32765, 32765) = 0 mod(32766, 32765) = 1 mod(32767, 32765) = 2 I wonder if the compiler just used the full register. I'll have to check the disassembly.

masklinn 5y ago

> I remember Ada having two different operators REM and MOD which I think is the best language choice. According to Boute 1992, > The Ada Reference Manual complements integer division (/) with two functions mod and rem. The first of these violates the division rule so it doesn't so much have two different operators as one operator and one broken mess, and its one operator is the truncating division (C-style). Also a quick check of the Hyperspec (or, again, Boute 1992) shows there are not two but 4 definitions based on rounding quotients, I think none of which "always returns a positive number" (which Python also does not do, incidentally). There is a 5th definition, which Boute 1992 champions, for which the property asserted in the title holds.

pyjarrett 5y ago

Ada mod takes the sign of the second operand. I wouldn't even bother with this, I'd just use a modular type (i.e. unsigned). with Ada.Text_IO; procedure Main is -- Modular type (unsigned) which can take values of [0, 15]. type Nibble is mod 16; Value : Nibble := 0; begin -- Prints 0 3 6 9 12 15 2 5 8 11 14 1 4 7 10 13 ... for I in 0 .. 63 loop Ada.Text_IO.Put_Line (Value'Image); Value := Value + 3; end loop; end Main; Then make that type the index into my circular buffer and then I never need to worry about it. type Circular_Buffer is array (Nibble) of Integer; Buffer : Circular_Buffer;

strenholme 5y ago

In C99, the modulo operator is defined thusly: “If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a” Source: The draft C99 standard http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf PDF page 94, physical page 82. Yes, as someone who both gets open source bug reports and has sent out open source bug reports, what determines whether a behavior being looked at is a bug depends on what the relevant standards say.

__s 5y ago
Meanwhile, C89: https://port70.net/~nsz/c/c89/c89-draft.html#3.3.5 https://port70.net/~nsz/c/c89/c89-draft.html#3.3.5 > When integers are divided and the division is inexact, if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than the algebraic quotient or the smallest integer greater than the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a .
- strenholme 5y ago
  Between C89 and C99, the standard was updated to require integer division to truncate towards 0. C99 draft standard: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf PDF page 94, physical page 82, “When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.” with a footnote: “This is often called ‘‘truncation toward zero’’” I wish % was a modulo instead of a remainder operation; this bug has bitten me more than once.