The Power of Modulo

Modulo is one of the first operations I learned in my high school CS classes. And it came easily because the concept of a remainder from division, which modulo gives you is one of the first things you learn after division.

Learning about it, I had never given it much thought. It came naturally to me every time I had to find a remainder or prove whether a number was even or odd:

package main
import "fmt"
func main() {
    numbers := []int{2, 4, 1, 7, 8}
    for _, n := range numbers {
       if isEven(n) {
          fmt.Println(n, "even")
       } else {
          fmt.Println(n, "odd")
       }
    }
}
func isEven(n int) bool {
    return n%2 == 0
}

run in Playground

The mathematical guarantee

Recently, I found out about a new property of the modulo operation, which is described in the following statement:

n % k always gives you a number between 0 and k -1

In other words, given a positive integer k, you can pick whatever positive integer n, and n % k will always yield a value in the [0, k-1] interval.

Logically, it makes sense, but this info, like all great things in life, might be dismissed as trivial because we’re not looking at it through beginner eyes.

For example, take the following code:

package main
import "fmt"
func main() {
    k := 5
    for n := range 100 {
       fmt.Print(n % k)
    }
}

run in Playground

0123401234012340123401234012340123401234012340123401234012340123401234012340123401234012340123401234

The above program will continuously print 01234 until it reaches 100 iterations. Let’s notice a few things before moving on:

• k is a fixed value
• n is a growing value
• after n%k reaches k-1 it starts over from zero

You know what else has values between 0 and k-1? The keys of an array of k elements. Knowing this, let’s put this info to practical use.

Load balancing

If you have a fixed number of servers and want to balance the requests to them in a round-robin fashion(one at a time), we can use the modulo operator.

The number of servers is fixed(k), the number of requests keeps increasing(n), and requestNumber modulo k always gives us a number between 0 and k-1. In other words, it always gives us a valid element of the servers array. Not only that, but each server will be picked one at a time, so the load of requests is evenly distributed among the servers.

package main
import "fmt"
func main() {
 servers := []string{"Server A", "Server B", "Server C"}
 requests := []string{
  "Req 1",
  "Req 2",
  "Req 3",
  "Req 4",
  "Req 5",
  "Req 6",
  "Req 7",
 }
 fmt.Printf("Distributing %d requests across %d servers:\n\n", len(requests), len(servers))
 for requestNumber, req := range requests {
  serverIdx := requestNumber % len(servers) // modulo for round-robin
  fmt.Printf("%s → %s\n", req, servers[serverIdx])
 }
}

run in Playground

Magic index

Another nice property of the fact that 0 ≤ n % k < k-1, is that we can have an index variable that will never go out of bounds.

Let’s say you have a list of songs and a playNextSong function to play the next one. And the way you pick the next song is by having a pointer to the current song, which gets incremented by 1:

package main
import "fmt"
var songs = []string{"A", "B", "C", "D"}
func main() {
    playNextSong(0)
}
func playNextSong(currentSong int) {
    currentSong = currentSong + 1
    fmt.Println("Playing", songs[currentSong])
}

This will eventually fail. When the current song is D, we get:

panic: runtime error: index out of range [4] with length 4

To avoid this issue, we can use the modulo operator, which will always give us a valid element:

package main
import "fmt"
var songs = []string{"A", "B", "C", "D"}
func main() {
    playNextSong(3)
}
func playNextSong(currentSong int) {
    currentSong = (currentSong + 1) % len(songs) 
    fmt.Println("Playing", songs[currentSong])
}

Just by adding % len(songs) to our incrementing logic, we are guaranteed never to get an overflow error. And we can change currentSong + 1 to currentSong + 2 for all we care, and our program will still not crash. Because the magic is done by % len(songs).

By adding % len(songs) we achieved an array that always wraps around:

Regular array: [0][1][2][3] → CRASH!
                                 ↑
                              nowhere to go!
Wrapped array:  [0][1][2][3]
                 ↑          ↓
                 └──────────┘
                    wraps around!

It’s almost like having a magical index that will rid us of all out-of-range errors. Modulo mathematically guarantees the result will always be a valid array index, regardless of the input.

It’s pretty handy to know this little trick, because you’ll meet circular structures all the time—clocks, days of the week, hash rings, etc. Once you see it, you can’t unsee it.

I hope you enjoyed this article as much as I had fun writing it. It’s really a simple topic, but it’s pretty fundamental, and I hope that after reading it, you’ll look at modulo with different eyes and make use of it next time you need to wrap around.

If you enjoyed this article, please give it a 👏 , leave a comment if something was unclear, or connect with me on Linkedin.

Happy coding!