The FizzBuzz problem is as follows:
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”
Below is a simple python implementation:
for i in range(1,101):
if i%3 == 0 and i%5 == 0:
print 'FizzBuzz'
elif i%3 == 0:
print 'Fizz'
elif i%5 == 0:
print 'Buzz'
else:
print str(i)However, this can be made more efficient, though at the expense of readability. Below it is written in C, and takes advantage of the fact that the Fizz Buzz pattern repeats every 15. This allows for the removal of the conditionals.
#include <stdio.h>
int main(int argc, char *argv[]){
for(int i=1; i<77; i+=15)
printf("%u\n%u\nFizz\n%u\nBuzz\nFizz\n%u\n%u\nFizz\nBuzz\n%u\nFizz\n%u\n%u\nFizzBuzz\n",
i, i+1, i+3, i+6, i+7, i+10, i+12, i+13);
printf("91\n92\nFizz\n94\nBuzz\nFizz\n97\n98\nFizz\Buzz\n");
return 0;
}This becomes the following assembly code from clang when set to maximum optimization (clang -S fizzbuzz.c -O3).
.section __TEXT,__text,regular,pure_instructions
.macosx_version_min 10, 11
.globl _main
.align 4, 0x90
_main: ## @main
.cfi_startproc
## BB#0:
pushq %rbp
Ltmp0:
.cfi_def_cfa_offset 16
Ltmp1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Ltmp2:
.cfi_def_cfa_register %rbp
pushq %rbx
subq $24, %rsp
Ltmp3:
.cfi_offset %rbx, -24
movl $14, 16(%rsp)
movl $13, 8(%rsp)
movl $11, (%rsp)
leaq L_.str(%rip), %rbx
movl $1, %esi
movl $2, %edx
movl $4, %ecx
movl $7, %r8d
movl $8, %r9d
xorl %eax, %eax
movq %rbx, %rdi
callq _printf
movl $29, 16(%rsp)
movl $28, 8(%rsp)
movl $26, (%rsp)
movl $16, %esi
movl $17, %edx
movl $19, %ecx
movl $22, %r8d
movl $23, %r9d
xorl %eax, %eax
movq %rbx, %rdi
callq _printf
movl $44, 16(%rsp)
movl $43, 8(%rsp)
movl $41, (%rsp)
movl $31, %esi
movl $32, %edx
movl $34, %ecx
movl $37, %r8d
movl $38, %r9d
xorl %eax, %eax
movq %rbx, %rdi
callq _printf
movl $59, 16(%rsp)
movl $58, 8(%rsp)
movl $56, (%rsp)
movl $46, %esi
movl $47, %edx
movl $49, %ecx
movl $52, %r8d
movl $53, %r9d
xorl %eax, %eax
movq %rbx, %rdi
callq _printf
movl $74, 16(%rsp)
movl $73, 8(%rsp)
movl $71, (%rsp)
movl $61, %esi
movl $62, %edx
movl $64, %ecx
movl $67, %r8d
movl $68, %r9d
xorl %eax, %eax
movq %rbx, %rdi
callq _printf
movl $89, 16(%rsp)
movl $88, 8(%rsp)
movl $86, (%rsp)
movl $76, %esi
movl $77, %edx
movl $79, %ecx
movl $82, %r8d
movl $83, %r9d
xorl %eax, %eax
movq %rbx, %rdi
callq _printf
leaq L_str(%rip), %rdi
callq _puts
xorl %eax, %eax
addq $24, %rsp
popq %rbx
popq %rbp
retq
.cfi_endproc
.section __TEXT,__cstring,cstring_literals
L_.str: ## @.str
.asciz "%u\n%u\nFizz\n%u\nBuzz\nFizz\n%u\n%u\nFizz\nBuzz\n%u\nFizz\n%u\n%u\nFizzBuzz\n"
.align 4 ## @str
L_str:
.asciz "91\n92\nFizz\n94\nBuzz\nFizz\n97\n98\nFizz\nBuzz"
.subsections_via_symbolsThe compiler has unrolled the loop, pulling out the 6 times the loop would run. Of course the true fastest method would be to simply print FizzBuzz directly as it is only 413 characters, 412 excluding the trailing new line.
Some simple profiling using the time command provides the following representative results.
time python fizzbuzz.py
real 0m0.026s
user 0m0.014s
sys 0m0.009s
time ./fizzbuzz
real 0m0.002s
user 0m0.000s
sys 0m0.002s
A clear speed improvement can be seen. Though this is an apples to oranges comparison as python is an interpreted and c a compiled language.