Update

[less_retarded_wiki.git] / fizzbuzz.md

# FizzBuzz

FizzBuzz is a relatively simple programming problem that's famous/infamous by having a number of different approach solutions and is often used e.g. in interviews to test the skills of potential hires. It comes from a child game that teaches basic integer division in which kids are supposed to shout a specific word if a number is divisible by some other number -- what's of interest about the problem is not the solution itself (which is trivial) but rather how one should structure an [algorithm](algorithm.md) that solves the problem. The problem is stated as follows:

*Write a program that writes out numbers from 1 to 100 (including both); however if a number is divisible by 3, write "Fizz" instead of the number, if the number is divisible by 5, write "Buzz" instead of it and if it is divisible by both 3 and 5, write "FizzBuzz" instead of it.*

The statement may of course differ slightly, for example in saying how the output should be formatted or by specifying goals such as "make the program as short as possible" or "make the program as fast as possible". For the sake of this article let's consider the following the correct output of the algorithm:

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26,
Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, Buzz

**Why the fuss around FizzBuzz?** Well, firstly it dodges an obvious single elegant solution that many similar problems usually have and it leads a beginner to a difficult situation that can reveal a lot about his experience and depth of his knowledge. The tricky part lies in having to check not only divisibility by 3 and 5, but also by BOTH at once, which when following basic programming instincts ("just if-then-else everything") leads to inefficiently checking the same divisibility twice and creating some extra ugly if branches and also things like reusing [magic constants](magic_constant.md) in multiple places, conflicting the "[DRY](dry.md)" principle etc. It can also show if the guy knows things usually unknown to beginners such as that the modulo operation with non-power-of-two is usually expensive and we want to minimize its use. However it is greatly useful even when an experienced programmer faces it because it can serve a good, deeper discussion about things like [optimization](optimization.md); while FizzBuzz itself has no use and optimizing algorithm that processes 100 numbers is completely pointless, the problem is similar to some problems in practice in which the approach to solution often becomes critical, considering [scalability](scalability.md). In practice we may very well encounter FizzBuzze's big brother, a problem in which we'll need to check not 100 numbers but 100 million numbers per second and check not only divisibility by 3 and 5, but by let's say all [prime numbers](prime.md). Problems like this come up e.g. in [cryptography](cryptography.md) all the time, so we really have to come to discussing [time complexity](time_complexity.md) classes, [instruction sets](isa.md) and hardware acceleration, [parallelism](parallelism.md), possibly even [quantum computing](quantum.md), different [paradigm](paradigm.md)s etc. So really FizzBuzz is like a kind of great conversation starter, a bag of topics, a good training example and so on.

TODO: some history etc.

## Implementations

Let's see how we can implement, improve and [optimize](optimization.md) FizzBuzz in [C](c.md). Keep in mind the question of scalability, i.e. try to imagine how the changes we make to the algorithm would manifest if the problem grew, i.e. if for example we wanted to check divisibility by many more numbers than just 1 and 5 etc. We will only focus on optimizing the core of the algorithm, i.e. the divisibility checking, without caring about other things like optimizing printing the commas between numbers and whatnot. Also we'll be supposing all compiler optimization are turned off so that the excuse "compiler will optimize this" can't be used :)

For starters let us write a kind of vanilla, [naive](naive.md) solution that everyone will likely come up with as his first attempt. A complete noob will fail to produce even this basic version, a slightly advanced programmer (we might say a "[coder](coding.md)") may submit this as the  [final solution](final_solution.md).

```
#include <stdio.h>

int main(void)
{
  for (int i = 1; i <= 100; ++i)
  {
    if (i != 1)
      printf(", ");

    if (i % 3 == 0 && i % 5 == 0)
      printf("FizzBuzz");
    else if (i % 3 == 0) // checking divisibility by 3 again :/
      printf("Fizz");
    else if (i % 5 == 0) // checking divisibility by 5 again :/
      printf("Buzz");
    else
      printf("%d",i);
  }

  putchar('\n');
  return 0;
}
```

It [works](just_werks.md), however with a number of issues. Firstly we see that for every number we check we potentially test the divisibility by 3 and 5 twice, which is not [good](good.md), considering division (and modulo) are one of the slowest instructions. We also reuse the magic constants 3 and 5 in different places, which would start to create a huge mess if we were dealing with many more divisors. There is also a lot of branching, in the main divisibility check we may jump up to three times for the checked number -- jump instruction are slow and we'd like to avoid them (again, consider we were checking e.g. divisibility by 1000 different numbers). A first, tiny optimization (that here will likely be performed automatically) to notice is that `i % 3 == 0 && i % 5 == 0` can be changed to just `i % 15 == 0`.

