[SML 7879] Re: 連想計算というリフレクティブな手法

[Masato Sumi]

成田さん。解説ありがとうございます。sumim です。

とりあえず大枠の部分だけですが、だいたい分かりました。
たとえば、Squeak で組み込みのなんちゃって Matrix において


Matrix >> raisedTo: n
  | m |
  n = 1 ifTrue: [^self].
  n even ifTrue: [^(m := self raisedTo: n/2) +* m].
  ^(self raisedTo: n - 1) +* self


を定義しておけば、


| fibonacci |
fibonacci := [:n |
  | T |
  T := Matrix rows: 2 columns: 2 contents: #(1 1 1 0).
  ((3 to: n) inject: T into: [:Tn :idx | Tn +* T]) +* #(1 0) at: 1].

[fibonacci value: 10000] timeToRun   "=> 758 ms "


というところを


| fibonacci |
fibonacci := [:n |
  | T |
  T := Matrix rows: 2 columns: 2 contents: #(1 1 1 0).
  (T raisedTo: n - 1) +* #(1 0) at: 1].

[fibonacci value: 10000] timeToRun   "=> 7 ms "


のように高速化できるということですね。


2010年12月15日17:04 Narita Takaoki <Narita.Takaoki ＠ exc.epson.co.jp>:
> 大枠は、特定の条件を満たした繰り返し作用に対する「逐次平方」の適用で
> す。フィボナッチ数列への適用は、フィボナッチと逐次平方でググると出てくる
> かな？