プログラミング言語 Standard ML 入門 (問題の解答例)

2.5 相互再帰的関数

問 2.10

最低利率が1%，残高1000万円以上の場合の利率が2%，残高が1000万円以下の場合の利率は，残高に比例して1%から2%まで連続して増えるものとする．この利率を表す関数 F を定義し，F を使って I と A を定義せよ．さらに，A(100.0,10)，A(100.0,20)，A(100.0,25)， A(100.0,30) の値をそれぞれ計算せよ．

解答例例えば以下のようにコード化できる．

   fun F x = if x > 2000.0 then 0.02
             else 0.01 + 0.01 * (x  - 1000.0) / 1000.0;
   fun I(x,n) = F(A(x,n - 1))
   and A(x,n) = if n = 0 then x
                else A(x,n-1)*(1.0+I(x,n));

これをSML#で実行すると，以下のような結果となる．

   # A(900.0, 10);
   val it = 988.102574973 : real
   # A(900.0, 20);
   val it = 1095.21279511 : real
   # A(900.0, 25);
   val it = 1157.91903751 : real
   # A(900.0, 30);
   val it = 1228.19345742 : real

(注１）教科書では A(100.0,10)， A(100.0,20)， A(100.0,25)， A(100.0,30) をそれぞれ計算せよ，との問題であるが，この範囲では Fの変化が結果に影響しないので，値を変えてある．

(注２）A(900.0, 30)の計算は、筆者の現在（Mon Jul 13 05:52:44 JST 2020）の環境では21秒ほど掛かる。

問 2.11

問2.10を実際試してみるとわかる通り，関数 A は n が大きくなると処理時間が膨大になり，実用に適さない．問2.7で定義した fastFib の考え方に習い， $A_{x}^{n}$ と $I_{x}^{n}$ の組を，以下の方針で同時に高速に計算する補助関数 auxAI を考えることができる．

1.

auxAI の引数は，目標とする年までの残りの年数 $k$ ，そのときの残高 $x$ ，および利率 $i$ の値の組とする．
2.

残りの年数が $0$ の場合は，引数をそのまま返せばよい．したがって auxAI(0, $x$ , $i$ ) は ( $x$ , $i$ ) である．
3.

$k$ が $0$ でない場合，与えられた $x$ と $i$ から1年先の $x^{\prime}$ と $i^{\prime}$ を求め，それらから $k-1$ 年先の値を求めればよいから，auxAI( $k$ , $x$ , $i$ ) は， auxAI(k-1, $x^{\prime}$ , $i^{\prime}$ ) を呼び出すことによって計算できる． $i^{\prime}$ は $F$ を前年の残高に適用して得られる値であり， $x^{\prime}$ は $x$ に $1+i^{\prime}$ を乗じたものである．

auxAI を補助関数として用い，残高 $x$ と年数 $n$ から $A_{x}^{n}$ と $I_{x}^{n}$ の組を計算する関数 fastAI を定義せよ．さらに，fastAI(100.0,100) と fastAI(100.0,1000) の値をそれぞれ計算せよ．

解答例 fastAIは以下のようにコード化できる．但し，Fは定義済みと仮定している．

  fun auxAI(n,x,i) = if n = 0 then (x,i)
                     else auxAI(n-1,x*(1.0 + F(x)),1.0 + F(x))
  fun fastAI(x,n) = auxAI(n,x,F(x));

SML#での実行結果は以下の通り．

   # fastAI(900.0,100);
   val it = (4305.75128361, 1.02) : real * real
   # fastAI(900.0,1000);
   val it = (236702870934.0, 1.02) : real * real

これらは一瞬で終了する．

問 2.12

上記の2つのプログラムで， $\left(\begin{array}[]{cc}1&0\\ 0&1\end{array}\right)$ の $20$ 乗と $30$ 乗を実際に計算し，かかった時間を比較せよ．

解答例筆者の現在の環境でtimeコマンドで計測した実行時間は以下の通り。

•
プログラム：(x (20, 1, 0, 0, 1), y (20, 1, 0, 0, 1), z (20, 1, 0, 0, 1), w (20, 1, 0, 0, 1))
```
   real    0m0.099s
   user    0m0.072s
   sys     0m0.024s
```
•
プログラム：(x (30, 1, 0, 0, 1), y (30, 1, 0, 0, 1), z (30, 1, 0, 0, 1), w (30, 1, 0, 0, 1))
```
   real    1m14.405s
   user    1m13.904s
   sys     0m0.512s
```

•

プログラム：matrixPower (20, 1, 0, 0, 1)

   real    0m0.003s
   user    0m0.000s
   sys     0m0.000s

•

プログラム：matrixPower (30, 1, 0, 0, 1)

   real    0m0.003s
   user    0m0.000s
   sys     0m0.004s

問 2.13

フィボナッチ数の定義から，当然，以下の等式が成立する．

	$\displaystyle F_{n}$	$\displaystyle=$	$\displaystyle F_{n}$
	$\displaystyle F_{n+1}$	$\displaystyle=$	$\displaystyle F_{n-1}+F_{n}$

今， $G_{n}=\left(\begin{array}[]{c}F_{n}\\ F_{n+1}\end{array}\right)$ とおき， $G_{n}$ と $G_{n-1}$ との関係を考えると，上記の等式は，以下のような行列を用いた式で表現できる．

G_{n}=\left(\begin{array}[]{cc}0&1\\ 1&1\end{array}\right)G_{n-1}

$G_{0}=\left(\begin{array}[]{c}0\\ 1\end{array}\right)$ であるから，定義に従い展開すると，以下の式が得られる．

G_{n}=\left(\begin{array}[]{c}F_{n}\\ F_{n+1}\end{array}\right)=\underbrace{\left(\begin{array}[]{cc}0&1\\ 1&1\end{array}\right)\left(\begin{array}[]{cc}0&1\\ 1&1\end{array}\right)\cdots\left(\begin{array}[]{cc}0&1\\ 1&1\end{array}\right)}_{\mbox{$n$回の繰り返し}}\left(\begin{array}[]{c}0\\ 1\end{array}\right)

$A=\left(\begin{array}[]{cc}0&1\\ 1&1\end{array}\right)$ とおくと，行列の積の結合性より，以下の結果を得る．

G_{n}=A^{n}\left(\begin{array}[]{c}0\\ 1\end{array}\right)

したがって， $F_{n}$ は行列 $A^{n}$ の第一行第二列目の成分に一致する．この性質を使い，フィボナッチ数を線形時間で求める関数 fastFib’ を matrixPower を使って定義せよ．

解答例ベクトルとの積を考えると $A_{n}$ の第１行の和が $F_{n}$ であるから以下のようにコード化できる．

   fun fastFib’ n = let
                       val (a,b,c,d) = matrixPower(n,0,1,1,1)
                    in
                      a + b
                    end;

問 2.14

matrixPower は， $n$ に関して線形時間を必要とするが，結合律が成り立つ積に関する巾乗の計算の場合は，それをさらに対数時間に高速化可能である．以下の処理を行う fastMatrixPower を定義せよ．

1.

$n=0$ なら単位行列(1,0,0,1)を返す．
2.
$n>0$ なら $m={n\over 2}$ と $k=(n\ mod\ 2)$ を求め，以下の処理を行う．
1. (a)
  
  fastMatrixPower(m,a,b,c,d) を計算する．
2. (b)
  
  上記の行列同士の積を計算する．
3. (c)
  
  もし $k=1$ なら，さらに，上で求めた行列と引数で与えられた行列の積を求める．

$n$ が $2^{k}$ の場合について，fastMatrixPower が行う行列の掛け算の回数を見積もれ．

matrixPower(1000000,1,0,0,1) と fastMatrixPower(1000000,1,0,0,1) とをそれぞれ計算し，実行速度を比較せよ．

fastMatrixPower を使って，fastFib’ と同一の動作をする関数 veryFastFib を定義せよ．

解答例 fastMatrixPowerは以下のようにコードできる．

   fun matrixMult (a,b,c,d) (x,y,z,w) = (a*x+b*z,a*y+b*w,c*x+d*z,c*y+d*w)
   fun fastMatrixPower (n,a,b,c,d) =
        if n = 0 then (1,0,0,1)
        else let val m = n div 2
                 val k = n mod 2
             in if m = 0 then (a,b,c,d)
                else let val (x,y,z,w) = fastMatrixPower(m,a,b,c,d)
                         val (x,y,z,w) = matrixMult (x,y,z,w) (x,y,z,w)
                      in if k = 0 then (x,y,z,w)
                          else matrixMult (x,y,z,w) (a,b,c,d)
                      end
             end;

fastMatrixPowerが引数 $2^{k}$ に対して行う掛け算の回数を $S_{k}$ と置くと

	$\displaystyle S_{0}$	$\displaystyle=$	$\displaystyle 0$
	$\displaystyle S_{k+1}$	$\displaystyle=$	$\displaystyle S_{k}+8$

である．従って $8k$ 回である．

以下に、プログラムコードと現在の著者の環境で計測した実行時間を示す。

•

プログラム：matrixPower (1000000,1, 0, 0, 1)

   real    0m0.085s
   user    0m0.052s
   sys     0m0.032s

•

プログラム：fastMatrixPower (1000000,1, 0, 0, 1)

   real    0m0.002s
   user    0m0.000s
   sys     0m0.000s

veryFastFibは，fastMatrixPowerを使い以下のように定義できる．

   fun veryFastFib n =
       let
         val (a,b,c,d) = fastMatrixPower(n,1,1,1,0)
       in
         b
       end;