SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

特集記事

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

PEARライブラリ活用 (6)


  • X ポスト
  • このエントリーをはてなブックマークに追加

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

  • X ポスト
  • このエントリーをはてなブックマークに追加

はじめに

 今日私たちが利用する計算機は、特定の範囲の整数(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数を計算する

次のページ
ベンチマーク (Benchmark)

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
特集記事連載記事一覧

もっと読む

この記事の著者

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

静岡県榛原町生まれ。一橋大学経済学部卒業後、NECにてシステム企画業務に携わるが、2003年4月に念願かなってフリーライターに転身。Microsoft MVP for Visual Studio and Development Technologies。執筆コミュニティ「WINGSプロジェクト」代表。主な著書に「独習シリーズ(Java・C#・Python・PHP・Ruby・JSP&サーブレットなど)」「速習シリーズ(ASP.NET Core・Vue.js・React・TypeScript・ECMAScript、Laravelなど)」「改訂3版JavaScript本格入門」「これからはじめるReact実践入門」「はじめてのAndroidアプリ開発 Kotlin編 」他、著書多数

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

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

WINGSプロジェクトについて>有限会社 WINGSプロジェクトが運営する、テクニカル執筆コミュニティ(代表 山田祥寛)。主にWeb開発分野の書籍/記事執筆、翻訳、講演等を幅広く手がける。2018年11月時点での登録メンバは55名で、現在も執筆メンバを募集中。興味のある方は、どしどし応募頂きたい。著書記事多数。 RSS X: @WingsPro_info(公式)、@WingsPro_info/wings(メンバーリスト) Facebook

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/2807 2010/01/05 11:15

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング