2008年2月14日木曜日

knuthのGPS

電通大での講義の時に,GPS(general problem solver)の話をした.Algol 60の名前呼びの機能を最大限活用するものだ.


real procedure gps(i,n,z,v); real i,n,z,v;
  begin for i:=1 step 1 until n do z:=v; gps:=1 end


つまり4つの引数i,n,z,vはvalueと宣言していないからすべて名前呼びである.

これを使うプログラムは

i:=gps(i, if i=0 then -1.0 else i,p,
 if i=1 the 1.0 else
  if gps(a,i,z,if a=1 then 1.0 else
   entier(a)×(entier(i)÷(entier(a))=entier(i)∧a<i then 0.0
    else z)=z then
     (if p<m then=p+1 else i×gps(a,1.0,i,0.0)) else p)

プログラムを実行するとpにm番目の素数が入る

最初の行はiを制御変数にしてfor文をまわす.iは1になっているので終点はiということ,すなわちiはどこまでも増え続ける.forループで実行するのは変数pへの代入で,まずはiが1なので1.0が入る.
次はiが2になって代入文へくる.今回からpへ代入する値はelse以降3行目からになる.
そこでgpsを呼ぶ.今回は制御変数aで1からiまで増える.代入先はzで初回は1.0が入る.その後aは1ずつiまで増える.代入される値は4行目で計算する.ここでentierはAlgol 60の基本関数で小数点以下を切り捨てる. ÷の記号は商の小数点以下を切り捨てる除算. したがってここではiがaで割り切れるかを見ている. 割り切れてしかもaがiより小さければiには約数がある,素数ではない. そうならzにoを入れ,そうでなければzのまま. zには最初1を入れたが途中1つでも約数があると最後は0になっている.
一方このgpsから脱出してきたときの値はgpsの宣言の最後にあるように1である. zがそれに等しいというのはiが素数であったことである. そこで最後の行のelseより前を実行してその値をpに代入する. pがmより小さければp+1だからpはmになるまで素数のたびに1ずつ増える. 素数でなければp, つまり不変.
ということでm番目の素数が見つかったところで中ほどのelseの次に来る. iには今m番目の素数が入っている. gpsの値1を掛けてpに入れる. gpsの仕事はiに0を代入して外側のgpsのループを停止させることである. 問題は最後の乗算でiを先に評価すればよいが, gpsを先に評価すると大切なiの値が変わっていることだ.
まだ他にも微妙な点はあるが,いちおうこのようなプログラムだ.

0 件のコメント: