連想計算

はじめに

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

しかしながら、１２の場合の計算に比べ２０の計算にはおよそ41倍の時間がかかっています。これは漸化式による素朴な定義をそのまま計算しているからです。重複した計算を多数行っているのが原因です。

図　黒川先生の本より引用　p93

３０のフィボナッチ数を求めようとするとさすがの現在のリッチなコンピューターでもお手上げです。スタックオーバーフローを起こします。

| ?- 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).

これならスタックオーバーフローになる心配もありませんし、計算は瞬時です。

応用

黒川先生の本では、この方法により階乗、最大公約数を計算してみなさい、という課題が示されています。せっかくならもっと大物に挑戦してみましょう。アッカーマン関数ならどうでしょうか？　アッカーマン関数は次の漸化式で表されます。とても大きな数になります。

A(0,n)=n+1             
A(m,0)=A(m−1,1) 
A(m,n)=A(m−1,A(m,n−1))

Prologのコードにすると下記のようになります。

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)とやってみると実に多くの計算をして記憶しているのかがわかります。

他の処理系

GNU-Prologで試すときには動的宣言をしてください。ISO-Prologに厳格に従っており、エラーとなります。　

:- dynamic(ack/3).
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)).

SWI-Prologでは動的宣言はなくても動作しました。ack(4,1)でも計算してしまいます。流石です。

?- ack(4,1,X).
X = 65533 .

?- 

参考文献

Prologのソフトウェア作法　黒川利明　著　岩波書店

Wikipedia　アッカーマン関数
https://ja.wikipedia.org/wiki/アッカーマン関数