When asked to optimize the algorithm a bit more one might come up with something like this:

```
#include <stdio.h>

int main(void)
{
  for (int i = 1; i <= 100; ++i)
  {
    if (i != 1)
      printf(", ");

    int printNum = 1;

    if (i % 3 == 0)
    {
      printf("Fizz");
      printNum = 0;
    }

    if (i % 5 == 0)
    {
      printf("Buzz");
      printNum = 0;
    }

    if (printNum)
      printf("%d",i);
  }

  putchar('\n');
  return 0;
}
```

Now we check the divisibility by 3 and 5 only once for each tested number, and also keep only one occurrence of each constant in a single place, that's good. But we still keep the slow branching.

A bit more experienced programmer may now come with something like this:

```
#include <stdio.h>

int main(void)
{
  for (int i = 1; i <= 100; ++i)
  {
    if (i != 1)
      printf(", ");

    switch ((i % 3 == 0) + ((i % 5 == 0) << 1))
    {
      case 1: printf("Fizz"); break;
      case 2: printf("Buzz"); break;
      case 3: printf("FizzBuzz"); break;
      default: printf("%d",i); break;
    }

  }

  putchar('\n');
  return 0;
}
```

This solution utilizes a [switch](switch.md) structure to only perform single branching in the divisibility check, based on a 2 bit value that in its upper bit records divisibility by 5 and in the lower bit divisibility by 3. This gives us 4 possible values: 0 (divisible by none), 1 (divisible by 3), 2 (divisible by 5) and 3 (divisible by both). The switch structure by default creates a jump table that branches right into the correct label in O(1).

We can even go as far as avoiding any branching at all with so called [branchless programming](branchless.md), even though in this specific case saving one branch is probably not worth the cost of making it happen. But for the sake of completeness we can do e.g. something as follows.

```
#include <stdio.h>

char str[] = "\0\0\0\0\0\0\0\0Fizz\0\0\0\0Buzz\0\0\0\0FizzBuzz";

int main(void)
{
  for (int i = 1; i <= 100; ++i)
  {
    if (i != 1)
      printf(", ");

    // look mom, no branches!
    char *s = str;

    *s = '1'; // convert number to string
    s += i >= 100;
    *s = '0' + (i / 10) % 10;
    s += (*s != '0') | (i >= 100);
    *s = '0' + i % 10;

    int offset = ((i % 3 == 0) + ((i % 5 == 0) << 1)) << 3;
    printf(str + offset);
  }

  putchar('\n');
  return 0;
}
```

The idea is to have a kind of [look up table](lut.md) of all options we can print, then take the thing to actually print out by indexing the table with the 2 bit divisibility value we used in the above example. Our lookup table here is the global string `str`, we can see it rather as an array of zero terminated strings, each one starting at the multiple of 8 index (this alignment to power of two will make the indexing more efficient as we'll be able to compute the offset with a mere bit shift as opposed to multiplication). The first item in the table is initially empty (all zeros) and in each loop cycle will actually be overwritten with the ASCII representation of currently checked number, the second item is "Fizz", the third item is "Buzz" and last one is "FizzBuzz". In each loop cycle we compute the 2 bit divisibility value, which will be a number 0 to 3, bit shift it by 3 to the left (multiply it by 8) and use that as an offset, i.e. the place where the printing function will start printing (also note that printing will stop at encountering a zero value). The conversion of number to ASCII is also implemented without any branches (and could be actually a bit simpler as we know e.g. the number 100 won't ever be printed). However notice that we pay a great price for all this: the code is quite ugly and unreadable and also performance-wise we many times waste time on converting the number to ASCII even if it then won't be printed, i.e. something that a branch can actually prevent, and the conversion actually further uses modulo and division instructions which we are trying to avoid in the first place... so at this point we probably overengineered this.

If the problem asks for shortest code, even on detriment of [readability](readability.md) and efficiency, we might try **the [code golfer](code_golf.md) approach**:

```
#include <stdio.h>
#define P printf(
int i;int main(){while(i<100){if(i++)P", ");int a=!(i%3)+!(i%5)*2;if(a)P"FizzBuzz\0Fizz"+(4+(a==1)*5)*(a!=3));else P"%d",i);}P"\n");}
```

It's almost definitely not minimal but can be a good start.

TODO: comun