ur2cのプロフィール

数学の論文において数値実験が必要だったため， 多倍長演算を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という数が大きすぎるため，演算においてメモリ間とのデータのやり取りで何かのオーバーヘッドが生じているのではないかと予想していますが，確証がもてません．

数学の論文において数値実験が必要だったため， 多倍長演算を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という数が大きすぎるため，演算においてメモリ間とのデータのやり取りで何かのオーバーヘッドが生じているのではないかと予想していますが，確証がもてません．

数学の論文において数値実験が必要だったため， 多倍長演算を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という数が大きすぎるため，演算においてメモリ間とのデータのやり取りで何かのオーバーヘッドが生じているのではないかと予想していますが，確証がもてません．

はじめて質問させていただきます。 来年2014年ブラジルワールドカップを見に一人でブラジルへ行こうと思っています！ なんとかワールドカップのチケット・飛行機は取れ、あとは現地の宿泊宿を探しています。 飛行機代が結構かかってしまったので今回できる限り費用をかけずに泊まりたいのですが、 良い方法はないでしょうか。 現時点ではサンパウロとベロオリゾンテの2都市に2週間程滞在する予定です。 ポルトガル語については現在勉強はしているのですが、かなり片言になると思います。 ブラジルについて詳しい方、現地の方是非、情報・ご指導よろしくお願いいたします。

数学の論文において数値実験が必要だったため， 多倍長演算を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という数が大きすぎるため，演算においてメモリ間とのデータのやり取りで何かのオーバーヘッドが生じているのではないかと予想していますが，確証がもてません．