読者です 読者をやめる 読者になる 読者になる

nekoTheShadow’s diary

技術ブログとして始めたはずが、読書&愚痴ブログになりました(´・ω・`)

「ソモスの数列」(でいいのかな?)という数列があるそうです。

scheme

 いつもどおり(?)インターネットを漂流していると、somos sequence(以下「ソモスの数列」)なるものを見つけました。より詳しいことはここを参照してほしいのですが、わたしなりに簡単に要約してみると――4以上の整数kについて次のような漸化式/数列を考えます。

  • A1 = A2 = ... = Ak = 1
  • An * A(n - k) = (1..(k / 2).floor).sum{|j| A(n-j) * A(n-(k-j))} [n > k]

一見整数列には思えない数列ですが、実のところk=4,5,6,7において無限に整数が続くことが証明されているそうです。わたしはこれを証明することには興味がないというか、証明するだけの数学力を持ち合わせていませんので、今回は「ソモスの数列」を無限リストにして遊んでみたいと思います。

 さてやろうと決めて、思いついたのは以下の3選手。それぞれmake-somos-sequence1/2/3として実装しています。

 できました。ここには記しませんが、一応テストらしきこともやって3つとも正しく動作することは確かめています。よって次は性能の計測に移りたいと思います――と問題発生。端的にいうと単純な再帰のmake-somos-sequence1がまったく使いものになりませんでした……。わたしの環境では第30項ごときで結果が返ってきません。しょうがないのでmake-somos-sequence2と3のどちらが優秀かを競うこととします。

(time (stream->list (stream-take (make-somos-sequence2 7) 300)))
(time (stream->list (stream-take (make-somos-sequence3 7) 300)))

;(time (stream->list (stream-take (make-somos-sequence2 7) 300)))
; real   0.219
; user   0.219
; sys    0.000
;(time (stream->list (stream-take (make-somos-sequence3 7) 300)))
; real  10.232
; user  10.672
; sys    0.156

 結果はmake-somos-sequence2の圧勝でした。3はみずからを再帰的に呼び出しているのにくわえ、何本(?)もstreamを生成、高階関数に引き渡しているので、このあたりがボトルネックになったのではないかと想像します。やはり効率のいいschemeプログラミングをするにあたっては、できるだけ単純な再帰を避け、末尾再帰の可能性を探るということ大事になりそうで