Answers.Body: <p>A specific example that I've used the mod operator before for (and have seen it used in production code this way) is to represent a higher dimensional array (usually 2D, but higher is possible) as a one dimensional array, and then use some modular arithmetic to retrieve the higher dimensional structure. The reason one might want to do this is if your array structure is a substructure of a more complex object, it might be simpler to implement it one dimensionally, and then add more complexity onto that. </p>
  
  <p>I've seen this done when one is "tiling" some 2D space, where each tile maps to some properties, <em>and</em> where each tile's properties may change in time. This could end up being a very complex structure: potentially, a mapping from time, to the first dimension of the tile, to the second dimension of the tile, to each of the properties of the tile. In such a case, the geometric "2D"-ness of the tiling may not be that important (except for perhaps the display), and so the implementation of the internal model of these tiles could be one dimensional instead, simplifying our model. </p>
  
  <p>Here's a simple 2D array example. Say one has a <code>3</code> by <code>3</code> array, where the "property" is represented by some integer:</p>
  
  <pre><code>1 4 9
  
  0 2 7
  
  5 6 4
  </code></pre>
  
  <p>Our 2d array may be indexed with <code>[row, column]</code> as follows:</p>
  
  <pre><code>[0,0] [0,1] [0,2]
  
  [1,0] [1,1] [1,2]
  
  [2,0] [2,1] [2,2]
  </code></pre>
  
  <p>However, we <em>can</em> represent it with only a single parameter as:</p>
  
  <pre><code>0 1 2
  
  3 4 5
  
  6 7 8
  </code></pre>
  
  <p>(left to right, then top to bottom is just a convention of course)</p>
  
  <p>Now, how do we retrieve the row and column numbers given one of these indices? This shows some nice symmetry between the <code>/</code> operator (that is, truncated division on integers) and the <code>%</code> operator. </p>
  
  <p>If we're indexing rows and columns as in my first example, the "row number" of an index <code>i</code> above is given by <code>i / 3</code> (again, truncated), and the "column number" of an index <code>i</code> above is given by <code>i % 3</code>. </p>
  
  <p>In general, if you have an <code>n</code> by <code>n</code> array, and you index it as I did above, the row number is given by <code>i / n</code> and the column number is given by <code>i % n</code>. </p>
  
  <p>Another example, and this one gets closer to the intuition you're trying to achieve, is simplifying computations for cyclic functions. If your functions are over the integers, then your operator <code>%</code> is good enough. However, this wouldn't work for continuous functions. Nicely enough, one can take your discrete cyclic model and make it continuous in programming languages by using <code>fmod</code> or an equivalent. </p>
  
  <p>Specifically, for students with enough background in Calculus that have some familiarity with Taylor series, one can think of how one would write a trig function like cosine. One might realize that the 6th degree Taylor polynomial approximation is "close enough" in the range between $- \pi/2$ to $\pi/2$. Then, one can "mirror" that to get one complete cycle of the cosine curve between $-\pi/2$ and $3\pi/2$ (for example.) Then, with this, one might ask how one would compute the value of $cosine$ for <em>any</em> real number, and the answer is quickly obtained by using some modular arithmetic to get your number in that range, and then use our restricted cosine function for that translated number. </p>
  
  <p>This use of mod also relates to <a href="https://cseducators.stackexchange.com/a/4128/27">Guy Coder's answer</a>: thinking of taking the mod of a number as involving several subtractions is precisely how one might implement the continuous <code>fmod</code> function (however, whereas a discrete mod function's usual "remainder" intuition may be lost here, the intuition regarding the cyclical nature of mod should be strengthened). </p>
  
  <p>In general, I like to think that the kind of mental modeling required to think about mods is going to help these students regardless of whether they literally use them later on in their programming careers.  </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-10T23:29:57.453Z
