第6章 並行処理の機能強化 : 問題 9 : フィボナッチ数の計算を並列化

問題

ひとつ前のブログを参照してくださいと言いたいとこだけど、一応書いときますか…

フィボナッチ数の計算を並列化するためにArrays.parallelPrefixメソッドを使え
n 番目のフィボナッチ数は

F = | 1 1 |
    | 1 0 |

とした場合の F の n 乗の計算結果の左上の要素の値である

準備

まず 2×2 行列のクラスMatrixを定義する

■ 行列クラス

public class Matrix {
    /**
     * 要素の配列<br>
     * 1オリジンなのでインデックス 0 は使わない
     */
    private double[][] a = new double[2+1][2+1];
    
    /** default コンストラクタ */
    public Matrix() { }
    /** 全ての要素を指定するコンストラクタ */
    public Matrix(double a11, double a12, double a21, double a22) {
        a[1][1] = a11;
        a[1][2] = a12;
        a[2][1] = a21;
        a[2][2] = a22;
    }
    /** 要素の取得 */
    public double get(int row, int column) {
        return a[row][column];
    }
    /** 要素の設定 */
    public void set(int row, int column, double value) {
        a[row][column] = value;
    }
    /** 乗算 */
    public Matrix multiply(Matrix other) {
        Matrix result = new Matrix();
        for (int row = 1; row <= 2; row++) {
            for (int column = 1; column <= 2; column++) {
                result.a[row][column] = 0;
                for (int i = 1; i <= 2; i++) {
                    result.a[row][column] += a[row][i] * other.a[i][column];
                }
            }
        }
        return result;
    }
}

本当は、加算やスカラー積も定義したいが、ここでは乗算だけにとどめておく

解答

行列 で配列を埋め尽くし、その配列にArrays.parallelPrefixメソッドを適用すると が得られる

final Matrix F = new Matrix(1, 1, 1, 0);
Matrix[] array = new Matrix[100];

Arrays.parallelSetAll(array, i -> F);            // 行列 F で配列を埋め尽くす
Arrays.parallelPrefix(array, Matrix::multiply);  // F の n 乗を計算
Arrays.stream(array).forEach(m -> System.out.println(m.get(1,1)));