1. sym_num

    Posted

    sym_num
Changes in title
+連想計算
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,197 @@
+#はじめに
+O-Prologのテストも兼ねて黒川利明先生の「Prologのソフトウェア作法」から例題をお借りしました。
+
+#連想計算とは
+連想計算(associative computation)は後藤英一先生の命名によるそうです。数値計算の分野では古くから用いられていたようです。現在ではメモ化(memoization)と呼ばれることの方が通常のようです。
+
+#フィボナッチ数を例にして
+有名なフィボナッチ数を例にします。フィボナッチ数は次の漸化式で表されます。
+
+```
+
+ F(n) = F(n - 1) + F(n - 2) (n=2,...)
+```
+これを素朴に漸化式の通りにPrologで書くと次のようになります。
+
+```
+fib(0,0).
+fib(1,1).
+fib(N,A) :-
+ N1 is N-1, N2 is N-2,
+ fib(N1,A1),fib(N2,A2),
+ A is A1+A2.
+
+test(N) :- fib(N,X),write(X),nl.
+
+```
+
+現在のコンピューターは高速です。O-Prologのインタプリタでもfib(20)程度なら瞬時に求まります。
+
+```
+| ?- time(test(20)).
+6765
+Elapsed Time=0.020372 (second)
+yes
+|
+
+| ?- time(test(12)).
+144
+Elapsed Time=0.000495 (second)
+yes
+```
+しかしながら、12の場合の計算に比べ20の計算にはおよそ41倍の時間がかかっています。これは漸化式による素朴な定義をそのまま計算しているからです。重複した計算を多数行っているのが原因です。
+
+図 黒川先生の本より引用 p93
+![ArcSoft_画像200.PNG](https://qiita-image-store.s3.amazonaws.com/0/33927/88163512-9d70-0c55-83c6-c18c60ee11d7.png)
+
+
+30のフィボナッチ数を求めようとするとさすがの現在のリッチなコンピューターでもお手上げです。スタックオーバーフローを起こします。
+
+```
+| ?- time(test(30)).
+Resource error fib(1,1)
+|
+
+```
+
+因みにISO-Prolog規格ではこのようにスタックオーバーフローが起きる場合であっても、クラッシュうにエラーを出力して停止することが求められています。
+
+#連想計算の工夫
+そこで、連想計算の登場です。無駄な重複計算をさせないためには一度計算した値を保存しておけばよいというのが連想計算の発想です。Prologではassertを使えば事実を表す述語として計算結果を保存しておくことができます。
+
+```
+fib(0,0).
+fib(1,1).
+fib(N,A) :-
+ N1 is N-1, N2 is N-2,
+ fib(N1,A1),fib(N2,A2),
+ A is A1+A2,
+ asserta(fib(N,A)).
+
+```
+
+最後にassertaが追加されただけです。assertaというのは事実を最初の方に登録します。assertzというものもありこれは事実を最後の方に登録します。小さなフィボナッチ数から順番に計算が終わりますから、大きな数は事実の最初の方に登録されていた方が探し出すときに幾分かは有利です。Prologは事実を最初から順番に探していくからです。
+
+
+さて、実行時間を計測してみましょう。
+
+```
+| ?- time(test(20)).
+6765
+Elapsed Time=0.000000 (second)
+yes
+| ?- time(test(30)).
+832040
+Elapsed Time=0.000000 (second)
+yes
+
+```
+
+
+瞬時に計算が終わっています。どのように計算結果が登録されているのでしょう? listingを使うと表示することができます。
+
+```
+fib(30,832040).
+fib(29,514229).
+fib(28,317811).
+fib(27,196418).
+fib(26,121393).
+fib(25,75025).
+fib(24,46368).
+fib(23,28657).
+fib(22,17711).
+fib(21,10946).
+fib(20,6765).
+fib(19,4181).
+fib(18,2584).
+fib(17,1597).
+fib(16,987).
+fib(15,610).
+fib(14,377).
+fib(13,233).
+fib(12,144).
+fib(11,89).
+fib(10,55).
+fib(9,34).
+fib(8,21).
+fib(7,13).
+fib(6,8).
+fib(5,5).
+fib(4,3).
+fib(3,2).
+fib(2,1).
+fib(0,0).
+fib(1,1).
+
+```
+
+これならスタッコーバーフローになる心配もありませんし、計算は瞬時です。
+
+
+#応用
+
+黒川先生の本では、この方法により階乗、最大公約数を計算してみなさい、という課題が示されています。せっかくならもっと大物に挑戦してみましょう。アッカーマン関数ならどうでしょうか? アッカーマン関数は次の漸化式で表されます。とても大きな数になります。
+
+```
+ack(0,N,A) :- A is N+1.
+ack(M,0,A) :- M1 is M-1,ack(M1,1,A).
+ack(M,N,A) :-
+ M1 is M-1,N1 is N-1,
+ ack(M,N1,A1), ack(M1,A1,A).
+
+```
+
+計算をさせてみるとack(3,5)くらいが限界でした。
+
+```
+| ?- ack(3,5,X).
+X = 253
+yes
+| ?- ack(3,6,X).
+Resource error ack(1,113,v_325585)
+|
+
+```
+
+では、連想計算にしたらどうなるのでしょう?
+
+```
+ack(0,N,A) :-
+ A is N+1,asserta(ack(0,N,A)).
+ack(M,0,A) :-
+ M1 is M-1,ack(M1,1,A),
+ asserta(ack(M1,1,A)),
+ asserta(ack(M,0,A)).
+ack(M,N,A) :-
+ M1 is M-1,N1 is N-1,
+ ack(M,N1,A1), ack(M1,A1,A),
+ asserta(ack(M,N1,A1)),
+ asserta(ack(M1,A1,A)).
+
+O-Prolog Ver 1.45(yoko)
+| yes
+| ?- ack(3,8,X).
+X = 2045
+yes
+| ?- ack(3,9,X).
+X = 4093
+yes
+
+```
+
+
+ack(3,9)くらいまでならなんとか計算できることがわかりました。listing(ack)とやってみると実に多くの計算をして記憶しているのかがわかります。
+
+
+#参考文献
+
+Prologのソフトウェア作法 黒川利明 著 岩波書店
+
+Wikipedia アッカーマン関数
+https://ja.wikipedia.org/wiki/アッカーマン関数
+
+
+
+
+
+