昔、共立出版から bit という月刊のコンピュータ雑誌が発売されていた。 その雑誌の連載に、問題を提示して読者から解答を求めるナノピコ教室という欄があった。 この連載の抜粋が「ナノピコ教室」という本にまとめられた。 以下はその一つである。
自然数の逆数の和
`sum_(k=1)^oo 1/k ` は発散する。言い換えれば、任意の正整数 `N` に対して、 `sum_(k=1)^M 1/k ge N` となるような正整数 `M` が存在する。 そこで関数 `f(N)` を、
`f(N) = min_M (sum_(k=1)^M 1/k ge N)`
のように定義する。たとえば、`f(1) = 1, f(2) = 4, f(3) = 11, cdots` である。
12までの正整数 `N` に対して,`f(N)` を求めよ。できれば,さらに大きな整数 `N` に対しても,`f(N)` を求めよ。
(後略)
さて、ここでどのようにして正確な計算を行うかが問題である。誤差評価と密接に絡んでくる。
普通ならこんなプログラムをかけばよい。
use strict; use warnings; for (my $sum = 1, my $i = 2; $i <= 13562027; $i = $i + 1) { $sum += 1.0 / $i; print $i, "\t", $sum, "\n"; }
この13562027 という数字は異様に大きいが、これがナノピコ教室による `f(17)` の値なのである。 ちなみに、上記の計算はどれだけかかっているかというと、およそ 30 分である。 print をループ 1 回やっていてこの時間なので、 print を止めれば速くなるだろう。
問題は時間というより誤差であろう。同書では
`sum_(k=1)^248396 = 12.9999972030`
`sum_(k=1)^248397 = 13.00000122881`
を得ている。一方、単純な上記の和のプログラムでは、
`sum_(k=1)^248396 = 12.9999972036674`
`sum_(k=1)^248397 = 13.0000012294809`
であり、誤差がある。場合によってはこのわずかな誤差によって、
単純に計算機で累積した和による `f(N)` では誤る可能性がある。
つまり、`f(13)=248397` という結果は一致しているが、
出題者のいうその計算方法で正しい答が得られる根拠(証明,あるいは説明)を明示すること.
には答えているとは言い難い。私はここで挫折した。その後挫折を乗り越えようとした苦闘は、
「ナノピコ教室」の書評を見てほしい。
数式表示には MathJax を用いている。
まりんきょ学問所 > コンピュータの部屋 > Perl 手習い > 数列の和の計算