Your Absolutes Are Relative

Relativity.

This is a topic that I have strong feelings about. The amount of times where I've been mad at an individual or had arguments with relatives on that topic is much, much greater than the amount of fingers on my hands.

If there's one thing that I try to remember whenever I am speaking or listening to someone, it is that there is always two sides to a medal. What you believe is right might not be the same thing as what someone else believes is.

Let me state this in a more "theoretical" kind of way: what you consider as absolute is relative. What do I mean by that? What you consider to be true (absolute), may be considered as false by somebody else. This is what gives your absolutes a relative aspect.

As a human being, I do not consider myself (or any other human being, for the matter), as an entity capable of knowing everything. In fact, I would say that I know close to nothing. Our universe is so vast and full of wonders that it is simply ignorant to consider something as absolute. How do I know that my view is better than another's? Who am I to assert anything at all in this world? Everything that I think only comes from what I currently know. I may learn something that disproves one of my beliefs as I grow up, or I may stay uncertain for the rest of my days, but I am in no way able to assert that something that I know is, in fact, true. Compare this to a kid learning maths. At first, teachers will tell him that he can't divide by 0. He will keep learning, constantly telling himself that division by 0 is straight impossible because his calculator answers with "Error" every time he tries to perform such an operation. However, he might learn later on that it is simply not defined, and that he can still work around this aspect (I am not even qualified enough to elaborate here, ironically). He learned an assumption ("division by zero is impossible") and later learned that it is relative to the context. Long story shot, what we currently know is based on what we learned. Tomorrow, I might learn that I was wrong. Therefore, it is not safe to assume anything, because it may change.

What is so great about relativity? People that understand that their opinion is not absolute are open-minded. I may believe in a religion or in a political decision, but I understand that other people may think differently and that their opinions are valuable nevertheless. This is what makes a society that progresses faster, and a society where everybody is on the same level (given that we accept that any opinion is as valuable as ours).

The moment where I have a problem with other people, is when they start to state their opinion as an absolute. They simply assert something and expect you to comply. If we accept that everything that we say is based on our knowledge and that it is not absolute, then it is normal to say that what we are saying is just our opinion. Of course, we can not always mention that we're expressing an opinion, because it would be extremely redundant to constantly say "I think that...". The problem comes when it is a hot topic. If your view on something could hurt somebody else's feelings, you should always state that you're only expressing an opinion. There is a whole difference between "I believe in God" and "God exists". The same holds for "I don't believe in God" and "God doesn't exist". Your view on the matter could unnecessarily hurt someone, so why not clear out right away that you don't pretend to know everything and that you could be wrong. Even better, the next step is to show that you consider other views as equally valuable: "I believe in God, although I understand why other people don't". It is a simple touch in your communication that can make a whole difference.

As you begin to view things as relative, it simply never stops. You constantly find new topics on which you have absolute views, and you make it a priority to make it relative. In fact, I think having no opinions at all would be the most logical thing to do. You just accept that every side is equally valuable, and evaluate them all to make a decision. No need to have a stopped opinion about something, that is just stubborn.

This is why I think Socrates, which I truly admire, was so great at arguing. He simply had no opinion. Or, at least, he never stated it first or as an absolute. His true power was from his listening. He would let people state their opinion (making them vulnerable by showing what they consider as absolute) and, once he observed enough vulnerabilities, would show different perspectives on the matter, therefore making the other people's views disprovable. He had no opinion, and defeated people that showed theirs. Having opinions make you vulnerable. Constantly evaluating the possible opinions makes you a great citizen.

Even to this day, I am still extremely struggling with this perspective or seeing everything as relative. One of my big problems right now is that I believe in one particular absolute: I consider everything to be relative. In fact, this whole post could be wrong. I understand it. It is wrong of me to have a stopped opinion on the matter, but I am not closed to the idea that I may be wrong.

Whether this is an absolute or not, your absolute are relatives. Be careful not to conflict with absolutes of others. Show them respect by accepting the value of their opinions. They may know more than you do.

Embracing Defeat

Recently, my perception of success completely metamorphosed. It went from being first at all costs to embracing defeat.

