2008-04-01から1ヶ月間の記事一覧

六面体の頂点をたどる(4)

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

第19回ナゴヤ チャリティマラソン フェスティバル

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

六面体の頂点をたどる(3)

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

六面体の頂点をたどる(2)

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

六面体の頂点をたどる(1)

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

GPGPUで多倍長整数計算(2)

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

5000m

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

GPGPUで多倍長整数計算(1)

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

GPGPUで整数計算(12)

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

GPUで「世界のナベアツ」問題

なにも考えずに素直に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のつく数かを判定する。これをプログラムで書く…

GPGPUで整数計算(11)

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

GPGPUで整数計算(10)

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

GPGPUで整数計算(9)

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