commons-math 解読 (6) : 連分数 ContinuedFraction

今回は連分数を表す ^{org.apache.commons.math.util.}ContinuedFraction クラスを見ていきます。

連分数

連分数の詳細に関してはこちらやwikipedia:連分数などを参照のこと。　後でサンプルに用いるため、1つだけ連分数の具体例を見ておきます（参照）：

$\pi = 3 + \frac{1^2}{6 + \frac{3^2}{6 + \frac{5^2}{6 + \frac{7^2}{6 + \frac{9^2}{6 + \cdots}}}}}$

これは書くのも見るのも面倒なので、こんな感じに書かれることもあります：

$\pi = 3 + \, \frac{1^2}{6 +} \, \frac{3^2}{6 +} \, \frac{5^2}{6 +} \, \frac{7^2}{6 +} \, \frac{9^2}{6 +} \, \cdots$

まぁ、どっちもどっちかな。　一般に連分数は

$a_0 + \, \frac{b_0}{a_1 +} \, \frac{b_1}{a_2 +} \, \frac{b_2}{a_3 +} \, \frac{b_3}{a_4 +} \, \frac{b_4}{a_5 +} \, \cdots$

として、{a_n}, {b_n} を定めれば決まります。

ちなみに、この ContinuedFraction クラスは org.apache.commons.math.fraction パッケージの Fraction クラスや BigFraction クラスとは何の関係もないようです。

ContinuedFraction クラス

さて、では ContinuedFraction クラスを見ていきましょう。　使い方の手順はこんな感じ：

ContinuedFraction のサブクラスを作成する
ContinuedFraction オブジェクトを取得する
ConitnuedFraction#evalueate() メソッドによって（必要な精度で）値を取得する

もしくは

CotinuedFraction の無名クラスを作成して ContinuedFraction オブジェクトを取得する
ConitnuedFraction#evalueate() メソッドによって（必要な精度で）値を取得する

まぁ、要は ContinuedFraction クラスは抽象クラスだよ?ってだけです。　実装する必要がある抽象メソッドは以下の2つ：

    protected abstract double getA(int n, double x);
    protected abstract  double getB(int n, double x);

これらは上記の例の下に書いた一般形の {a_n}, {b_n} を計算するメソッドで、x は次に見る評価点です（上記のπの例では評価点に依存しない）。　精度を指定して値を評価する evaluate() メソッドはいくつかオーバーロードされてます：

    public double evaluate(double x){ ... }
    public double evaluate(double x, double epsilon){ ... }
    public double evaluate(double x, int maxIterations){ ... }
    public double evaluate(double x, double epsilon, int maxIteration){ ... }

x は評価点です。　この変数 x は「実行時に指定できるが、全評価段階で一定」の値です。　getA(), getB() メソッドの第2引数の double 型パラメータはこの値が渡されます。　ちなみに、getA(), getB() メソッド第1引数の n は「実行時には指定できないが、各評価段階で変化する」値です。　使い分けられれば柔軟性が増しそう。
epsilon は前回みたdouble 値に対する equals() メソッドの、精度を指定する double 型の第3引数と同じでしょう。
maxIterations は計算する（最大の） convergent を指定する整数です。　まぁ分数の繰り返し回数と思ってもいいかと。　詳しくはこちら（「convergent」で検索してちょ）。

実行してみる

やっぱ、こういうのは実行してみないとね。　ってことで、次の3つの方法で上記 $\90dpi \pi$ の連分数を計算してみました：

Java だけで実装 (Pure Java)
クロージャを使用して実装 (Groovy Closure)
Groovy コード中にて無名クラスで実装 (Groovy Anonymous)

Pure Java

まずは Java オンリーの実装：

import org.apache.commons.math.util.ContinuedFraction;

public class Pi extends ContinuedFraction{

    @Override
    protected double getA(int n, double x) {
        return n == 0 ? 3 : 6;
    }

    @Override
    protected double getB(int n, double x) {
        double y = (2 * n) - 1;
        return y * y;
    }
}

getA(), getB() メソッドの実装はこんなんだって示すためのサンプルと言ってもいいかも。　実行は後でまとめて。

Groovy Closure

次は Groovy のクロージャを使った実装。　groovy.lang.Closure は使ってますが、このクラス自体は Java で実装してます：

import groovy.lang.Closure;
import org.apache.commons.math.util.ContinuedFraction;

public class ClosureContinuedFraction extends ContinuedFraction{

    private final Closure a;
    private final Closure b;

    public ClosureContinuedFraction(Closure a, Closure b){
        this.a = a;
        this.b = b;
    }

    @Override
    protected double getA(int i, double v) {
        return (Double)this.a.call(new Object[]{i, v});
    }

    @Override
    protected double getB(int i, double v) {
        return (Double)this.b.call(new Object[]{i, v});
    }
}

クロージャ・プロパティを final 宣言する必要はないかもね*1。　~~少々パフォーマンスは良くなるかも知れないけど~~ （←あまりパフォーマンスに影響なし。）　このクラスは Groovy コード内でこんな感じに使います：

def a = { int n, double x ->
    return (n == 0) ? 3d : 6d
}

def b = { int n, double x ->
    double y = (2d * n) - 1d
    return y * y
}

def cfClosure = new ClosureContinuedFraction(a, b)

Groovy Anonymous

最後は Groovy コード内での無名クラス：

def cfAnonymous = new ContinuedFraction(){

    @Override
    protected double getA(int n, double x) {
        return (n == 0) ? 3d : 6d
    }

    @Override
    protected double getB(int n, double x) {
        double y = (2d * n) - 1d
        return y * y
    }
}

まぁ、何てことないですね。

パフォーマンス

さて、上記の3つの ContinuedFraction クラスを実行してみましょう。　実行するコードはこんな Groovy コード：

perform(new Pi(), 'Pure Java')
perform(cfClosure, 'Groovy Closure')
perform(cfAnonymous, 'Groovy Anonymous')

def perform(cf, message){
    def epsilon = 0.0000001d
    def start = System.currentTimeMillis()

    10000.times{
        cf.evaluate(0d, epsilon)
    }

    def end = System.currentTimeMillis()
    println("$message : ${end - start} ms")
}

cfClosure はクロージャによる実装、cfAnonymous は無名クラスによる実装。　精度を指定して 10000 回評価を行っています。　結果は

Pure Java : 125 ms
Groovy Closure : 2906 ms
Groovy Anonymous : 1000 ms

うーむ、クロージャを使うと Pure Java の20倍以上になっとる。　無名クラスだとかろうじて10倍にならずに済んだってところ。　まぁ、1回1msもかかってないから気にする程でもないのか・・・

追記

クロージャを値に持つ Map を使って

[getA:a, getB:b] as ContinuedFraction    // a, b はクロージャ

のように ContinuedFraction オブジェクトを作成することもできます。　これを以下のように実行すると

def a = { int n, double x ->
    return (n == 0) ? 3d : 6d
}

def b = { int n, double x ->
    double y = (2d * n) - 1d
    return y*y
}

perform([getA:a, getB:b] as ContinuedFraction, 'Groovy Closure Map')