Why such a change of perspective? I couldn't even tell. All I can say is that it is for the better. What I used to consider as pure failure now gives me pure happiness. As I always say, happiness comes from the little things (surely that quote should be attributed to somebody, just imagine a reference here).

You see, I love to learn. Even though school used to be a massive source of disgust when I was young (and I certainly am not alone here), it now turned into something much more valuable: a constant resource to learn from. I learned to enjoy learning. Now, I simply can't get enough. The mere idea of not learning enough gives me a dizzy feeling, as if it was a mistake in itself. I consider not going fast enough as going backwards. The only way to keep up is to work harder. I'll state it again: I love to learn.

Who in their right mind would consider 1st place to be inferior to 2nd place?  I would. In fact, I would consider last place to be even more valuable.  Being first means that you've achieved just enough. By always ending up first, you lose this thrill for competition, this energy to fight and persevere. Ending last only means that you have even more opportunities to learn from than the others. You can get better. Work is required, just a bit more than the ones before you. And this is just wonderful.

Stop perceiving defeat as a failure in itself, see it as an experience. By experiencing defeat, you learn to get back up. You learn to fall, and that is crucial. Never have I seen or heard of someone that never fell from their oh-so-great podium. They'll fall eventually. The difference? You'll get back up faster.

By no means am I stating that last place should be your goal. You should always aim for the sky, and even higher. With dedication and hard work, you'll reach your goal. Just don't perceive defeat as a wall on your path.

Catch the opportunities to learn when you're last, learn to embrace defeat.

Why Pre-Optimization Truly is the Root to All Evil

Every now and then, you'll live this situation in your head:

Alright, alright. Now what do I want. Oh yes, right. If the zombie is close enough to the player, it has to hit the player. Soooo *typing* if zombie distance-to player is smaller than hit distance *stops typing*... Wait, what am I doing? That's a wasted square root! No need to calculate the exact distance, I just want the squared distance to see if it's smaller than the threshold! Haha! I am so clever. *ctrl-shift-home* *backspace* *typing* if zombie distance-squared-to player is smaller than hit distance then... 

Boom. You heard that? That's the time-bomb that you just set. You'll keep on writing the rest of your function with that I'm-so-clever feeling, compile, press that start button from your menu and test it out. Oh, what? The distance looks too close? How about a SQUARE ROOT too close?

You know why that is? Because if you're in any way like me (human, that is) you'll make mistakes. You'll forget that DISTANCE_THRESHOLD*DISTANCE_THRESHOLD, and it won't do what you expected.

Now, I'm not pretending in any way that this particular situation is a common mistake for programmers or that you would have forgotten it. All I'm saying here is that I often did the exact same as this. Wanted to get rid of that "useless" square root, and forgot an essential part of the equation: the distance squared. I'm sure I'm not the only one that does these kind of mistakes. We all look at a piece of code and our little optimization-demon goes over our shoulder and whispers in our ear that "this is sub-optimal" or "I could have made it faster". Whether this is due to the constant need for programmers to be right or a legit observation from an experienced person is irrelevant.

In the past 5-6 months, my vision of programming in general completely changed. Game development taught me a lot of lessons, and I'll try to share my perspective of approaching a problem. Who knows, it might give ideas to somebody out there too! Keep in mind that this is the way that I perceive programming, your opinion might totally differ - and that's perfectly fine, but at least give me the benefit of the doubt by reading the whole thing before pointing that finger and listening to that optimization-demon.

So, here's how I now approach a programming problem:

I want something working as soon as possible, no matter how fast it computes

Whether I'm making an optimized algorithm to find non-prime numbers or a zombie shooter, I focus on getting visual feedback as soon as I can.

A zombie game? Here's my approach:

1. Get a drawn map on screen loaded from a hard-coded array
2. Load the map from a more flexible format
3. Get a player drawn on screen
4. Move the player
5. Handle collisions
6. Move the camera along with the player
7. etc.

The first step? Get something to work with quickly. I don't care about the game logic, about the map loader, about the collisions yet. I want feedback - make sure that it's working. In the context of one-man indie game development this is crucial. It literally saved me hours of debugging.

An optimized primality-checking algorithm? Here's how I'll deal with it:

1. Make it work, with the slowest algorithm on earth if I have to
2. Make SURE it works with tests
3. Optimize where needed