Answers.Text: Welcome to [cseducators.se]. This is a breathtaking answer.  There is much to think about in here!
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-10T23:04:57.330Z
Answers.LastActivityDate: 2018-01-10T23:29:02.627Z
Answers.LastEditDate: 2018-01-10T23:29:02.627Z
Answers.UserDisplayName: Umer Amjad
Answers.Body: <blockquote>
    <p>How far should modular arithmetic be taken in the CS classes that are
    early enough along in the curriculum that they still focus on
    programming?</p>
  </blockquote>
  
  <p>I view the <code>mod</code> or <code>modulus</code> operator as any other operator that is new to the students. Even though <code>mod</code> is used more often when programming because it results in an integer value which is much more friendly to work with than a mantissa of a real division, I see no reason early on to spend any more time than is necessary to get the idea of how the mod function/operator works.</p>
  
  <p>When students are introduced to the mod operator for the first time it can be confusing. To make it easer for them I tell them that just because it is named <code>mod</code> doesn't mean you have to create a new idea in your head to understand it. Instead just think of it as the <code>remainder</code>, but when you talk to others programmers you have to use the word <code>mod</code> or <code>modulus</code> as that is the currently accepted name. They like that and we only spend a few minutes on it. I obviously show them how it relates to float division and integer division by listing examples of <code>float division</code>, <code>integer division</code> and <code>modulus</code>.  </p>
  
  <p>Also if a student says <code>remainder</code> in class I just ask <code>Did you mean mod?</code> and if they say yes we keep going. If they say no then I ask what they mean. If they are getting it wrong I do a quick review. Most students get it rather quickly but do say <code>remainder</code> more often at first but quickly get to using <code>mod</code> or <code>modulus</code>. </p>
  
  <p>If I do have to go over the concept again for some students I do use the concept of having items in my hand and do multiple subtractions until I have just the remainder. When I can subtract no more I ask them what do I have left and they give me an integer number and I say that is the <code>mod</code> value. Haven't had anyone get it wrong after they repeat that exercise back with them holding the items and doing the repeated subtractions, e.g.</p>
  
  <p>1 % 3<br>
  I have 1 item in my hand,<br>
  Can I subtract 3: <code>No</code><br>
  What do I have left: <code>1</code><br>
  That is the mod value  </p>
  
  <p>5 % 3<br>
  I have 5 items in my hand,<br>
  Can I subtract 3: <code>Yes</code><br>
  Now I have 2.<br>
  Can I subtract 3: <code>No</code><br>
  What do I have left: <code>2</code><br>
  That is the mod value  </p>
  
  <p>7 % 3<br>
  I have 7 items in my hand,<br>
  Can I subtract 3: <code>Yes</code><br>
  Now I have 4.<br>
  Can I subtract 3: <code>Yes</code><br>
  Now I have 1.<br>
  Can I subtract 3: <code>No</code><br>
  What do I have left: <code>1</code><br>
  That is the mod value </p>
  
  <p>0 % 2<br>
  I have 0 items in my hand,<br>
  Can I subtract 2: <code>No</code><br>
  What do I have left: <code>0</code><br>
  That is the mod value </p>
  
  <p>1 % 2<br>
  I have 1 item in my hand,<br>
  Can I subtract 2: <code>No</code><br>
  What do I have left: <code>1</code><br>
  That is the mod value </p>
  
  <p>4 % 2<br>
  I have 4 items in my hand,<br>
  Can I subtract 2: <code>Yes</code><br>
  Now I have 2.<br>
  Can I subtract 2: <code>Yes</code><br>
  Now I have 0.<br>
  Can I subtract 2: <code>No</code><br>
  What do I have left: <code>0</code><br>
  That is the mod value   </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-05T18:04:34.910Z
