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

質問

数学の論文において数値実験が必要だったため，
多倍長演算をC++で実行したところ，計算量とのギャップが生じました．
その原因をコンピュータに詳しい方にアドバイスを頂きたいと思って質問させていただきました．

具体的には，n,m を同ビット　として　以下の二つの演算を考えます．

演算(1) n * m
演算(2) n^2 % m (n^2は先に計算しておき，% (mod)の演算のみ)

--------------------------------------------------
■計算量評価
大雑把に(1)と(2)の計算量を比較すると

(1) lg n * lg m = (lg n)^2

(2) (2*lg n - lg m) * lg m = (lg n)^2

となるので，(1) と (2)はほぼ同じ計算量となります．
--------------------------------------------------

しかしながら，実際に計算をしてみると，
n,m が 1000bit　ほどまでは，ほぼ同じ計算時間なのですが，
2000bit, 4000bit ,..., と数を大きくしていくと，大きくしただけ (2) の速度が遅くなります．

具体的な実験結果は画像で添付いたします．
画像 (http://puu.sh/6iBQf.png)

(1) と (2)の実行時間のギャップは何処から生じたものなのか，何かわかるかたがいらっしゃいましたら教えていただけたら嬉しいです．

よろしくお願い致します．

予想：
　コンピュータの知識があまりないですが，自分なりの予想では，(2)のn^2という数が大きすぎるため，演算においてメモリ間とのデータのやり取りで何かのオーバーヘッドが生じているのではないかと予想していますが，確証がもてません．

回答No.9

SortaNerd · ベストアンサー

No3です。
演算プログラムを見て計算量評価をしたのかと思ったら違うのですね。
やはり単純に計算量評価が間違っているだけでした。

なんというか、ここまで見事だとあなたのためにならない気がしてくるんですが…

お示しのデータをプロットしたものが添付画像です。
青が乗算、赤が剰余算です。
剰余算が遅いというような言い方でしたが、これを見ると剰余算は綺麗に(lg n)^2となっています。
剰余算が遅いのではなく、乗算が速いのです。
これ、プロットすれば一発で分かることなんですよね。

で、参考までに、あなたも名前を挙げたカラツバ法の計算量はO(n^1.585)らしいですね。(こちらのnは桁数)
http://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%A9%E3%83%84%E3%83%90%E6%B3%95

お礼

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

小さな係数をかけて調整して，理論値と比べたのですね．
これを参考にして，自分の実験結果を同じように比較しましたら，
乗算はカラツバ法(ビット長の1.585乗)，除算はそのまま(ビット長の2乗)
とすると，計算量と実験データがほぼ一致いたしました．

上昇の比率も (lg n)^2 / (lg n)^1.585 = (lg n)^0.415 として，
係数を調整して実験データと比較したらほぼ一致いたしました．(http://puu.sh/6kKc9.png)

論文のほうも無事にまとめられそうです．
ありがとうございました．

回答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倍違うので，それも実験データに効いてきていると思います．
貴重な議論をありがとうございました．

回答No.7

Tacosan

「うまいところ理論値と実際の実行時間とのギャップを "いいわけ" したい」とか言ってるけど, 「どう計算しているのか」も分からず「理論値」なんて考えても時間の無駄.

お礼

専門は純粋数学なので，計算機については周りの教授も全く知識がありません．
口頭試問でギャップについての単純な質問が来たときに，どのように納得させるか考えています．
・除算は乗算に比べてハードウェア上では計算が遅いこと
・入出力量の差からオーバーヘッドに違いがあること
などで，恐らく十分すぎるほど準備はできてます．

とりあえず，口頭試問では色々なことを試して研究したということが大事なので，無駄なことは一つも無いと思います．

回答No.6

ur2c

> (1)は2n (2)は3nに比例するので，差がどんどん広がってくるということですね．

ちょっと気になることが２つ。

1. 差ではなく比です。

図を示します。横軸が n、縦軸が [(2) の実行時間] / [(1) の実行時間] です。これが n が大きいとき線形です。

2. 線形は普通「どんどん」より「のろのろ」です。「どんどん」と言うと、大概の人は指数関数的と思っちゃいます。

お礼

回答ありがとうございます．
すみません，やはり何か勘違いしていたようです．
いろいろと考えてみたのですが，以下の質問をさせていただきます．

質問1： 実行時間が (1) 2n (2) 3n　に比例するということは，比は

[(2) の実行時間] / [(1) の実行時間]　= (3n)k / (2n)k = 3/2　と一定になってしまう気がします．　

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

よろしくお願いします．

回答No.5

ur2c

> 入出力量については
> (1)入力 n+n = 2n，出力 n^2なので 2n
> (2)入力 2n + n= 3n ，出力 1n
> で総合的には4nとなって同じになりそうな気がします．

「入出力」の意味に誤解があるようです。大きな計算は

入力 -> 演算-> 出力

という風に進むのではありません。「入出力」は内部記憶装置と外部記憶装置とのやりとりを指しており、上記「演算」の中で複数回、行われるはずです。それをするのは多分、application program ではなく OS でしょう。

上の意味での入出力が１回行われるとき、(1) は n 桁を 2 つ書くとか読むとかします。ですから 2n に比例です。それに対して (2) は 2n 桁が 1 つと n 桁が 1 つです。ですから 3n に比例です。

plot で n が小さいときに立ち上がりが急なのは、n に比例せずに入出力の準備や後始末に関する固定部分が効いているのだろうという解釈です。

お礼

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

>入出力量
なるほど，なんとなく理解ができました．
(1)は2n (2)は3nに比例するので，差がどんどん広がってくるということですね．

回答No.4

ur2c

＃１ です。

> profiler

入出力は program でなく OS が paging でやっている可能性があります。その場合 profiler によっては、はっきりしない可能性もあります。多分、だいじょぶですけど。

回答No.3

SortaNerd

単純に計算量評価が間違っているのだと思いますが…。

> (1) lg n * lg m = (lg n)^2
> (2) (2*lg n - lg m) * lg m = (lg n)^2
この式(とくに2)の導出過程を書いてください。

補足

回答ありがとうございます．
正確に表記しますと，
nとmは同ビットなので そのビット長は等しい(n≧mとします)
[lg n]+1 = [lg m]+1 ([]は小数点以下切捨て記号)

(1)乗算 n * m のビット演算量は高々
([lg n]+1)*[lg m] …[*]
なので
+1の部分はざっくり0として，
[lg n]*[lg m] = [lg n]^2

(2)剰余算 n^2 mod m のビット演算量は高々
([lg n^2] - [lg m] + 1)*([lg m] + 1)　　…[*]
なので
+1の部分は省略して
([2lg n] - [lg m])*[lg m]　…(A)
[2lg n] = 2[lg n] or 2[lg n]+1 なので， [2lg n] = 2[lg n]とすると，
(A) = [lg n]*[lg m] = [lg n]^2

となります．　+1 を省略しても定数かつ小さいので計算量評価には問題ありません．

[*]開かれた数学 数論アルゴリズム 中村　憲著 (p12)より

回答No.2

kmee

肝心の計算部分が無いので、なんとも言えませんが。

一般に、Orderが同等でも、実際の演算実行には、Oでは消えている定数部分や項が効いてきます。
また、並列処理を始め、さまざまな工夫が使われます。

お礼

ご回答ありがとうございます．
＞さまざまな工夫
そうですね，乗算にもFFTが使われていたりすると，O(n^2)がO(n log n loglog n)になったり，カラツバ法や，除算にはモンゴメリ乗算やニュートン除算などを使われていると計算量が変化してしまいます．うまいところ理論値と実際の実行時間とのギャップを "いいわけ" したいのですが，なかなか良い感じのデータや根拠が取れなくて悩んでいます．

回答No.1

ur2c

> (2)のn^2という数が大きすぎるため，演算においてメモリ間とのデータのやり取りで何かのオーバーヘッドが生じているのではないか

n = m で、かつ中間結果を読み書きしていると仮定します。n が大きいときの入出力量は (1) は 2n, (2) は 3n に比例するはずです。したがって (2) 対 (1) の計算時間比は n が大きいとき n に比例するはずです。plot してみると data の後半は実際、桁数にほぼ比例して時間比が大きくなっています。

> 確証がもてません．

profiler という tool があって、実行時間（や記憶消費）のうちわけなどを教えてくれます。それを使えば確実な情報が得られるかと思います。

お礼

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

入出力量についてはあまり詳しくないですが，
(1)入力 n+n = 2n，出力 n^2なので 2n
(2)入力 2n + n= 3n ，出力 1n
で総合的には4nとなって同じになりそうな気がします．

profilerは今実行しようとしてますが，環境の準備に時間がかかってしまい，論文に間に合わなりそうなので今のところ保留にしています，すみません；