Visual feedback indirectly make me more productive, because the mere sight of something that works makes me feel like things are going good, and my mind works much better in these conditions. 

I want small, estimable, and realistic tasks to achieve

Making a complete battle/ai system with all the different components interacting with each other properly on one programming sprint is hard. Making a player walk on screen is easy.

If you're like me, looking at your TODO task-list of the day and seeing - make zombie AI -, and you'll have procrastination hit you pretty fast.

However, show me a list of small tasks such as: - Spawn zombie hard-coded - Spawn zombie randomly - Spawn zombies at intervals - Make zombie wander around - Make zombie chase Player - Path finding for Zombie - ... and I'll breeze through them without even noticing how long it took. My mind is more productive when I set smaller tasks for myself, even in life on a daily basis.

Breaking everything in small pieces also makes it easier to estimate the time of your work.

I want to see that pre-optimization demon burn in front of all programmers for them to watch

I hate pre-optimization. I wasted way too much time debugging optimizations that I thought would "just work". I've helped a friend once that asked for help as to why his function wasn't working properly. I freaked out as soon as I merely saw the hint of a goto.

It's not so much that I think that it's bad to optimize, obviously not. I just think that optimizing something just because you have the pretension to assert that "this will be the bottleneck of the program" is ignorant. Especially when it's an algorithm that you are not so familiar with or a piece of code that you didn't profile. 

Obviously, this does not apply to people that know what they're doing. If it's more than the fifth time that you write that A* algorithm, you have the absolute right to use any optimizations that you know will help. What's the difference? You have tried it before, multiple times. Heck, even then I'd still go with a working solution, and only optimize if it is really needed.

I won't tell you where I should optimize, my profiler will

Here is the solution to any pre-optimization: profile first.

But, man, that A* will take so much processing time I really need to run it partially every frame and optimize all the containers and-

Profile first.

 Modulo is so slow! My teacher said that it's the slowest arithmetic operation. I have to find a trick to make it fas-

Profile first.

Woah this is so sl-

Profile first.

Why would you even waste a single second optimizing something that may actually represent only 0.1% of your application processing time? You're a programmer, you certainly like optimizing your schedule just like I do. So, please use that time to make your project features progress, not optimizing something that may actually be nothing in terms of computational time.

Once you profile what do you do? You find the bottleneck, and optimize that part. Not only will you find that your optimizations will be far more effective, you'll also spend more time actually making the project move on.

Next time, focus on optimizing your wall clock time rather than that modulo time.

Make humanity a favor - keep the gotos for the optimization competitions and velicoraptors.

OPTIMUS NOT-PRIME - Part Two: Let’s Make it Work, AND Be Fast

OPTIMUS NOT-PRIME - Let’s Make it Work, AND Be Fast

This is the second part of a series Optimus Not-Prime, where we find the n first non-prime numbers as fast as possible.

What we've done so far

On the first part of this series, we managed to get an algorithm working. For comparison's sake, let me show you the two functions that we were working with:

bool isPrime(int n)
{
    if (n<=1) return false; // 0 and 1 are not prime numbers
    for (int i = 2; i<n; ++i) // check every possible factor to see if we can divide by it
        if (n%i == 0) return false; // if we can, the number is not prime
    return true; // otherwise, the number is prime!
}

void fillNonPrimes(int array[], int count)
{
    int index = 0;
    for (int n = 0; index < count; ++n)
    {
        if (!isPrime(n)) // number is composite?
        {
            array[index++] = n; // add it to our list and move to next item
        }
    }
}

It does the job, but in a competition environment, we want more than "the job". We have a need for speed (no pun intended.) You can go ahead and test out with n=1000, n=10000, and it may be pretty fast. But try to go with n=500000. You'll have enough time to grab a cup of coffee. Clearly, we need to optimize. Here's what we'll do here:

1. Make some assumptions about the problem that will help us optimize further
2. Start optimizing, step-by-step, with a following explanation of the improvements

Please take note: a lot of optimizations are based on observations on my setup (which will be the same at evaluation), they might not apply to any application/environment.

Also, I'll say it again: things will get messy. Do NOT assume you can just use these optimizations everywhere. They are highly non-flexible and extremely specific to the current problem.

