べき乗の計算は、 1のみの要素からはじめて、要素同士足し算してその結果を加える、 といった操作と同じである。 例えば、15乗を計算するとき、 a -> a2 -> a3 -> a6 -> a12 -> a15 一般的なアルゴリズムのバイナリ法より1回少なくて済む。 これは、 {1} -> …

べき乗の計算は、ふつう次のように行う。 例えば、aの13乗を計算するとき、 13を2進数で表すと1101、 まず2乗して、 a2 = a * a 2進表示の左から2番目が1なのでaをかけて、 a3 = a2 * a 2乗して、 a6 = a3 * a3 2進表示の左から3番目が0なのでそのまま。 2乗…

ひざが不安だが、短い距離ならだいじょうぶだろう、 という根拠のない考えから、 1km×2を。 300mほどジョギングしてから、 1kmを流しっぽく。 3分32秒。 少し余裕をもってこのタイムなら、 いますぐにでも1500のベストが出せるかも。 300mほどゆっくり走って…

素数分布（2） 前にも書いたように、GPUは分岐に弱い。 ある程度まとまったスレッド（16 or 32）が同じ命令を実行するため、 分岐すると、違う命令を実行するスレッドは、 今実行している命令が終わるのを待っていなければならない。 だから、分岐しないよう…

グラフを見れば分かるが、ここ1週間ロクに走れていない。 左ひざが痛いから。 仕方がないから、実家の近くの小さな山に登った。 いつもは、 ふもとまで約3kmをジョギングして、 200mほど登って、すぐに下りてきて、 またジョギングをして帰ってくるのだが、 …

演算の速度 こういうデータを用意して、 const int nWidth = 256; const int nHeight = 256; const int nData = nWidth * nHeight * 4; float *data = new float[nData]; int nRep = 16384; for(int i = 0; i data[i] = (float)((i & 1) + 1); }こういう演算…

素数分布（1） 手始めに、ガウスの故事にならって、素数分布を求めよう。 1000ずつ区切って、そのうちの素数の数を数える。 1001〜1000万を1000ずつ区切ることにする。 const int nWidth = 128; const int nHeight = 128; const int nData = nWidth * nHeigh…

整数の演算 intの演算はどうなのだろうか。 uniform samplerRECT texUnit0;void main(void) { vec4 color = texRECT(texUnit0, gl_FragCoord.xy); ivec4 icolor = ivec4(color); icolor /= 3; gl_FragColor = vec4(icolor); }これを実行すると、 0.000000 0.…

全面的に書き直し。 整数の精度 整数のデータを入力したかったが、よくわからなかった。 検索しても出てこないし。 仕方がないので、floatの配列をGPUに送って、キャストすることにした。 const int nWidth = 4; const int nHeight = 2; const int nData = n…

浮動小数点数計算（2） ピクセルごとに少ない計算量だとあまり速くならないが、 ピクセルごとにループを回すと速くなる。 前回の問題を、 を計算するように変える。 コードはほとんど変わらない。 シェーダープログラムのほうを次のようにする。 //shader_nv…

浮動小数点数計算（1） まず、 http://aaa.jspeed.jp/~ohshima/cgi-bin/fswiki/wiki.cgi?page=OpenGL%2BGLSL(Windows)%A4%C7GPGPU_HelloWorld で必要な準備をする。 そして、一番下のコードをコピペし、次のようにコンパイルする。 > cl /O2 /GX gpgpu1.cpp…

GPGPUというのは、General Purpose GPUの略で、 本来CGに使うGPUを汎用的に使おうという話。 GPUは使いにくい面はあるが、CPUより圧倒的に速い。 革命的に速くなる。 しかし、整数計算ではまだあまり使われていないのではないだろうか。 （私も仕事では浮動…

今年の東大の問題でこんなのがあったそうだ。http://blog.livedoor.jp/seven_triton/archives/51364482.html 区間 0＜x＜1 からランダムに数を一つ選ぶという試行を繰り返し，ｎ回目に選んだ数を a[n] とする。 このとき，a[1] + a[2] + … + a[n] が初めて１…

やや古い記事だが、 ここに、数学オリンピックの問題が載っていた。 http://d.hatena.ne.jp/hiroyukikojima/20080211 「ある世界的組織は6カ国のメンバーから構成される。組織のメンバーリストには1978人が登録し、各人が1,2,･･･,1978番と番号付けられている…

しばらくサボっていたが、今日ようやく少し走った。 きのうまで足の裏が痛かった。 たぶんもうだいじょうぶ。 2週間くらい前から、右足の左側が若干痛かった。 それでややそこをかばい気味に走ったら、 今度は右側が痛くなった。 どこかをかばったらどこかが…

今まで考えていた問題は、 「コラッツ予想」とか「コラッツの問題」というらしい。 http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84%E3%81%AE%E5%95%8F%E9%A1%8C しかし、このWikipediaの「ヒューリスティクス」な議論はひどい。 なぜな…

速報が出ていた。 完走率が意外と低くて驚いた。 確かに制限時間はきびしめだが。 http://www.city.sasayama.hyogo.jp/abc/ そこに掲示板があり、やはりスタート時のことが大きな話題となっていた。 ロープの中に入るときにチェックをすればいいだけなのに。…

未だに筋肉痛だが、ふつうに走る分にはなんでもない。 どうやら走り方がいつも全然違ったらしい。 スタートラインをまたぐが、前が詰まっていてゆっくりしか走れず。 すぐに道が狭くなり、さらに詰まる。 だからタイム順のスタートなのに。 立ちションの人は…

http://www.asahi.com/kansai/news/OSK200803020032.html ながらに乗って、こだまで新大阪、 福知山線のどこかで乗り換えると、乗客がいかにもという人ばかり。 50代が多いように見えた。 終点の篠山口で降りると、シャトルバス待ちの列がずらり。 バスは西…

悪夢を見た。 0:16:51 3km 0:22:04 4km 0:27:14 5km 0:52:46 10km 1:18:56 15km 1:45:38 20km 1:56:16 22km 2:01:48 23km 2:07:02 24km 2:12:17 25km 2:18:00 26km 2:23:30 27km 2:29:17 28km 2:35:12 29km 2:41:22 30km 2:47:24 31km 2:53:37 32km 2:59:52 …