FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

今どきのGCCは再帰を書いても再帰を出さない (exponentialだとどうなる?)

「その数式、プログラムできますか?」→「その数式、どのようにコンパイルされますか?」になってしまっている。っていうか再帰一個で立ち止まりすぎだろ!

その数式、プログラムできますか?

その数式、プログラムできますか?

指数関数の計算だと、どうなるのかやってみようと思った。再帰を入れている構造と、そもそも再帰を使わずにループで表現したバージョンを用意した。

int exponential0 (int n, int a) {
    if (n == 0) { return 1; }
    return exponential0 (n-1, a) * a;
}


int exponential1 (int n, int a) {
    if (n == 0) return 1;
    int result = exponential1 (half(n), a * a);
    if (odd (n)) result = result * a;
    return result;
}


int exponential2 (int n, int a) {
    if (n == 0) return 1;
    int result = exponential1 (half(n), a);
    result *= result;
    if (odd (n)) result = result * a;
    return result;
}


int exponential3 (int n, int a)
{
    int result = 1;
    while (1) {
        if (n == 0) {
            return result;
        }
        if (odd (n)) {
            result = result * a;
        }
        a = a * a;
        n = half (n);
    }
}

5337の累乗を計算した結果。

  • exponential0 : 167命令。ループに直ってはいるが、時間計算量としては線形のまま
  • exponential1 : 93命令。時間計算量としてはlogにまで落ちているが、再帰が発生することによるオーバヘッド多い。
  • exponential2 : 90命令。同上。
  • exponential3 : 45命令。再帰を省略した上に時間計算量がlogになっている。

まあ当然といえば当然だが、コンパイラに任せずに、アルゴリズムをしっかり考えたほうが結果的には高速なプログラムが作れるってことさね。