Fibonacci数の計算で学ぶ、PHPでの多倍長整数の扱いとベンチマーク方法

PEARライブラリ活用 (6)

Math_Fibonacciの実装

　f(5000)の計算時間の平均は0.156秒、標準偏差は0.494でした。標準偏差はデータのばらつき具合を示すものですが、この値は大きすぎると言わざるを得ません。何かが間違っています。

　実は、Benchmark_Iterateを使ってMath_Fibonacciのベンチマークを行っても、意味のある結果は得られないのです（Benchmark_IterateとMath_Histogramの使い方を紹介するためにあえて載せました）。先の結果をよく見ると、時間がかかっているのは1回目の計算だけだということが分かります。統計量を鵜呑みにしてはいけないということのよい例です。

　ソースコードを読むと確認できますが、Math_Fibonacciは一度計算した結果を記憶しているのです（厳密に言えば、f(47)からf(500)はあらかじめ計算してあります）。そのため、1回目の計算には時間がかかりますが、2回目からは一瞬で終わっているのです（計算結果を記憶すれば2回目以降が必ず速くなるというわけではありませんが、この場合は速くなっています）。

　これが良い実装だとは筆者には思えません。Fibonacci数の計算は、再帰的な処理の例題としてよくあるものです。一般的な手続き型言語でこの問題を再帰的に実装すると、計算は非常に遅くなってしまいます。それを解決する手段として、計算結果を記憶するという方法が採られます。しかし、それはあくまで例題で練習する場合のことです。

　この特殊な実装のために、計算できるFibonacci数は、とても小さい範囲に限られてしまっています。PHPが利用できるメモリはphp.iniで設定できますが、f(65536)の計算には256MBでは足りません。f(100000)の計算には1GBでも足りません。

素朴な実装1 (Math_Integer)

　Math_Fibonacciが利用する多倍長整数の機能は、Math_Integerによって提供されています。これを用いて、Fibonacci関数を実装し直してみましょう。

simple-fib-integer.php

include_once 'Math/IntegerOp.php';

function &fib($n){
    $one=new Math_Integer('1');//多倍長整数オブジェクト
    if(Math_IntegerOp::compare($n,$one)==0) return $one;//compareで比較
    
    $two=new Math_Integer('2');
    if(Math_IntegerOp::compare($n,$two)==0) return $one;
    
    $bar=new Math_Integer('1');
    $baz=new Math_Integer('1');
    for($i=new Math_Integer('3'); Math_IntegerOp::compare($i,$n)<=0;
        $i=Math_IntegerOp::add($i,$one)){//addで加算
        $foo=$bar;
        $bar=$baz;
        $baz=Math_IntegerOp::add($foo,$bar);
    }
    return $baz;
}

　多倍長整数はMath_Integerのオブジェクトです。比較には、等号や不等号ではなく、Math_IntegerOp::compareを使わなければなりません（第1引数が小さいときに戻り値が負になります）。加算にも、単なる+ではなくMath_IntegerOp::addを使います。これらの点に注意すれば、計算のアルゴリズム自体は単純です。

　この実装なら、Math_Fibonacciより遙かに大きな値まで計算できます。

　あとでベンチマークをするために、php simple-fib-integer 10などとすると、f(2の10乗)を計算するようにしておきましょう（Math_IntegerOp::powはべき乗を計算するメソッド、$argvはコマンドライン引数を格納する配列です）。

simple-fib-integer.php

$n=Math_IntegerOp::pow(new Math_Integer('2'),
    new Math_Integer($argv[1]));

require_once 'Benchmark/Timer.php';
$timer=new Benchmark_Timer;
$timer->start();
$result=fib($n);
$timer->stop();
//print "{$result->toString()}\n";

$profile=$timer->getProfiling();
print "{$n->toString()},{$profile[1]['diff']}\n";

素朴な実装2 (GNU Multiple Precision)

　GNU Multiple Precision (GMP)はC言語やC++で多倍長整数を利用するためのライブラリです。一部のPHPにはこのライブラリ（の一部）を利用するための関数群が備わっています。先に利用したMath_Integerは、GMP関数がサポートされているならそれらを使い、サポートされていないなら別の関数群（BC Math）を使うようになっています。

　GMPをサポートしている環境で利用することが確実なら、Math_Integer経由でGMPを使うよりも、直接GMP関数を描いた方がコードは簡潔になります（Math_IntegerがサポートしていないGMP関数を利用できるというメリットもあります）。PHP 5.1以降ではWindows版でもサポートされているはずですが、筆者の環境のPHPには含まれていなかったため、この節の動作確認はFedora 8上で行いました。

　Fibonacci数を計算する関数は次のようになります。

simple-fib-gmp.php

function fib($n){
    if(gmp_cmp($n,'1')==0) return 1;
    if(gmp_cmp($n,'2')==0) return 2;
    
    $bar=1;
    $baz=1;
    for($i=3; gmp_cmp($i,$n)<=0; $i=gmp_add($i,'1')){
        $foo=$bar;
        $bar=$baz;
        $baz=gmp_add($foo,$bar);
    }
    return $baz;
}

　先の場合と同じように、php simple-fib-gmp 10などとすると、f(2の10乗)を計算するようにしておきましょう。

simple-fib-gmp.php

$n=gmp_pow('2',intval($argv[1]));

require_once 'Benchmark/Timer.php';
$timer=new Benchmark_Timer;
$timer->start();
$result=fib($n);
$timer->stop();
//print gmp_strval($result)."\n";

$profile=$timer->getProfiling();
print gmp_strval($n).",{$profile[1]['diff']}\n";

C言語による実装

　そもそも、PHPのようなスクリプト言語は、計算速度を求めるときに使うものではありません。Fibonacci数を速く計算したいときにはC言語を使うといいでしょう。実は、GMPにはFibonacci数を求める関数mpz_fib_uiが用意されているため、C言語で実装するのは簡単です（残念なことに、この関数mpz_fib_uiは、PHPに備えられたGMP関数には含まれていません）。

fib.c

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

int main(int argc, char *argv[]){
    long x=atol(argv[1]);
    mpz_t result;
    mpz_init(result);
    mpz_fib_ui(result,x);
    printf("%s\n",mpz_get_str(NULL,10,result));
    return 0;
}

　次のようにコンパイル・実行すると、f(10)を計算します。

$ gcc fib.c -o fib -lgmp
$ ./fib 10
55