Modulo

AP Computer Science Modulo it's Just Remainder

Think Mathematically

Computer Science is technically a branch of Mathematics and yet pure mathematical thinking may cause problems when you try to understand the temporal relationships (temporal fancy word for timing) of computer programing. For example if you try to understand the following (based on your understanding of algebra):

j = j + 1

The above statement makes no sense, algebraically. But in Computer Science this really means take the current value of j add 1 to it, store the answer back in j. In Programming names are not algebraic variables they are memory locations whose value depends on the timing of instructions. When the above example gets compiled the instructions to the computer get ordered in a certain way and the processor acts on each statement one at a time in the order they are found. It is confusing to the beginning Computer Scientist because they have years of mathematics where the variable was only going to be one value and it was their job to find out what it is.

Another human thought process getting in our way is the fact that we read English from left to right. For the human to understand what is happening they have to read in the whole sentence then work backwards:

• Start on the expression on the right hand side
  • interpret what is happening here (j + 1)
• Then figure out what will happen because of the equals sign

The late Ken Iverson realized this back in the early 1960's Dr. Iverson created a whole notation that would allow a mathematician to represent algorithms. The seminal treatise was captured in his book A Programming Language. IBM hired Dr. Iverson to implement this notation on a computer. He created a new programmming language called APL.

