多倍長演算における実行時間と計算量の差

質問

• 多倍長演算において、計算量と実行時間の差が生じる原因とは？
• 多倍長演算において、計算量と実行時間の関係を調査しました。
• なぜ多倍長演算において、数を大きくすると実行時間が遅くなるのか？

回答No.8

ur2c

> 質問2： 図のグラフは理論的に計算したグラフではなくて実験値でしょうか？

そうです。ご質問にあった画像の数値です。ただし、説明をまちがえました。

> 横軸が n、縦軸が [(2) の実行時間] / [(1) の実行時間] です。

と書きましたけど、横軸は n でなく h := lg n です。そこで

> 質問1： 実行時間が (1) 2n (2) 3n　に比例する

も同様に「(1) は 2h, (2) は 3h に比例」になります。それでも

> ということは，比は
> [(2) の実行時間] / [(1) の実行時間]　= (3n)k / (2n)k = 3/2　
> と一定

が

[(2) の実行時間] / [(1) の実行時間] = 3h/(2h) = 3/2

となるだけです。つまり結論はおっしゃるとおり、実行時間の比が一定になるはずです。ご指摘ありがとうございます。

ところで実測値を見ると、

[(2) の実行時間] / [(1) の実行時間] = O(h)

になってるように見えます。だから O(h^2) の O() に隠れた部分が効いてるのでしょう。その隠れた部分は入出力だと思います。なぜなら、入出力は内部記憶を用いた計算より桁違いに時間がかかるからです。つまり (2) では (1) にはない入出力が h に比例して、余計にかかっているということのような気がします。

(1) では長さ h の strings を 2 つ入出力しながら掛算します。時間は 2h + O(h^2) に比例。(2) では長さ 2h と h の strings を入出力しながら、割算します。時間は 3h + O(h^2) に比例。h が小さいときは O(h^2) 部分は内部記憶で処理されるので、入出力に比べれば無視できる、と仮定します。すると [(2) の実行時間] / [(1) の実行時間] は O(h) になります。h は最大でも 2 [MBytes] くらいなので、これはすくなくとも図と矛盾しません。

上は憶測にすぎませんので結局、prifile を見るのが確実と思います。

お礼

たびたびご回答ありがとうございます．

#9さん の回答で解決致しました．
ハードウェア上では乗算は除算よりも高速で，
カラツバ法を用いるとO(h^1.585)，除算はそのままO(h^2)として，実験データと比較しましたらほぼ一致いたしました．
(2)/(1)が増加する原因ですが，(h^2)/(h^1.585) = h^0.415 となるためだと思います．

たしかに，入出力量が3/2倍違うので，それも実験データに効いてきていると思います．
貴重な議論をありがとうございました．