Please, keep the dirty code only for the optimization competitions

 - Albert Einstein

Let's take some stuff for granted

Let’s just simply assume that we are allowed to initialize the array with some values first. This will greatly simplify our optimizations after that. In the context of the competition, the teacher says that it’s fine to fill up to n=4. So, let’s do that!

Our fillNonPrimes will change just a bit:

void fillNonPrimes(int array[], int count)
{
    array[0] = 0; array[1] = 1; array[2] = 4; // 0, 1 and 4 are not primes.
    int index = 0;
    for (int n = 5; index < count; ++n) // start at 5 since we already filled with some numbers
    {
        if (!isPrime(n)) // number is composite?
        {
            array[index++] = n; // add it to our list and move to next item
        }
    }
}

Now, that’s not optimization. If you compare with the previous version you’ll certainly see close to no difference. But, it let’s us make some assumptions:

1. We can assume that every single even number that we meet is not prime. Why? Because we passed 2 already (the only prime even number). We’ll see how to do that in a few mouse-wheel scrolls.
2.  We can ignore the special cases (0 and 1) which would over-complicate our algorithm for nothing.
3. We add 4, well because the teacher allowed us to do so. Then, we can start right away at 5.

Cutting our fillNonPrimes calculations by half 

How do we do that? We ignore half of the data. From the few pieces of code that I had to optimize while programming, one of the biggest optimization that I found was not the x << 1 instead of x*2 that makes you feel so clever, but rather finding how to reduce the data tested. Even in games, it goes around the same idea. Your path-finding is making your game lag? Well no need to go and optimize every single line of it yet. You can actually just call it less often. Calling the path-finder at different intervals for every enemy every 15-30 frames instead of every frame will make a difference.

But, I'm going out of context. Let's reduce our data:

void fillNonPrimes(int array[], int count)
{
    array[0] = 0; array[1] = 1; array[2] = 4; // 0, 1 and 4 are not primes.
    int index = 0;
    for (int n = 5; index < count; n+=2) // start at 5 since we already fill some numbers
    {
        if (!isPrime(n)) // number is composite?
        {
            array[index++] = n; // add it to our list and move to next item
        }
                
        if (index < count) // we still have space for one more
        {
            array[index++] = n+1; // add the next even number
        }
    }
}

I think the comments are pretty straightforward. We just skip every even number in the loop and simply add it after we have checked an odd number. We do n+1 because the even number is the current odd number plus one. The if right before we add the even number is just to make sure we don't bust our array.

There. Half our data will be checked now.

Cutting our isPrime calculations by half

With the previous optimization, we know that every single n that will get into isPrime will be odd, since we treat even numbers separately. What does it mean? We can ignore any even number. So, we only need to check if the number has any odd factor and completely ignore the check to see if it is even. Let's do that right away:

bool isPrime(int n)
{
    for (int i = 3; i<n; i+=2) // check every possible odd factor to see if we can divide by it
        if (n%i == 0) return false; // if we can, the number is not prime
    return true; // otherwise, the number is prime!
}

Here, I removed the check to see if n is smaller or equal to 1, since we handle that with our assumption that we start at 5.

Then, I simply chance ++i to i+=2, making it only pass through odd numbers.

Cutting our isPrime calculations even more

It is a mathematical property that you only need to check to the square root of a number to see if it is prime. 

Why? Because if you want to see if 10 has factors, you start by checking if 10 is evenly divisible by 2. If it is, then you can deduce right away that it is also evenly divisible by 5, because 2*5 = 10. The same goes for a number like 100. When you find that 100%2 == 0, you know that 50 is a factor, so you don't need to go this far. You only need to check up to i=10 (the square root of 100) to find out that 10 is also a factor. No need to go further.

Specifically, it means that we don't need to go higher than sqrt(n). Let's implement that:

bool isPrime(int n)
{
    int limit = static_cast<int>(sqrt(static_cast<double>(n))); // no need to go higher than the square root of the number
    for (int i = 3; i <= limit; i+=2) // check every possible odd factor to see if we can divide by it
        if (n%i == 0) return false; // if we can, the number is not prime
    return true; // otherwise, the number is prime!
}

The static_casts are just there to get rid of warnings.

Optimizing the modulo