Answers.LastActivityDate: 2018-01-07T14:22:37.460Z
Answers.LastEditDate: 2018-01-07T14:22:37.460Z
Answers.UserDisplayName: Guy Coder
Body: <p>I'm sure that basically every introductory course involves teaching about the ubiquitous mod operation.  In my experience, and I'm sure I'm not alone in this, I've found that teaching my students that "mod is the remainder of division" is insufficient if I want them to make any use of the concept later on.</p>
  
  <p>Beyond showing them how to use mod to check divisibility, I have for the last few years gone into far more interesting operations in order to help them achieve some intuitive understanding of what mod is and how it works.  So, for instance, I show them how they can increment within a modular circle of numbers from <code>0</code> to <code>n-1</code> (a circle of size <code>n</code>):</p>
  
  <pre><code>[some loop structure] {
      x = (x+1)%n;
  }
  </code></pre>
  
  <p>Or, how to move that circle along so that it ranges from <code>m</code> to <code>(m+n-1)</code> (still a circle of size <code>n</code>, but it no longer starts at <code>0</code>):</p>
  
  <pre><code>[some loop structure] {
      x = (x+1-m)%n+m;
  }
  </code></pre>
  
  <p>Or how to decrement along a <code>0</code> to <code>n-1</code> circle in a language like Java, which deals with negative modular operations by returning the highest negative congruence (ie. <code>-10 % 4</code> would return <code>-2</code> instead of <code>2</code>.  While they are both technically correct answers, Java's answer is decidedly inconvenient for the purpose of moving along a modular circle of numbers, because when you try to move from 0 back to <code>n-1</code>, you get the wrong result.)</p>
  
  <pre><code>[some loop structure] {
      x = (((x-1)%n)+n)%n;
  }
  </code></pre>
  
  <p>Or, doing the same thing by moving <code>n-1</code> steps clockwise around the circle instead of moving <code>1</code> step counterclockwise:</p>
  
  <pre><code>[some loop structure] {
      x = (x+n-1)%n;
  }
  </code></pre>
  
  <p>And, of course, we can generalize this to involve any cyclical pattern of numbers that can be reduced to a proper modular circle where $f(n)$ is the function that takes any number within the cycle to its corresponding location in the modular circle, and $g(n)$ is the function that takes it back:</p>
  
  <pre><code>[some loop structure] {
      x = g(f(x+1)%n);
  }
  </code></pre>
  
  <p>Now, I am reasonable certain that nobody uses structures like this in any production environment.  Part of my justification for going to such lengths with mod operators has been that I am not a teacher of software engineering.  I am a teacher of computer science, and having a firm understanding of modular arithmetic is important for Some Big Ideas later on.  (Like Two's Complement, which has a very intuitive and coherent explanation when you think about it in terms of cycles within a number space.)  And when all is said and done, many of my students really do come out with a good, intuitive sense of how the mod operation works.</p>
  
  <p>But I also wonder if I have just gone plum crazy.  This stuff takes a lot of class time to get the kids to master, and I'm really wondering if the time would be better spent on other pursuits.</p>
  
  <p><strong>How far should modular arithmetic be taken in the CS classes that are early enough along in the curriculum that they still focus on programming?</strong></p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-04T21:09:19.947Z
Comments.Text: You can show them the more advanced examples without expecting them to reproduce them on a test. That way you open the door for interested students but don't overwhelm everybody else.
Comments.UserDisplayName: Kevin Workman
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-04T21:28:17.053Z
Comments.Text: @KevinWorkman That's a good solution, but I still don't know where to draw the line. Also, I'm not sure if I'm missing other (more important) examples.
Comments.UserDisplayName: Ben I.
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-05T11:17:40.137Z
Comments.Text: @BenI : when n is a power of 2, bit-masking does the trick at very low cost. But the consideration is more relevant for low-level programming languages (buffer management in a micro-controller) than for every-day programming in java.
Comments.UserDisplayName: Michel Billaud
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-05T11:23:29.240Z
Comments.Text: @BenI : music may be an interesting example.  What is the note when your finger is on the 8th fret of the G string ? [mod 12]
Comments.UserDisplayName: Michel Billaud
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-06T16:29:02.683Z
Comments.Text: To save time, you could use a clock. Ignore the computer, and show that 5min - 10min = 55min. Then show how this can be useful. We can not distinguish between 55 and -5 (5 to), but we can at least have negative numbers.
Comments.UserDisplayName: ctrl-alt-delor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-10T17:21:21.173Z
Comments.Text: "*early enough along in the curriculum that they still focus on programming*" seems to presuppose a linear curriculum structure of (a) programming; (b) other areas of CS as they relate to programming; (c) other areas of CS in their own right. Is that an intended implication? Why should elementary number theory not be taught before programming?
Comments.UserDisplayName: Peter Taylor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-10T17:25:43.573Z
Comments.Text: @PeterTaylor You are speaking in hypotheticals, and you are not wrong, but in practice I have never encountered (or even heard of) any program that goes in any order other than your a -> b -> c.
Comments.UserDisplayName: Ben I.
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-11T08:51:51.217Z
Comments.Text: @BenI., the course I studied had number theory in parallel with an introduction to Java, and although I can't remember the exact lecture-by-lecture sequencing it's possible that modular arithmetic had been introduced in the number theory course before numeric operators in the Java course.
Comments.UserDisplayName: Peter Taylor
Tags: <mathematics>
Title: How far do you take modular expressions?
ThreadText: # How far do you take modular expressions?
  
  (Asked by: username_0 on 2018-01-04)
  
  I'm sure that basically every introductory course involves teaching about the ubiquitous mod operation. In my experience, and I'm sure I'm not alone in this, I've found that teaching my students that "mod is the remainder of division" is insufficient if I want them to make any use of the concept later on.
  
  Beyond showing them how to use mod to check divisibility, I have for the last few years gone into far more interesting operations in order to help them achieve some intuitive understanding of what mod is and how it works. So, for instance, I show them how they can increment within a modular circle of numbers from `0` to `n-1` (a circle of size `n`):
  
  ```
  [some loop structure] {
      x = (x+1)%n;
  }
  
  ```
  
  Or, how to move that circle along so that it ranges from `m` to `(m+n-1)` (still a circle of size `n`, but it no longer starts at `0`):
  
  ```
  [some loop structure] {
      x = (x+1-m)%n+m;
  }
  
  ```
  
  Or how to decrement along a `0` to `n-1` circle in a language like Java, which deals with negative modular operations by returning the highest negative congruence (ie. `-10 % 4` would return `-2` instead of `2`. While they are both technically correct answers, Java's answer is decidedly inconvenient for the purpose of moving along a modular circle of numbers, because when you try to move from 0 back to `n-1`, you get the wrong result.)
  
  ```
  [some loop structure] {
      x = (((x-1)%n)+n)%n;
  }
  
  ```
  
  Or, doing the same thing by moving `n-1` steps clockwise around the circle instead of moving `1` step counterclockwise:
  
  ```
  [some loop structure] {
      x = (x+n-1)%n;
  }
  
  ```
  
  And, of course, we can generalize this to involve any cyclical pattern of numbers that can be reduced to a proper modular circle where $f(n)$ is the function that takes any number within the cycle to its corresponding location in the modular circle, and $g(n)$ is the function that takes it back:
  
  ```
  [some loop structure] {
      x = g(f(x+1)%n);
  }
  
  ```
  
  Now, I am reasonable certain that nobody uses structures like this in any production environment. Part of my justification for going to such lengths with mod operators has been that I am not a teacher of software engineering. I am a teacher of computer science, and having a firm understanding of modular arithmetic is important for Some Big Ideas later on. (Like Two's Complement, which has a very intuitive and coherent explanation when you think about it in terms of cycles within a number space.) And when all is said and done, many of my students really do come out with a good, intuitive sense of how the mod operation works.
  
  But I also wonder if I have just gone plum crazy. This stuff takes a lot of class time to get the kids to master, and I'm really wondering if the time would be better spent on other pursuits.
  
  **How far should modular arithmetic be taken in the CS classes that are early enough along in the curriculum that they still focus on programming?**
  
  **Tags:** mathematics
  
  > **Comments:**
  > **username_1**: You can show them the more advanced examples without expecting them to reproduce them on a test. That way you open the door for interested students but don't overwhelm everybody else.  
  > **username_0**: @username_1 That's a good solution, but I still don't know where to draw the line. Also, I'm not sure if I'm missing other (more important) examples.  
  > **username_2**: @BenI : when n is a power of 2, bit-masking does the trick at very low cost. But the consideration is more relevant for low-level programming languages (buffer management in a micro-controller) than for every-day programming in java.  
  > **username_2**: @BenI : music may be an interesting example.  What is the note when your finger is on the 8th fret of the G string ? [mod 12]  
  > **username_3**: To save time, you could use a clock. Ignore the computer, and show that 5min - 10min = 55min. Then show how this can be useful. We can not distinguish between 55 and -5 (5 to), but we can at least have negative numbers.  
  > **username_4**: "*early enough along in the curriculum that they still focus on programming*" seems to presuppose a linear curriculum structure of (a) programming; (b) other areas of CS as they relate to programming; (c) other areas of CS in their own right. Is that an intended implication? Why should elementary number theory not be taught before programming?  
  > **username_0**: @username_4 You are speaking in hypotheticals, and you are not wrong, but in practice I have never encountered (or even heard of) any program that goes in any order other than your a -> b -> c.  
  > **username_4**: @BenI., the course I studied had number theory in parallel with an introduction to Java, and although I can't remember the exact lecture-by-lecture sequencing it's possible that modular arithmetic had been introduced in the number theory course before numeric operators in the Java course.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_5 on 2018-01-10. Score: 7
  
  A specific example that I've used the mod operator before for (and have seen it used in production code this way) is to represent a higher dimensional array (usually 2D, but higher is possible) as a one dimensional array, and then use some modular arithmetic to retrieve the higher dimensional structure. The reason one might want to do this is if your array structure is a substructure of a more complex object, it might be simpler to implement it one dimensionally, and then add more complexity onto that.
  
  I've seen this done when one is "tiling" some 2D space, where each tile maps to some properties, *and* where each tile's properties may change in time. This could end up being a very complex structure: potentially, a mapping from time, to the first dimension of the tile, to the second dimension of the tile, to each of the properties of the tile. In such a case, the geometric "2D"-ness of the tiling may not be that important (except for perhaps the display), and so the implementation of the internal model of these tiles could be one dimensional instead, simplifying our model.
  
  Here's a simple 2D array example. Say one has a `3` by `3` array, where the "property" is represented by some integer:
  
  ```
  1 4 9
  
  0 2 7
  
  5 6 4
  
  ```
  
  Our 2d array may be indexed with `[row, column]` as follows:
  
  ```
  [0,0] [0,1] [0,2]
  
  [1,0] [1,1] [1,2]
  
  [2,0] [2,1] [2,2]
  
  ```
  
  However, we *can* represent it with only a single parameter as:
  
  ```
  0 1 2
  
  3 4 5
  
  6 7 8
  
  ```
  
  (left to right, then top to bottom is just a convention of course)
  
  Now, how do we retrieve the row and column numbers given one of these indices? This shows some nice symmetry between the `/` operator (that is, truncated division on integers) and the `%` operator.
  
  If we're indexing rows and columns as in my first example, the "row number" of an index `i` above is given by `i / 3` (again, truncated), and the "column number" of an index `i` above is given by `i % 3`.
  
  In general, if you have an `n` by `n` array, and you index it as I did above, the row number is given by `i / n` and the column number is given by `i % n`.
  
  Another example, and this one gets closer to the intuition you're trying to achieve, is simplifying computations for cyclic functions. If your functions are over the integers, then your operator `%` is good enough. However, this wouldn't work for continuous functions. Nicely enough, one can take your discrete cyclic model and make it continuous in programming languages by using `fmod` or an equivalent.
  
  Specifically, for students with enough background in Calculus that have some familiarity with username_4 series, one can think of how one would write a trig function like cosine. One might realize that the 6th degree username_4 polynomial approximation is "close enough" in the range between $- \pi/2$ to $\pi/2$. Then, one can "mirror" that to get one complete cycle of the cosine curve between $-\pi/2$ and $3\pi/2$ (for example.) Then, with this, one might ask how one would compute the value of $cosine$ for *any* real number, and the answer is quickly obtained by using some modular arithmetic to get your number in that range, and then use our restricted cosine function for that translated number.
  
  This use of mod also relates to [username_6's answer](https://cseducators.stackexchange.com/a/4128/27): thinking of taking the mod of a number as involving several subtractions is precisely how one might implement the continuous `fmod` function (however, whereas a discrete mod function's usual "remainder" intuition may be lost here, the intuition regarding the cyclical nature of mod should be strengthened).
  
  In general, I like to think that the kind of mental modeling required to think about mods is going to help these students regardless of whether they literally use them later on in their programming careers.
  
  > **Comments:**
  > **username_0**: Welcome to [cseducators.se]. This is a breathtaking answer.  There is much to think about in here!  
  
  ---
  
  ### Answer by username_6 on 2018-01-05. Score: 3
  
  > How far should modular arithmetic be taken in the CS classes that are
  > early enough along in the curriculum that they still focus on
  > programming?
  
  I view the `mod` or `modulus` operator as any other operator that is new to the students. Even though `mod` is used more often when programming because it results in an integer value which is much more friendly to work with than a mantissa of a real division, I see no reason early on to spend any more time than is necessary to get the idea of how the mod function/operator works.
  
  When students are introduced to the mod operator for the first time it can be confusing. To make it easer for them I tell them that just because it is named `mod` doesn't mean you have to create a new idea in your head to understand it. Instead just think of it as the `remainder`, but when you talk to others programmers you have to use the word `mod` or `modulus` as that is the currently accepted name. They like that and we only spend a few minutes on it. I obviously show them how it relates to float division and integer division by listing examples of `float division`, `integer division` and `modulus`.
  
  Also if a student says `remainder` in class I just ask `Did you mean mod?` and if they say yes we keep going. If they say no then I ask what they mean. If they are getting it wrong I do a quick review. Most students get it rather quickly but do say `remainder` more often at first but quickly get to using `mod` or `modulus`.
  
  If I do have to go over the concept again for some students I do use the concept of having items in my hand and do multiple subtractions until I have just the remainder. When I can subtract no more I ask them what do I have left and they give me an integer number and I say that is the `mod` value. Haven't had anyone get it wrong after they repeat that exercise back with them holding the items and doing the repeated subtractions, e.g.
  
  1 % 3  
  I have 1 item in my hand,  
  Can I subtract 3: `No`  
  What do I have left: `1`  
  That is the mod value
  
  5 % 3  
  I have 5 items in my hand,  
  Can I subtract 3: `Yes`  
  Now I have 2.  
  Can I subtract 3: `No`  
  What do I have left: `2`  
  That is the mod value
  
  7 % 3  
  I have 7 items in my hand,  
  Can I subtract 3: `Yes`  
  Now I have 4.  
  Can I subtract 3: `Yes`  
  Now I have 1.  
  Can I subtract 3: `No`  
  What do I have left: `1`  
  That is the mod value
  
  0 % 2  
  I have 0 items in my hand,  
  Can I subtract 2: `No`  
  What do I have left: `0`  
  That is the mod value
  
  1 % 2  
  I have 1 item in my hand,  
  Can I subtract 2: `No`  
  What do I have left: `1`  
  That is the mod value
  
  4 % 2  
  I have 4 items in my hand,  
  Can I subtract 2: `Yes`  
  Now I have 2.  
  Can I subtract 2: `Yes`  
  Now I have 0.  
  Can I subtract 2: `No`  
  What do I have left: `0`  
  That is the mod value
  
  
  ---
  
  