It’s time to…

That's right, bitches.
Cue insipid hip-hop music.

Yo dawgs. Today me and my homies laid our eyes on some sweet piece of code, that finds a list of prime numbers. The man’s name is P.J, and he’s asked us to pimp his code. Let’s move to his crib and meet the guy.

This is the part where I knock on the person’s door and he pretends he’s surprised to see me.

S'up, PJ?
Whazzup, P.J? We're gonna PIMP YOUR ALGORITHM.

So, P.J wants his code to run faster and to look cooler. That seems like a job for my crew. Show me the damn stuff, man.

Original Algorithm
Yo, that's some nice ass piece of code.

As you can see, dat shit makes a list of prime numbers. But P.J forgot to include the primeNumbers list declaration in that snippet. Come on boy, you can do better than that. Now take a good look at this, man. Can you see what the three steps are?

  1. Use currentPossiblePrime as a cursor to go up and up every number possible.
  2. Check if currentPossiblePrime can be divided by a factor. Check out the second while loop, and you can see that the factor is increased until it’s half the value of the currentPossiblePrime, because the number cannot be divided by anything below 2 that isn’t 1. That means the currentPossiblePrime is prime. currentPossiblePrime is suspected to be prime until it is proven otherwise: when it can be divided by a factor, the loop exits, as isPrime is then set to false.
  3. Add the newly found prime number to the primeNumbers list, and increase the primeCount value. This way, when primeCount exceeds the total amount of requested primes, the main loop exits.
That’s how you get a list of prime numbers. Now for some bitchin’ pimpin’.

FIRST: GET THAT LIST OUTTA HERE.

Lists are nice and convenient, but if you want some real efficient action, an array’s the f***ing way to go. Change the primeNumbers list into an array. This adds some complications:
  • Each time the function is called, the array must be recreated with a new statement. We can’t just remove everything that’s in it, because the request might be for a different amount, so we have to create a new one. We’re not in C++, so we don’t give a f**k about calling delete[].
  • Instead of an Add statement, set the current prime number to the newly found prime number

SECOND: MAKE THAT SECOND LOOP A BETTER PLACE

The while loop is all cool, but can be more efficient. You ain’t seen nothing until you witness the power of the modulo.

  • First off, check out that for loop. We’re looping through the prime numbers. Why the f**k would you want to do that? Well man, when testing for a prime number, there is no need to check if all numbers before it can divide it. Nope. You just need to check if you can divide it by any prime number that comes before it! Picture that in your headbox: you want to check if 13 is prime. You start by checking if you can divide it by 2, and surprise, you can’t. Why, then, would you check if 4 (2 * 2) or 6 (2 * 3) divide 13, since they’re all multiples of 2.
  • The second stop condition of the ‘for’ loop is the same as on the previous code, but with primeNumbers[i] instead of possibleFactor (because we got rid of teh motherf***er). Small change is that the /2 is now a *0.5f. Multiplying is more efficient than dividing, so if you want to nitpick go for it when you feel like it.
  • Now, the if statement uses another method to check if currentPossiblePrime  can be divided by possibleFactor (now ditched for primeNumbers[i], since we’re using the prime numbers themselves to test for divisibility). See that %? This is modulo. It returns the rest of an integral division. This means 13 % 2 would yield 1, as 13 = 2 * 6 + 1. See where I’m heading there? If the modulo of a division is 0, it means the division yields no rest! So,  currentPossiblePrime % primeNumbers[i] = 0 means that primeNumbers[i] divides currentPossiblePrime! Modulo is goddamn useful in situations like this one.
  • Note: Instead of adding a !isPrime condition in the for loop, it is also possible to add a break when isPrime is set to false. It is more efficient, as only called once, but adds lines, and in Pimp My Algorithm, we don’t want no added lines.

THIRD: FIX THE REST

Now all this messing around has got us into some trouble. What trouble? Running the algorithm will give you a damn “Divided by zero” exception at the for loop. How the f**k do you get out of this shit? Well, initialise the first prime number to 2. In the for loop, the first comparison will check the array of prime numbers. Problem is, it’s empty. Filled with nada. Which is why you need to set the first prime number yourself. You can set the currentPossiblePrime to the same number, as it will be increased by one on its first time through the loop.

RESULT

Here it is, PJ, your code is now both shorter and more efficient! Have a look at that fading effect from your old code to your new code.
Just look at this shit.

Addendum:

Today’s networking labs were about multithreading in distributed applications. What I love about Peter Robinson’s labs is that there is always something to sidetrack on. A ‘sidequest’ of sorts.

Though they would usually be pig latin related, today’s sidequest is an algorithm set to find a list of X prime numbers. The basic algorithm was pure brute force, as it was written for demonstation purposes to show how a slow application can freeze an interface if not running on a separate thread.

Advertisements

5 thoughts on “It’s time to…

      1. private void FindPrimes()
        {
        //There are no prime numbers pre 2
        if(maxNo < 2)
        {
        MessageBox.Show("No Prime Numbers Found");
        }

        else
        {
        //2 is a prime number
        //even numbers after 2 are not so do not check
        listBox1.Items.Add(2);
        double maxSqrt = Math.Sqrt(maxNo);

        //Bit Array to keep track of removed numbers
        BitArray removed = new BitArray(maxNo + 1);

        //start looping at 3 and only check the odd numbers
        //After finding a prime remove the numbers from its square and forward
        //as ones previous should have already been done
        for (int i = 3; i <= maxNo; i += 2)
        {
        if (!removed[i])
        {
        //stop before the square root of the max number
        if (i < maxSqrt)
        {
        //stop before the max number
        for (int j = i * i; j <= maxNo; j += 2 * i)
        {
        removed[j] = true;
        }
        }
        listBox1.Items.Add(i);
        }
        }
        }

  1. Hello, talk about late to the party.

    Anyways, this was a good example of optimization. (I also enjoyed the Pimp My Ride parody !).
    However, for increasingly larger amounts of larger primes (see RSA : http://en.wikipedia.org/wiki/RSA_(algorithm)), a different approach is required.

    One way to go about it is probabilistic algorithms; in this case, you would generate a random large odd number and then check if it’s a prime.

    There are a number of tests available do to so; I have implemented the Miller-Rabin primality test in Java but don’t have the code available (make use of BigIntegers !).

    Each test has a high probability of truthfulness : in Miller-Rabin’s case, it returns a false positive 1/4 of the time. To strengthen the result, the test can be run multiple times and the probability of a false positive would decrease by a factor of 1/4 each time.
    Other tests include Fermat’s test and the Solovay-Strassen test (see http://en.wikipedia.org/wiki/Primality_test).
    Note that there are special numbers called Carmichael numbers (see http://en.wikipedia.org/wiki/Carmichael_number) which the tests do not pick up on.
    However, they are extremely rare and on average it is unlikely to cause problems (unless you’re in a mission critical project and you’re relying on prime numbers for some reason).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s