Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

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

PEARライブラリ活用 (6)

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2008/08/18 14:00

32ビットや64ビットなど、通常で用意されている範囲で収まらない整数の計算を行いたい場合、多倍長整数という仕組みを利用するのが一般的です。本稿では、Fibonacci数の計算を例にして、PHPで多倍長整数を扱う方法を紹介し、そのパフォーマンスを調べます。Fibonacci数や多倍長整数には興味のない方も、パフォーマンスの調べ方(ベンチマークや統計処理方法)は、きっと参考になるでしょう。

目次

はじめに

 今日私たちが利用する計算機は、特定の範囲の整数(32ビットあるいは64ビット整数など)は簡単かつ高速に計算できるようになっています。しかしながら、その範囲に収まらない整数を扱いたいこともあります。そういう場合には、多倍長整数という仕組みを利用するのが一般的です。

 本稿では、Fibonacci数の計算を例にして、PHPで多倍長整数を扱う方法を紹介し、そのパフォーマンスを調べます。Fibonacci数や多倍長整数には興味のない方も、パフォーマンスの調べ方(ベンチマークや統計処理方法)は、きっと参考になるでしょう。

必要な環境

 XAMPP for Windows 1.6.4に含まれるPHP 5.2.4で動作を確認しました。利用したPearのパッケージは次のとおりです。

  • Benchmark 1.2.6
  • Math_Fibonacci 0.8
  • Math_Histogram 0.9.0 beta
  • Math_Integer 0.8
  • Math_Stats 0.8.5

準備

 Math_HistogramだけはXAMPPに含まれていなかったため、コマンドプロンプトで次のようにインストールしました([コマンドの実行前に、c:\xampp\php\pear.iniの「"\xampp」を「"C:\xampp」に修正)。β版なので-fを付けてインストールしました。

c:
cd \xampp\php
pear install -f Math_Histogram

 本稿では、コマンドプロンプト(あるいはシェル)上でPHPのプログラムを実行します。PHPのための設定ファイルがいつもと違う場合があるので注意してください(筆者の環境では、Webサーバのためのphp.iniは「C:\xampp\apache\bin\php.ini」ですが、コマンドプロンプトのためのphp.iniは「C:\xampp\php\php.ini」です)。

Fibonacci数(Math_Fibonacci)

 「f(0)=0, f(1)=1, f(n+2)=f(n+1)+f(n)(nは0以上の整数)」で定義されるような数をFibonacci数と言います(本稿では「f」はFibonacci数のこととします)。初めの数個を列挙すると、「0, 1, 1, 2, 3, 5, 8, 13, 21, 34...」のようになります(連続する2つの数の和が、次の数になっています)。

 Fibonacci数には、「連続する2つの数の比が黄金比に近づく」というような興味深い性質(文献[1]を参照)の他に、探索アルゴリズムなどにおいて実用上の価値もあることが知られています(文献[2]を参照)。

 少し計算してみると分かりますが、Fibonacci数はとても速く増大します。そのため、nを少し大きくすると、f(n)は簡単に32ビット整数や64ビット整数の範囲を出てしまいます。そのようなf(n)を計算するためには、一般に多倍長整数と呼ばれるものを利用しなければなりません。

 多倍長整数は多くのプログラミング言語でサポートされています。PHPでも、Math_Integerというパッケージを利用することで、簡単に多倍長整数を扱うことができます。Math_Integerを利用するパッケージの一つにMath_Fibonacciがあり、これを利用することで、大きなFibonacci数を簡単に計算することができます。

 Math_FibonacciクラスのtermメソッドでFibonacci数を計算します。

fib.php
<?php
include_once 'Math/Fibonacci.php';

$result=Math_Fibonacci::term(10);
print "f(10) = {$result->toString()}\n";//f(10) = 55
?>

 Math_Fibonacciクラスには、ここで利用したtermの他に、次のようなメソッドが用意されています。リファレンスマニュアルを参照してください。

Math_Fibonacciクラスの主なメソッド
メソッド 処理
closestTo 引数に最も近いFibonacci数を求める
decompose 引数をFibonacci数の和で表す
getIndexOf f(n)からnを求める
isFibonacci 引数がFibanacci数かどうかを調べる
series 指定した範囲のFibonacci数を計算する

  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • 山田 祥寛(ヤマダ ヨシヒロ)

    静岡県榛原町生まれ。一橋大学経済学部卒業後、NECにてシステム企画業務に携わるが、2003年4月に念願かなってフリーライターに転身。Microsoft MVP for ASP/ASP.NET。執筆コミュニティ「WINGSプロジェクト」代表。 主な著書に「入門シリーズ(サーバサイドAjax/XMLD...

  • WINGSプロジェクト 矢吹 太朗(ヤブキ タロウ)

    <WINGSプロジェクトについて> 有限会社 WINGSプロジェクトが運営する、テクニカル執筆コミュニティ(代表 山田祥寛)。主にWeb開発分野の書籍/記事執筆、翻訳、講演等を幅広く手がける。2012年2月時点での登録メンバは37名で、現在も執筆メンバを募集中。興味のある方は、どしどし応募頂き...

おすすめ記事

All contents copyright © 2006-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5