Go to the profile of Or Perel
Or Perel
I like writing stuff :-)

Playing with Primes

This post aims to add another skill to your “bag-of-tricks” as a programmer, whether you’re on the client side, server side or a full stack kind of developer. Code demonstrations are implemented in simple C++ / Java-like pseudo-code, but should be easily transferable to any programming language. Hopefully by the end of this post, you’ll realize that even non-graphic programmers can benefit from a bit of basic algebra to get some nifty results!

I’ll start with one of my favorite examples, inspired by this blog post. Remember your job interview, where you were asked to implement a simple factorial function? A naïve recursive implementation looked like this:

And quickly you wanted to support big numbers, and negative numbers, and maybe cache the results…and before you realized, you ended up with a whole class filled with a bunch of useless code for taking care of all these small edge cases. Wouldn’t it be nice if there was just a simple, satisfying solution?

Well there is:

It might not be the prettiest of functions out there, but without digging into small details — it works. It may not be easy to understand, but is very simple to implement.

And this example pretty much introduces the point: there are often as many ways to implement your solution as there are casinos in Las Vegas, but if you open your mind, you’ll find that sometimes there is a simple and elegant algebraic solution out there, which bests the rest of them.

Today’s blog post will focus on some techniques that use prime numbers.

Prime what?

  • Prime numbers are like the basic building blocks of integer numbers — they are the numbers that cannot be divided by any number other than themselves or 1 (we exclude fractions here).
  • Every natural number out there is a multiplication of some prime numbers.
  • We call the non-prime numbers composite numbers.
  • Each number is a composed of a unique combination of prime numbers.

So 2, 3 and 5 are prime numbers, because you cannot divide them any further.

4, 18 and 60 are composite numbers, and are composed of multiplications of 2,3 and 5.

Upgrading data structures with repetitive objects

Naturally prime numbers can be used to represent small lists of items that repeat themselves.

Imagine we have a list of repetitive objects. In reality it could be a list of threads, or graphic primitive shapes, or even GUI components. Regardless of the object type you have, each of those object types may appear once or more in your data structure. For the sake of our examples, we’ll use fruits because there’s nothing like bananas for introducing algorithms:

We want to ask questions such as:

  • Are there any bananas in the list?
  • Do all fruit types appear in the list?
  • How many oranges are there?

We also want to easily add and remove objects to our list.

Regardless of the data structure you choose to store your objects, you can easily answer those questions by attaching an additional number to it. That number will uniquely represent the contents of your data structure. Let us denote this number K, and we will use it to quickly find info about our data structure.

The idea is we assign a prime number for each object type. So for our example above, strawberries are represented by 2, oranges by 3 and bananas by 5.

K should always be the multiplication of all objects currently in your list. So for 2 oranges, 2 bananas and one strawberry we get K=3x3x5x5x2=450. Remember that 450 is unique for this state of the data structure, and we cannot get K=450 for any other arrangement of bananas, oranges and strawberries.

Now your questions boil down to:

  • Are there any bananas in the list?
  • Is (K mod 5 == 0)?
  • Do all fruit types appear in the list?
  • Is (K mod (2 * 3 * 5) == 0)?
  • How many oranges are there?
  • while (K mod 3 == 0) { K /= 3; numOfOranges++; }
  • This works because we’re actually asking:
  • 450 mod 3 == 0?
  • Yes, we have 1 orange at least.
  • 450 / 3 = 150.
  • 150 mod 3 == 0?
  • Yes, so we have 2 oranges at least.
  • 150 /3 = 50
  • 50 mod 3 == 0?
  • No, so we have 2 oranges in total.

As for adding and removing objects to the list:

  • Adding an orange:
  • Update the number to: 450*3 = 1350
  • Removing a strawberry:
  • Update the number to: 450/2 = 225

There you have it.

Advantages:

  • Implementing the structure above is pretty straight forward. Functions are extremely short.
  • K also doubles as a hash-code that uniquely identifies the group of objects.
  • Flexible and easily wraps around other data-structures, whether you’re dealing with lists, queues, stacks, trees, etc.
  • Easy to debug.

Disadvantages:

  • Finding prime numbers to assign to your object types is a challenging problem in itself, but there’s a simple workaround — see below.
  • For medium and larger data-structures, or lists with too many types, this method may cause an overflow.
  • If your list contains 3 object types, and your K can hold 128 bit (long long type in C++), your maximum is around 50 elements.

Now before you go bananas, remember this is just another way of doing things. It is not necessarily the best or only way out there.

If your data always contains a maximum of one object of each type, you’re better off using a bitmask.

If you have a lot of objects or object types, this method becomes cumbersome.

For small-medium cases, this is a quick and easy solution.

How to easily find prime numbers

For practical uses, the small prime numbers you’re likely to use are already known and prime numbers tables are all over the internet. You can simply preload them from an external file and use a generator that returns them sequentially.

A prime numbers generator code example in C++ is attached at the bottom of this post.

Other use cases for prime numbers

Pseudo Random traversal of lists (without repeating over the same object twice)1: This one is useful if you need to travel your list of objects without repeating the same object twice.

Java programmers may resort to Array.shuffle and then travel their list. This is one way of doing it, and there are other methods as well, but if you’ve already implemented a module that generates prime numbers you may want to take a look at the following algorithm too:

http://stackoverflow.com/a/11799186

This technique is efficient, simple and quick to implement. Unlike shuffling, it does not require a linear traversal of the data-set. Nevertheless remember this is a “pseudo-random” traversal, meaning, the traversal of the data structure may show particular patterns (e.g: jump in repetitive gaps).

Encryption: Prime numbers play a big role in the cryptography field (RSA is probably the most famous example out there). However, it goes beyond the scope of this post.

Writing your own

The stuff we mentioned today is merely scratching the surface. Surely there are many other useful use cases for the unique attributes of prime numbers out there.

Found any more uses? Happily share!

Attachment: Prime Numbers Generator code

1 Credit for the original outline of the pseudo-random traversal algorithm goes to Game Coding Complete (4th edition) [Mike McShaffry, David Graham]. For those of you who are interested in game development, this is a great book and I highly recommend it.

Or is a SW Engineer at AutoCAD 360 Core (witty developers with attitude). He enjoys teddy bears, traveling, and in depth airport interrogations.