tinycc-devel
[Top][All Lists]

## [Tinycc-devel] fib.c

 From: Laszlo Hars Subject: [Tinycc-devel] fib.c Date: Thu, 15 Mar 2007 16:38:07 -0700 User-agent: Web-Based Email 4.9.21

Today I came across this wonderful piece of work. Congratulations, and
thanks for making it widely available!

After trying the example fib.c, I'd like to note the following:

The included fib.c is the notorious example, how you should not compute
Fibonacci numbers. I understand that it is for comparisons to other
compilers and for benchmarking, but one could get the impression that
this program can be used in real life, but it would be a bad idea. The
number of recursive calls is proportional to fib(n), which can be as
large as 2**31, without overflow. Just try to run the program with n=46
(and be patient). If you want to demonstrate recursive calls, here is an
alternative, which saves already computed results, and so the number of
recursive calls is never more than n:

unsigned fib(n)
{
static unsigned Fibs[48] = {48*0};
return n < 3 ? 1 : n > 47 ? 0 : Fibs[n] > 0 ? Fibs[n] : Fibs[n] =
fib(n-1)+fib(n-2);
}

The right data type is unsigned, because the Fibonacci numbers are
positive integers. We ought to signal overflow (with returning 0), and
print the result with "printf("fib(%d) = %u\n", n, fib(n));"

Of course, it could be even more interesting with 64-bit unsigned
integers. It works perfectly up to n=93, and lightning fast:

#include <stdio.h>

unsigned long long fib(n)
{
static unsigned long long Fibs[94] = {94*0};
return n < 3 ? 1 : n > 93 ? 0 : Fibs[n] > 0 ? Fibs[n] : Fibs[n] =
fib(n-1)+fib(n-2);
}

int main(int argc, char **argv)
{
int n;
if (argc < 2) {
printf("usage: fib n\n"
"Compute nth Fibonacci number\n");
return 1;
}
n = atoi(argv[1]);
printf("fib(%d) = %I64u\n", n, fib(n));
return 0;
}