tinycc-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[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;
}





reply via email to

[Prev in Thread] Current Thread [Next in Thread]