4 ms·

One subject that's pretty useful for programmers to understand reasonably well is numerical analysis, even if it's at a fairly basic level. It's amazing how qu

One subject that's pretty useful for programmers to understand reasonably well is numerical analysis, even if it's at a fairly basic level. It's amazing how quickly you run into problems in practice as soon as you try to do anything with floating point numbers. I didn't carefully read through the section on modular arithmetic, so maybe this is already there, but one thing worth noting that bites a lot of people is that using modular arithmetic for integer representations means that addition, subtraction, and multiplication work the same for signed and unsigned integers. This means that you can typically write arithmetic expressions involving these operations without worrying too much about whether things are being regarded as signed or unsigned at intermediate steps. As soon as you introduce division into the mix, though, the whole thing falls apart, and you have to be very careful about how the language is interpreting each subexpression.

enchiridion 6y ago
I'm not sure understand what you're saying with mod arithmetic. Can you provide an example?
- macmmajor 6y ago
  You can think of it as applying a mod operator after each operation. Say we wanted to work with mod 5 Then 6 + 8 = 14 = 4 mod 5
  - eru 6y ago
    Doesn't work for division. At least not in general in a naive fashion.
- BearsAreCool 6y ago
  Not OP, but I'll give it a shot. At a low level pretty much all standard integer math is mod arithmetic, typically mod 2^32 or 2^64 depending on if a computer is 32 or 64 bit. This means that when a number goes above this limit it "overflows" and only the part left after dividing by the mod size is left. Additionally, negative numbers are stored by essentially counting down from the maximum number that can be stored + 1, in scholarly terms this is the twos complement. For instance on a 32 bit system -7 as a signed integer would be stored identically to the unsigned integer (2^32)-7. For anyone new to programming, unsigned meaning an integer variable that can only be positive and signed being an integer variable that could be positive or negative. Now all of this combines to make addition, subtraction, and even multiplication essentially identical for signed and unsigned numbers. On an 8 bit system (so integers can be between 0 to 255 inclusive) you could be trying to add the signed number 40 and the unsigned number 200. Naturally, this is 200+40 or 240. Now inside the computer, 240 is stored in the exact same way that -16 is so it is important that the software knows the correct way to handle the variable. This is equivalent to subtracting 56 from 40, and the signed integer -56 is represented in the exact same way as the unsigned integer 200. Now this is where it starts to get crazy. What if you add the signed integer -5 (represented by 251 in the unsigned world) and the unsigned integer 100? Well it is equivalent to 251 + 100 = 351. However, now we encounter modular arithmetic, because this is an 8 bit system and the maximum value for an integer is 255 we calculate everythihg mod 256, so ar left with 351 % 256 = 95. You can mentally view this as the calculation occurring with 1s and 0s, where everytime a 1 is added to a 1, there is a single bit carried and the last bit is dropped, which is exactly how full and half adders work in a processor! This also works for multiplication! If we multiply -5 by 5, we get -25 easily. But for computers we do 251 * 5 = 1255. The modulo math starts to get tricky for us puny humans but for a computer it is trivial, 1255 % 256 = 231. As a signed integer that is equal to -25, as it is equivalent to (255+1-25). For division, everything is just crazy. 250/5 is way different than -5/5, no amount if mod arithmetic will save it. Unsigned 50 and signed -1 have completely different representations, and this is even an example without fractions and rounding. I may have went long winded, but hopefully this helps someone!
  - fmi11 6y ago
    You're a cool bear! Thanks for the detailed explanation!
  - eru 6y ago
    Purely on the mathematical side, you can define division as the inverse of multiplication, and then when you are working modulo a prime number, division works just fine. (But computers usually don't implement it that way.) As an example when working modulo 17 and you want to work out what division by 3 means. You want to solve equations like: x * 3 = 10 (mod 17). For this case, x = 9; because 9 * 3 = 27 = 10 (mod 17). In general when working modulo 17, 6 is the multiplicative inverse of 3. Ie 6 * 3 = 1. Thanks to Fermat's Little Theorem you can find multiplicative inverses very easily, y^(p-2) mod p gives you the inverse of y. (Most programming languages won't know that you are going to apply a mod afterwards, so they just give you eg rounded or truncated integer division. Which is completely different in general.)
    - Tainnor 6y ago
      Sure, but computer arithmetic is modulo some power of two, which is not a prime. So you don't get a proper field and in particular, all even numbers don't have an inverse.
      - threatofrain 6y ago
        Huh? GF(2) is the smallest finite field, and 2 is a prime...? 0 is also excluded when we’re talking about multiplicative inverses.
        Tainnor 6y ago
        Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1". Now I'm not aware of any language where there is an integer type that has only two elements, unless you're talking about booleans - but booleans are so special that, while they're of course isomorphic to GF(2), we don't really use the same words (addition and multiplication) but different ones (exclusive disjunction (xor) and conjunction (and)). So, in any real-life situation, your fixed-size integers won't form a field, because the ring of integers modulo n is only a field when n is prime, and so in particular, division by nonzero elements will be undefined in general. And yes, of course, you can't divide by zero, but that's also true of the real numbers themselves, so no surprises there... (I guess a better point would be that division is mathematically "broken" for integers anyway, since integers technically also don't form a field and, depending on the language, you may either get back a truncated result from division or will get a different type (ratio or floating point).)
- alblue 6y ago
  You probably do this all the time with time without realising it. If it’s 11 o’clock and we agree to meet in two hours, you instinctively know I’m talking about 1 o’clock. But what you’ve just done is add two numbers mod(ulus) 12. In effect your brain added 11+2 to get 13, then took away 12 to make it fit, and came up with the modulus (or remainder) of 1. Modulus arithmetic is therefore sometimes known as clock arithmetic.
  - mbeex 6y ago
    > In effect your brain added 11+2 to get 13, then took away 12 to make it fit Not my German brain. But mod 24, I'm with you again :) And don't let me start with the Russians, they did it in hardware: https://en.wikipedia.org/wiki/24-hour_analog_dial#/media/File:Raketa-24h-ghiera-ore.jpg https://en.wikipedia.org/wiki/24-hour_analog_dial#/media/Fil...
eru 6y ago
If you are using C or C++, you need to be extremely careful with signed integers, even when working modulo. Their overflow is undefined.
- boston_clone 6y ago
  Is that due to the division taking place like the parent mentions, or something else?
  - eru 6y ago
    Due to how C and C++ are defined in their standards. The reason behind that is so that the compiler is allowed to assume that expressions like (x + 1 > x) are true, and thus can optimise more.

enchiridion 6y ago

I'm not sure understand what you're saying with mod arithmetic. Can you provide an example?

macmmajor 6y ago
You can think of it as applying a mod operator after each operation. Say we wanted to work with mod 5 Then 6 + 8 = 14 = 4 mod 5
- eru 6y ago
  Doesn't work for division. At least not in general in a naive fashion.
BearsAreCool 6y ago
Not OP, but I'll give it a shot. At a low level pretty much all standard integer math is mod arithmetic, typically mod 2^32 or 2^64 depending on if a computer is 32 or 64 bit. This means that when a number goes above this limit it "overflows" and only the part left after dividing by the mod size is left. Additionally, negative numbers are stored by essentially counting down from the maximum number that can be stored + 1, in scholarly terms this is the twos complement. For instance on a 32 bit system -7 as a signed integer would be stored identically to the unsigned integer (2^32)-7. For anyone new to programming, unsigned meaning an integer variable that can only be positive and signed being an integer variable that could be positive or negative. Now all of this combines to make addition, subtraction, and even multiplication essentially identical for signed and unsigned numbers. On an 8 bit system (so integers can be between 0 to 255 inclusive) you could be trying to add the signed number 40 and the unsigned number 200. Naturally, this is 200+40 or 240. Now inside the computer, 240 is stored in the exact same way that -16 is so it is important that the software knows the correct way to handle the variable. This is equivalent to subtracting 56 from 40, and the signed integer -56 is represented in the exact same way as the unsigned integer 200. Now this is where it starts to get crazy. What if you add the signed integer -5 (represented by 251 in the unsigned world) and the unsigned integer 100? Well it is equivalent to 251 + 100 = 351. However, now we encounter modular arithmetic, because this is an 8 bit system and the maximum value for an integer is 255 we calculate everythihg mod 256, so ar left with 351 % 256 = 95. You can mentally view this as the calculation occurring with 1s and 0s, where everytime a 1 is added to a 1, there is a single bit carried and the last bit is dropped, which is exactly how full and half adders work in a processor! This also works for multiplication! If we multiply -5 by 5, we get -25 easily. But for computers we do 251 * 5 = 1255. The modulo math starts to get tricky for us puny humans but for a computer it is trivial, 1255 % 256 = 231. As a signed integer that is equal to -25, as it is equivalent to (255+1-25). For division, everything is just crazy. 250/5 is way different than -5/5, no amount if mod arithmetic will save it. Unsigned 50 and signed -1 have completely different representations, and this is even an example without fractions and rounding. I may have went long winded, but hopefully this helps someone!
- fmi11 6y ago
  You're a cool bear! Thanks for the detailed explanation!
- eru 6y ago
  Purely on the mathematical side, you can define division as the inverse of multiplication, and then when you are working modulo a prime number, division works just fine. (But computers usually don't implement it that way.) As an example when working modulo 17 and you want to work out what division by 3 means. You want to solve equations like: x * 3 = 10 (mod 17). For this case, x = 9; because 9 * 3 = 27 = 10 (mod 17). In general when working modulo 17, 6 is the multiplicative inverse of 3. Ie 6 * 3 = 1. Thanks to Fermat's Little Theorem you can find multiplicative inverses very easily, y^(p-2) mod p gives you the inverse of y. (Most programming languages won't know that you are going to apply a mod afterwards, so they just give you eg rounded or truncated integer division. Which is completely different in general.)
  - Tainnor 6y ago
    Sure, but computer arithmetic is modulo some power of two, which is not a prime. So you don't get a proper field and in particular, all even numbers don't have an inverse.
    - threatofrain 6y ago
      Huh? GF(2) is the smallest finite field, and 2 is a prime...? 0 is also excluded when we’re talking about multiplicative inverses.
      - Tainnor 6y ago
        Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1". Now I'm not aware of any language where there is an integer type that has only two elements, unless you're talking about booleans - but booleans are so special that, while they're of course isomorphic to GF(2), we don't really use the same words (addition and multiplication) but different ones (exclusive disjunction (xor) and conjunction (and)). So, in any real-life situation, your fixed-size integers won't form a field, because the ring of integers modulo n is only a field when n is prime, and so in particular, division by nonzero elements will be undefined in general. And yes, of course, you can't divide by zero, but that's also true of the real numbers themselves, so no surprises there... (I guess a better point would be that division is mathematically "broken" for integers anyway, since integers technically also don't form a field and, depending on the language, you may either get back a truncated result from division or will get a different type (ratio or floating point).)
alblue 6y ago
You probably do this all the time with time without realising it. If it’s 11 o’clock and we agree to meet in two hours, you instinctively know I’m talking about 1 o’clock. But what you’ve just done is add two numbers mod(ulus) 12. In effect your brain added 11+2 to get 13, then took away 12 to make it fit, and came up with the modulus (or remainder) of 1. Modulus arithmetic is therefore sometimes known as clock arithmetic.
- mbeex 6y ago
  > In effect your brain added 11+2 to get 13, then took away 12 to make it fit Not my German brain. But mod 24, I'm with you again :) And don't let me start with the Russians, they did it in hardware: https://en.wikipedia.org/wiki/24-hour_analog_dial#/media/File:Raketa-24h-ghiera-ore.jpg https://en.wikipedia.org/wiki/24-hour_analog_dial#/media/Fil...

eru 6y ago

If you are using C or C++, you need to be extremely careful with signed integers, even when working modulo. Their overflow is undefined.

boston_clone 6y ago
Is that due to the division taking place like the parent mentions, or something else?
- eru 6y ago
  Due to how C and C++ are defined in their standards. The reason behind that is so that the compiler is allowed to assume that expressions like (x + 1 > x) are true, and thus can optimise more.