後日談

一応言っておくと, 例の記事はフォローとして書いた.
オーダー記法の定義を伝えるのが一点. 計算量が正確に定義されていないがそれでもdankogaiの記事に意味を持たせるために関数の呼び出し回数を測っているんだよということを知らせるのが一点. (やっぱりというか予想通りというか, 「計算量の定義は?」とか「オーダー記法の定義は?」とか「べき乗演算がO(1)?」とか各所から正面からのツッコミがあったのはご存知の通り.)

補遺でこちらが間違えていたので, どうしようもない. これは実に申し訳なかった. 恥ずかしい.
ただ, 個人的に重要な指摘と思っているところの問題が解決されていない. （整数の演算にもコストがかかる）計算量なのか関数の呼び出し回数なのか曖昧なままだ.

さて, 冪乗演算はO(1)かという話で記事が上がっているが, アレは話がそれている. 紹介されているアルゴリズムは有限精度のものである. フィボナッチ数列を求めるときにはもっと精度に気を使って冪乗計算をしないといけない. 今後, O(log n)回乗算する話が出てくるようだ. (勿論, 乗算の回数がO(log n)というだけである. 実マシン上でもチューリングマシン上でも計算の度に桁数が増えることによりlog nでは抑えきれなくなるだろう.)

ということでアレは回答ではないのだろう. 後からもっとちゃんとした返信が出てくると予想している. ということで勝手にフォローする記事の二つ目終了.

眠い. 起きたら論文と資料を作る.
あと, 是非Challenge for Geeks - JGeek Logに参加して欲しい.

二整数の桁数が増えるたびに四則演算に掛る時間が増えることは簡単に分かる. ナイーブにintの配列を使って足し算してみよう. 配列の各要素を足し合わせてるわ繰り上がりはあるわで桁数に比例して配列の要素同士の足し算の回数が増える.