ひざもだいぶよくなって、日常生活にはほとんど問題なくなった。 受付をすませてから、安全ピンでナンバーカードをシャツにつける。これ苦手。しかも今回は2枚ある。なぜ2枚あったのか、よくわからなかった。間違えて後ろにつけると誘導できないからだろうか…

早くも結果が上がっていた。 http://www.city.kariya.lg.jp/hp/page000002100/hpg000002038.htm この大会はほとんど宣伝されていない。うちには届かない市報と、あといちおうネット上で紹介されるが、RUNNETによる受付はない。申込むには、直接ウィングアリ…

とにかく、状態が悪かった。昨日の夜突然腹が痛くなった。今朝はあまり食事が取れなかった。水もほとんど飲めなかった。ひざも不安なのでほとんど走れていない。 それでもベストタイムだけは狙っていたが、距離が非常にあやしかった。最初の1kmが3分49秒、次…

開平（1） 開平の方法はたぶん中学で習ったと思うが、割り算と似たようなやり方がある。あれをコード化するとこんな感じだろうか。 #include using namespace std;void sqrt(int a, int& b, int& c); int get_bit_num(int a);int main() { for(int i = 0; i …

10進変換（4） 前回、ある程度小さい数を10進数にして、それを自乗していくという方法を考えた。今回は、その自乗をGPUで行う。 多倍長整数の乗算は、多項式の乗算と同じようなものだから、1ピクセル（一つの項）ごとに大量の乗算・加算をする。だからGPUで…

固有値が求まらなかったので、数値的に求める。 ニュートン法でやってみた。 Array.prototype.value = function(x) { var v = this[this.length-1]; for(var i = this.length - 2; i >= 0; i--) v = v * x + this[i]; return v; }Array.prototype.differenti…

六面体で同じように行列を作る。 ここで、行列の各成分を3倍すれば整数化できるので、その行列の固有値を考える。 この固有方程式は、 |A - λE| = 15120λ3+10080λ4-137484λ5-8916λ6+477972λ7 -192860λ8-753221λ9+591113λ10+497726λ11-643343λ12 -78020λ13+33…

10進変換（3） 前回、16ビットずつ掛け算していったが、2100000 = (250000)2だから、250000を計算してそれを自乗したほうが速いような気がする。さらに、250000も同様に。 実際に組んでみたら、倍くらいの時間がかかるようになった。 ただし、この掛け算はGP…

前に出てきた漸化式を解く問題は、単なる固有値問題である。 例えば、元の四面体の問題は、 だから、 の固有値を求めればよい。 を解いて、 それぞれに横ベクトルをかけて0ベクトルになる固有ベクトルは、 ( 1 0 0 ), ( 2 1 0 ), ( 1 1 1 ) だから、 につい…

前回求めた漸化式に順番に値を代入して確率を具体的に求めた。それを以前と同じようにはじめて全頂点をたどった確率に直してグラフにした。回数が大きくなると、偶数回とその次の奇数回が同じ確率になる。また、2つ前の7/9の確率になるようである。 プログラ…

庄内緑地公園にて。 参加者は1000人ほど。一般男子10kmは458人エントリーと小規模。 10kmは2.3kmの公園内コースを4周するらしい。 受付すると完走証が。タイムを自分で記入というのは今までもあったが。タイムは自分で計ればよいが、これだと順位がわからな…

同値な状態を一意に表すために次のようにしよう。現在の点は0に持ってくるように写像を施す。そのうえで、0を固定した回転・対称変換を施して、状態を表す整数が最も小さくなるものを正規の表現とする。状態を表す整数とは各頂点がすでにたどっていればその…

この問題は、 という漸化式を解けばよい。 ここで、siは状態を表しており、psi,tは時刻tに状態siを取る確率、qsi→sjは状態siからsjに遷移する確率である。 状態とは、すでにたどった点の集合と今の点の位置の組合せである。状態は数多く存在し、その分漸化式…

今年の京大2問目、 正四面体ABCDを考える。点Pは時刻0では頂点Aに位置し、1秒ごとにある頂点から他の3頂点のいずれかに、等しい確率で動くとする。このとき、時刻0から時刻nまでの間に、4頂点A、B、C、Dのすべてに点Pが現れる確率を求めよ。ただしnは1以上の…

10進変換（2） 前回は1ビットずつ計算していたが、さすがにそれでは遅いので16ビットずつに区切って10進計算を行ったところ、0.1秒くらいになった。 しかし、これでもGPUは使えない。

最近すっかり走っていなかったが、来週レースがあるので、土曜5km、日曜6kmを走って、今日はトラックを久しぶりに走ってみた。グラウンド整備の人のみで、貸切状態。 1000mを4分30秒で刻んでみたが、やっぱりトラックを一人で走るのは精神的に無理。今日は特…

タイトルを変えた。 10進変換（1） 計算は2進数で行い、表示するときに10進数に直す。 2100000を10進数にするのに、1を10万回2倍すると非常に簡単に実装できる。適当な桁で区切って（下のコードは4桁）、ビットにしたがって、2倍とインクリメントを繰り返す…

前に効率的なべき乗の計算というのをやったが、これは多項式の計算がしたかったからである。 例えば、 という計算をやらせる。 代数的に簡単に計算できるが、それはおいといて、次のようになる。今回はテクスチャを2枚用意するので、久しぶりにフルソースを…

なにも考えずに素直にGLSLでGPUに解かせてみた。 こういうデータを用意する。 const int nMax = 100000; const int nWidth = 512; const int nHeight = 256; const int nData = nWidth * nHeight * 4; float *data = new float[nData]; for(int i = 0; i dat…

お笑いには非常にうとくて、「世界のナベアツ」という言葉は最近よく目にするなあとは思っていたが、この間はじめてテレビで見たばかりだ。しかし、それは本人ではなかったらしい。 3の倍数、5の倍数、または3のつく数かを判定する。これをプログラムで書く…

以下の話は、NVIDIAのG8シリーズ固有の話である。ただ、推定実行時間でソートしてGPUに投げるというのは恐らくどのGPUでも通用するテクニックだと思われる。 スレッド群 次のようにテクスチャを用意し、 int bit = atoi(argv[1]); int mask = 1 const int nW…

for文 例えば、128*128のデータを用意して、それになんらかの値が入っている。シェーダプログラムのほうは、0ならそのまま抜けて、それ以外なら重い計算（1000万回の繰り返し計算）をするようになっている。 uniform sampler2DRect texUnit0; // datauniform…

配列 配列は次のように宣言して使う。 int a[10];関数に引き渡すには次のようにする。 void f(in int a[10]);f(a);型にinがつくと、入力、 outがつくと、出力、 inoutがつくと、入出力になる。 次の例は、 an = a0 + ... + an-1 s = a0 + ... + an を、a0を…

べき乗の計算は、 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…