From this point, we're starting to get to more specific optimizations. Ugly optimizations. From profiling, I saw that the modulo operation was doing most of the work. So, it makes sense to target our optimizations towards it.

Why are we doing modulo in the first place? We want to see if the n is evenly divisible by i. We don't really care about the remainder, we just want to see if it is evenly divisible. In our environment, we tried a variety of variations to n%i==0. The one we found out was the fastest (again, in our environment) was a simple trick that gets the job done.

Instead of checking to see if the remainder is zero, we check right away if the number is evenly divisible. How? We make use of the integer cast truncation. Like so:

if ((n/i)*i == n)

How does it work? (n/i) performs an integer division, truncating anything that is not an integer. For example, 5/2 would give us 2 instead of 2.5. Then, we multiply it back by i, and see if it's the same number as before. If the number is not evenly divisible by i, it won't be the same number after the calculations.

Example: 5 / 2 gives us 2 (with integer truncation), multiplied by 2 gives us 4. 4 is not equal to 5. 5 is not evenly divisible by 2.
10 / 2 gives us 5, multiplied by 2 gives us 10. Boom, evenly divisible.

Let's use the trick now:

bool isPrime(int n)
{
    int limit = static_cast<int>(sqrt(static_cast<double>(n))); // no need to go higher than the square root of the number
    for (int i = 3; i <= limit; i+=2) // check every possible odd factor to see if we can divide by it
        if ((n/i)*i == n) return false; // if we can, the number is not prime
    return true; // otherwise, the number is prime!
}

Why have an easily understandable solution? Let's use maths!

Here we'll use a mathematical optimization that I don't fully understand, so I'll just redirect you to this stackoverflow question (the interesting part is the brute-force method by LostInTheCode). It basically states that every prime number can be represented by 6k+1 or 6k-1, and makes use of that to check if it is prime. Here is the isPrime code:

bool isPrime(int n)
{
    if (n % 3 == 0) return false; // divisible by 3 = not prime (number can't be 3, we start at 5.)
    for (int k = 1; 36*k*k-12*k < n; ++k)
    {
        if (n % (6*k+1) == 0 || n % (6*k-1) == 0) return false;
    }
    return true;
}

Let's use our modulo trick once again:

bool isPrime(int n)
{
    if ((n/3)*3 == n) return false; // divisible by 3 = not prime (number can't be 3, we start at 5.)
    for (int k = 1; 36*k*k-12*k < n; ++k)
    {
        if (((n / (6*k+1))*(6*k+1) == n)|| ((n/(6*k-1))*(6*k-1)==n)) return false;
    }
    return true;
}

Now you should get some pretty decent speed. You could use a variable to store 6k+1 and 6k-1, but our benchmarks showed that the assignation of a variable was slower than the actual calculation.

Extracting all the juice we can out of it

Let's give some final touch now. Make it truly geeky but at the same time extremely ugly.

From our benchmarks,unsigned int calculations were faster than int calculations, so we decided to use unsigned ints everywhere:

void fillNonPrimes(unsigned int array[], unsigned int count)
{
    array[0] = 0; array[1] = 1; array[2] = 4; // 0, 1 and 4 are not primes.
    unsigned int index = 0;
    for (unsigned int n = 5; index < count; n+=2) // start at 5 since we already fill some numbers
    {
        if (!isPrime(n)) // number is composite?
        {
            array[index++] = n; // add it to our list and move to next item
        }
                
        if (index < count) // we still have space for one more
        {
            array[index++] = n+1; // add the next even number
        }
    }
}

bool isPrime(unsigned int n)
{
    if ((n/3)*3 == n) return false; // divisible by 3 = not prime (number can't be 3, we start at 5.)
    for (unsigned int k = 1; 36*k*k-12*k < n; ++k)
    {
        if (((n / (6*k+1))*(6*k+1) == n)|| ((n/(6*k-1))*(6*k-1)==n)) return false;
    }
    return true;
}

We also found out that gotos were faster than loops because of the overhead of loop jumps that started to appear with huge ns. Now, GOTOS ARE EVIL. The only reason I will ever use them is in a optimization competition or to call the goto velicoraptor. Here's the final super-ugly code:

void fillNonPrimes(unsigned int array[], unsigned int count)
{
    array[0] = 0; array[1] = 1; array[2] = 4; // 0, 1 and 4 are not primes.
    unsigned int index = 0;
    unsigned int n = 5; // start at 5 since we already fill some numbers
    
    loop:
        if (!isPrime(n)) // number is composite?
        {

            if (index >= count) return;
            array[index++] = n; // add it to our list and move to next item
        }
         

        if (index >= count) return;

        ++n;

        array[index++] = n; // add the next even number


        ++n;

        goto loop;
}

bool isPrime(unsigned int n)
{

    if ((n/3)*3 == n) return false;

    // http://stackoverflow.com/questions/4424374/decide-if-number-is-prime-number

    unsigned int k = 1;
    loop:
        if (36*k*k-12*k >= n) return true;
        // modulo trick for 6k+1 and 6k-1
        if (((n / (6*k+1))*(6*k+1) == n)|| ((n/(6*k-1))*(6*k-1)==n)) return false;
        ++k;
        goto loop;
}

Enough of the ugly code. 

In conclusion... 

So, that's how you can optimize a prime-finding algorithm! You can get much faster results using sieves, probabilistic methods, or better-optimized versions (I rarely have to optimize stuff! If you have tips for me feel free to comment.)

That's it for the isPrime test.

I am considering writing an article about our Eratosthenes version in the near future... So stay tuned!

OPTIMUS NOT-PRIME - Part One: A First Working Algorithm

OPTIMUS NOT-PRIME - A First Working Algorithm

This is a series about how I go on solving a mathematical problem and optimize it as much as I can with what I know. Here is a list of the parts:

1. A First Working Algorithm
2. Let's Make it Work, AND Be Fast
3. (not yet written)

The problem

Here’s the problem that we have to solve in one of my computer science class:

Find all the non-prime numbers up to n.

Where n is a number that we don’t know.

Did I mention that the team that ends up with the program that executes the fastest doesn’t need to do the final lab of the course? Wait, what? Did I hear COMPETITION? I’m in.

Some basic definitions

Some definitions first:

What is a prime number? A number only divisible by 1 and itself.

What is a non-prime (composite) number? All the other numbers.

How do we check it out? Well, if a number has no possible factors, then it is prime. If we can divide it evenly by something between 1 and the number, we got a composite number.

Okay. I won’t explain all the concepts like that because Google will get you much better explanations than I can manage to write, but if something isn’t quite clear enough, please tell me in the comments, I’ll elaborate. I’d rather keep it code-explanation-code-explanation. Not too much time on definitions.

Is it prime?

 Let’s go right up to a working (but slow) solution to check if a number is prime in C++.

bool isPrime(int n)
{
    if (n<=1) return false; // 0 and 1 are not prime numbers
    for (int i = 2; i<n; ++i) // check every possible factor to see if we can divide by it
        if (n%i == 0) return false; // if we can, the number is not prime
    return true; // otherwise, the number is prime!
}

Sure, that’s messy with no brackets and return points everywhere in the function. That’s bad practice, don’t get me wrong. But, heck, it’s an optimizing competition! It has to look a bit “geeky” or just a bit cryptic at least! So, you have been warned: things will get messy.

“But why not optimize the crap out of it right away?”

Because thinking like that is bad and you should feel bad.

Back to the initial problem

Now, let’s get a more complete solution to the initial problem, which is: Find all the non-prime numbers up to n.

So, we have to fill some sort of array that will contain the non-prime numbers.

Let’s ignore all the jazz around creating the array and all that stuff. We’ll just optimize 1 or 2 functions and stick to that.

void fillNonPrimes(int array[], int count)
{
    int index = 0;
    for (int n = 0; index < count; ++n)
    {
        if (!isPrime(n)) // number is composite?
        {
            array[index++] = n; // add it to our list and move to next item
        }
    }
}

Note that I didn’t test the code and it’s off the top of my head since our current version is way too different now. So, if something doesn’t work, leave a comment.

In conclusion...

Now, this gets the job done. But we can do much better than “getting the job done”. We can get the job done fast. We want to avoid the “it doesn’t work, BUT IT’S FAST!”. So next, let’s optimize it a bit.

In part 2, we optimize what we made so far.