Cでもフィボナッチを書いてみる

Scheme演習第2回-問1と続・Scheme演習第2回-問1で、schemeで再帰と末尾再帰を用いてフィボナッチ数列を解いてみたが、練習のためにCでも書いてみた。（すぐできるか試してみたかった）
今回は計算結果を出力するのはおいといて、いきなり時間のみを計測。

#include <stdio.h>
#include <time.h>

static int fib1(int n)
{
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return (fib1(n - 1) + fib1(n - 2));
    }
}

static int fib_tail(int n, int a, int b)
{
    if (n == 0) {
        return b;
    } else if (n == 1) {
        return a + b;
    } else {
        return fib_tail(n-1, b, a+b);
    }
}

static int fib2(int n)
{
    return fib_tail(n, 1, 0);
}

int main(int argc, char* argv[])
{
    int n = 10;
    int loop = 1000000;
    int i;
    clock_t start, end;
    
    start = clock();
    for (i = 0; i < loop; i++) {
        fib1(n);
    }
    end   = clock();
    printf("fib1 clock: %.2f [ms]\n", (double)(end-start)*1000.0/CLOCKS_PER_SEC);

    start = clock();
    for (i = 0; i < loop; i++) {
        fib2(n);
    }
    end   = clock();
    printf("fib2 clock: %.2f [ms]\n", (double)(end-start)*1000.0/CLOCKS_PER_SEC);

    return 0;
}

nを大きくしすぎると、無駄な再帰をしている方のfib1で時間がかかりすぎるので適度に10で。

$ ./a.out
fib1 clock: 1890.00 [ms]
fib2 clock: 70.00 [ms]

たったの10でもこれだけ実行時間に差がでるんですね。
ちなみに計算の繰り返し回数は100万回です。

時間計測関数について

今回は、C言語-時間の計測を参考にclockを使用して時間を計測。time関数で求める場合とは以下のように異なるそうな。（常識かも）

clock() で求まる時間はそのプロセスが消費したプロセッサ時間になります． 一方，time(time_t *) で求まる時間は歴時間です．
つまり，clock() で求めた時間は実時間とは異なります． （そのプロセスが実行されている間，プロセッサリソースのほぼ100％を占有している場合は，ほぼ実時間になります） time(time_t *) は精度は低いですがプロセスの切り替えに影響されず実時間を取得できます．

C言語-時間の計測

場合によって使い分けることが必要ですね。