Dr. Iverson came up with a brilliant realization (among many) that our traditional way of resolving precedence (the order we do operations in mathematics) was in reality arbitrary and ambiguous. While most computer languages (like Java) strived to duplicate tradition, Dr. Iverson¹ said there is no operator precedence we just read a statement from RIGHT to LEFT (yes the opposite of what you've been taught all these years) and do the operation when we first hit it. If the programmer needs to ensure certain operations happen first rewrite your equation or use parenthesis to organize which operations go first (so parentheses are the same in any language). The beauty of this realization in our simple example above, reading Right to Left gives us a sense of the temporal considerations when running the program.

1 is added to j and the result stored back in j

Reading right to left provides a better understanding of what happens and when. You begin to think more about how the computer sees things. Java uses a traditional precedence mechanism for mathematical formulas. Reading right to left will not be that helpful for complex statements.

The budding computer scientist needs to be ready to think mathematically in non-traditional ways. Indeed, Dr. Iverson even invented new mathematic symbols and had to create his own font to even print the new operations. He was striving for a new mathematical world where the opertator relationships would be defined in a standard way so you could map your mathematical talents and apply them to a computer in a useful way. This is much the same as Dirac notation for quantum mechanics or Laplace transforms for differential equations. Create a new mathematics that abstracts away tedious details and helps the mathematician to think and get their hands around a new environment.

When you are able to map your mathematics skills into solving the programming assignments, you will be surprised at your own intuition and creativity. You will be able to simplify a problem because you saw the mathematical tricks that reduced 100 lines of code down to 10.

Tricks of the Trade: Modulo

One computer math trick you need to be aware of is modulo. There are many reasons to use Modulo. Indexing into 2 dimensional arrays (matrix after its mathematical counterpart) as an example. It is usually used when we are trying to map large a set of numbers into a smaller set. Many indexing operations will take advantage of modulo (the Java operator %). Modulo is rooted in long division. You know what it is and what it does even if you don't recognize the name.

Modulo = Remainder

Remember doing long division all those years ago in Elementary School? You used an algorithm and your knowledge of the "times" tables and would come up with 2 answers. One was the quotient the other was the remainder. The amount of stuff left over since the division did not go in evenly.

Remainder was always a throw away item in school we reported it but didn't use it very much. But it turns out it's very useful in many aspects of programming. In fact for games you use it all the time with out knowing about it. Most random number generators use modulo by a prime number. In fact the very architecture of the CPU registers has modulo built in. If you were to add 10 to (2³²-1) you would overflow the register but the number left in the register would wrap around 0 and what would be left is 9.

The best thing about modulo is it's a built in mathematics operation. If we had to duplicate the functionality programatically it would make our code too complex. The reality is that complex code is error prone code and we may not take into account every eventuality. By using computer mathematics we have a much better likelihood the code will operate properly. Hopefully by using a mathmatics solution there will be much smaller set of lines of code to debug. It's much easier to find a mathematical error in one line than a logic error in multiple nested if statements

First Example Simulating Multidimensional Arrays

Let's pretend Java didn't provide the ability to declare multidimensional arrays. But they do give us single dimensional arrays. For simplicity sake lets just simulate square matrices (NxN).

Specifications

1. Call the class Matrix1d
2. Using only one array field and any number of individual support fields
3. The actual elements shall be 'int's just to simplify
4. Create a class that constructs a 2 dimensional array given the size N
5. Use Method getElement(int row, int col)
6. Create a display method display() that prints a list of elements and their indexes and prints the matrix in standard matrix format

Lets work on 4 first. There are N columns so the first N elements of the 1d array should represent the first row of the matrix. The second row would be the next N elements … the Nth row would be the last N elements. You should be able to figure out the equation to map a row and column into a single address in our 1d array:

row * N + col

The code for this is:

int getElement(int row, int col) 
{
  return this.mat1d[row * this.n + col];
}

Let's store N in field int n and using the mat1d name for the array let's code the class so far with a possible constructor:

class Matrix1d {
int n = 10;
int mat1d[] = null;

Matrix1d(int n)
{
  this.n = n;
  this.mat1d = new int [this.n * this.n];
  // intialize the elements to count up from 0
  for (int i = 0; i < this.n*this.n; i++) 
  { 
    mat1d[i] = i;
  }
}

// put our code to get an element here
int getElement(int row, int col) 
{
  return this.mat1d[row * this.n + col];
}

void display()
{
  int r,c;

  for (int i = 0; i < this.n*this.n; i++)
  {
    r = i/this.n;   // integer divide gives us the row for the element

    // for the column it's the left over after the integer divide
    // col = i - (r * n) which sin r was calculated with int division is just
    // the remainder. Well since we want to look professional we know that's 
    // modulo. So to look like we know what's going on let's use modulo
    c = i%n
    println("matrix["+r+"]["+c+"] = " + mat1d[i];
  }
}

Now the above code has a few syntax errors in it.

• I'm missing public in front of my class definition
• I forgot a semicolon in the 4th line from the bottom (c = i%n)
• I'm missing the close parenthesis int the println statement and the 'System.out.' before the println

Now these are mistakes you make all the time that the IDE (eclipse, netbeans, etc) point out to you immediately. How did I get the code with those mistakes? Because I coded it in a separate editor I use to write these blog articles and then copied the code and pasted it into Netbeans. Rather than fix my article I thought I would point out to you that you can program outside of the IDE. It's actually helpful to your design. Code out large chunks of code, think about what you want to do, then as a separate step (once you have your logic in place) fix the syntax. It helps to keep you focused on your real problem instead of being side tracked by fixing semicolons or missing keywords.

There is also another problem above in my style of coding Java I am missing 'this.' on my fields. Instead I am addressing them directly by name. I find it helpful to reference object fields by using the 'this' keyword. It is a reminder that this code takes place inside an object. That object would have been constructed somewhere else in the code by calling 'new' on the constructor in the class definition for the object.

Ultimately in object oriented programming fields should be addressed directly as little as possible (even using the 'this' directive). Indeed, I would normally refrain from using them at all and instead implement 'getter' and 'setter' methods to change and access the fields. Now you may be thinking: "It seems kind of dumb for such a simple program" and I agree. For this simple program it's not necessary and only adds clutter to the code with out expressing any central logic. This again is why I like to prepend 'this' to the field. It's a reminder that if this simple little program actually becomes part of a library that another programmer would use, it needs to be buffed up with 'getter' and 'setter' methods and replace my direct references to object fields using the get and set method calls.

Now let's add a main method to test the class so far:

static void main(String[] args)
{ 
  // Create a 5 x 5 matrix
  Martix1d mymatrix = new Matrix1d(5);

  mymatrix.display();
}

Again I just coded this directly in my article editor now I will copy and paste into the IDE and see what mistakes pop up.

There are two mistakes in the main method code see if you can find it.

In the meantime once I fixed all the mistakes in the code above here is what we get as the output:

matrix[0][0] = 0
matrix[0][1] = 1
matrix[0][2] = 2
matrix[0][3] = 3
matrix[0][4] = 4
matrix[1][0] = 5
matrix[1][1] = 6
matrix[1][2] = 7
matrix[1][3] = 8
matrix[1][4] = 9
matrix[2][0] = 10
matrix[2][1] = 11
matrix[2][2] = 12
matrix[2][3] = 13
matrix[2][4] = 14
matrix[3][0] = 15
matrix[3][1] = 16
matrix[3][2] = 17
matrix[3][3] = 18
matrix[3][4] = 19
matrix[4][0] = 20
matrix[4][1] = 21
matrix[4][2] = 22
matrix[4][3] = 23
matrix[4][4] = 24

Did I happen to mention Modulo?

Please review the code so far as it pertains to Modulo. You need to see how modulo is taking a single number and converting it into a column index. This is believe it or not a non-trivial use of a computer program. If you enter the field or do electronics as a hobby you may have to program in a language that doesn't have multidimensional arrays. But that shouldn't stop you from making them yourself out of the tools you do have available. If the project you are working on needs multi-dimensional arrays to simplify the code build your own.

Certainly Java has multidimensional arrays. But what if you wanted to fill the contents of a multidimensional array with the values in a 1 dimensional array? How would we do that? We could adapt our code without much of a problem, but how would you do it if you weren't an expert with modulo?

Better Display or at least more mathematical display

For those of you who have already been introduced to matrices you will agree that our display method does not look like a matrix in a math book. Let's create a new method call displayMatrix that will display the values in rows or columns we don't need the indexes. But we will use modulo to tell us when to start printing elements in a new row. I won't go into the design but try to do it yourself. I provide my solution with the full code listing. One problem with the output from my implementation below, the matrix printed out isn't very square. Single digit numbers get different spacing than double digit. I'll address that in the next installment.

Conclusion

I'm not finished with modulo 2 more articles are coming one to implement 2 dimensional arrays as a Java multidimentional array and fill it with consecutive numbers or from numbers in a single dimensional array. Modulo will play a role there. The second article will be a Blackjack program and how modulo helps us to determine the type of card ace through ten, jack, quesn, king. Modulo will also help determine the suit spades, diamonds, clubs, hearts.

I hope that my taking you through an actual design process didn't bore you to much. I will probably continue in that vein because these programs don't go from mind to paper with out some syntax errors. I thought it might be helpful to you to see how some one else thinks through the process and how far they take it before commiting to compile the code.

/**
 *
 * @author Nasty Old Dog
 */
public class Matrix1d {

    int n = 10;
    int mat1d[] = null;

    Matrix1d(int n) {
        this.n = n;
        this.mat1d = new int[this.n * this.n];
        // intialize the elements to count up from 0
        for (int i = 0; i < this.n * this.n; i++) {
            mat1d[i] = i;
        }
    }

// put our code to get an element here
    int getElement(int row, int col) {
        return this.mat1d[row * this.n + col];
    }

    void display() {
        int r, c;

        for (int i = 0; i < this.n * this.n; i++) {
            r = i / this.n;   // integer divide gives us the row for the element

            // for the column it's the left over after the integer divide
            // col = i - (r * n) which sin r was calculated with int division is just
            // the remainder. Well since we want to look professional we know that's 
            // modulo. So to look like we know what's going on let's use modulo
            c = i % this.n;
            System.out.println("matrix[" + r + "][" + c + "] = " + this.mat1d[i]);
        }
    }

    void displayMatrix() {
        for (int i = 0; i < this.n * this.n; i++) {
            if (i % n == 0) {
                System.out.println();
            }
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a 5 x 5 matrix
        Matrix1d mymatrix = new Matrix1d(5);

        mymatrix.display();
        mymatrix.displayMatrix();
    }
}

References

1. Iverson, K.E., A Programming Language, Wiley, 1962-05. Available at J Software Site

Footnotes:

¹ The late Dr. Iverson's work lives on at a company he created: J Software. He also updated APL (so to speak) with it's sister the programming language J. J has versions for most platforms even the iPhone and iPod. The difference between J and APL is that J reverts back to standard characters yet all of the interesting operators are there. Dr. Iverson also improves on APL in the terminology used to describe the language. Dr. Iverson maps the language contructs into English grammar equivalents. This way comments are started by NB. the english equivalent for NB note bene (note well), operators are now verbs, Variables are nouns, etc. It's a great language one I highly recommend. Read more at http://wwww.jsoftware.com

By the way in J the operator, I mean verb, for modulo is called residue and it uses the "|" symbol instead of a "%" like in Java. You also must put the numbers in reverse, why because the entire language J is read from Right to Left. So the J equivalent of Java's 121%5 would be 5|121. You may think it's confusing, I prefer to think of it as amazing that I can change the way a computer does things to suit my whims and fancies.

Author: Nasty Old Dog