Computational complexity of modulos and FizzBuzz

Question

So I don't want to go into whether this is the most perfect code for the FizzBuzz challenge.

For those unfamiliar with FizzBuzz, there are four rules in printing out a range of 1-100:

Print out all numbers;
If the number is divisible by 3, print "Fizz" instead;
If the number is divisible by 5, print "Buzz" instead;
If the number is divisible by both 3 and 5, print "FizzBuzz".)

I ran two implementations, to compare their speed:

# Code A
%%timeit
for i in range(1,10001):
    if i % 15 == 0:
        print('FizzBuzz')
    elif i % 3 == 0:
        print('Fizz')
    elif i % 5 == 0:
        print('Buzz')
    else:
        print(i)

# Code B
%%timeit
for i in range(1,10001):
    if i % 5 == 0 and i % 3 == 0:
        print('FizzBuzz')
    elif i % 3 == 0:
        print('Fizz')
    elif i % 5 == 0:
        print('Buzz')
    else:
        print(i)

Despite the extra if evaluation of Code B, it consistently ran quicker than Code A. Does a larger number result in a slower modulo? What is the underlying reason for this?

user_6074376 · Answer

The main reason I could think of is perhaps optimization.

Version B uses the same operation a few times, namely:

i mod 5
i mod 3

A reasonably intelligent compiler/interpreter might spot this, and calculate these intermediate results. By doing so, it would be able to immediately calculate the entire if-block with only 2 mod operations.

In short, I think the code that ends up being executed might look something like this:

for i in range(1,10001):
    a = i % 5
    b = i % 3
    if a == 0 and b == 0:
        print('FizzBuzz')
    elif b == 0:
        print('Fizz')
    elif a == 0:
        print('Buzz')
    else:
        print(i)

However, the code in block A is perhaps too complicated. By that, I mean the compiler will always be forced to execute 3 mod operations. Unless it would somehow be able to spot that 15 = 3 * 5, and use that logic to re-work the if-statement.

Computational complexity of modulos and FizzBuzz

1 Answers