No Such Blog or Diary

«Prev || 1 | 2 | 3 |...| 1068 | 1069 | 1070 |...| 1074 | 1075 | 1076 || Next»

グリチャレ初級クリア

グリチャレの初級課題をクリアした.約1000プロセッサを利用できる Grid において,自分のプログラムはわずか 9 個のプロセッサしか使用していない... あほすぎる仕様ではあるが,とりあえず本戦に出るためにもさっさと結果を提出を済ませた.

お次は上級用に通信をしっかりやるプログラムを書かねばならんのだけどMPIを非同期通信に使いつつ TCP/IP 通信も非同期にやるとなると結構面倒なような… とにかくがんばってみるか.

くずれる男

みょんが負けてくずれる男の AA でも書くかと思い探していたら,MY・くずれる男コレクション なるものを見つけた.結構うまいものもあって,特にNo.22が凝った作りでなかなか良いなぁとおもふ.

みょんが負けた...

第2回東方最萌トーナメント でみょんが中国に敗れてしまった... 霊夢以外は一回戦での得票数の多いほうが二回戦で勝っていたからやばいかなぁと思ってたけど,やっぱり負けてしまったのはショックだ.でもまあ,ゆゆ様が敵をとってくれるに違いない.

グリチャレ

今日は昨日からぶっ続けでグリチャレのプログラムを書いていた.といってもまだローカルで計算する部分のみだけど.

昨日の晩から比べると約十倍位のスピードアップを達成できたのだが,これは元のプログラムが馬鹿だったのか新しいのがいいプログラムなのだかよくわからない... でもまあ,直交座標系でのインクリメントを Morton Order に変換して実行している部分をビット操作のみにしたり,ビットフィールドをバイト単位で操作するようにテーブルを作りまくって操作したりしているので,現状のアルゴリズムではこれ以上のスピードアップは難しそうではある.ということで,現状に適当に満足しつつ次はネットワークでのやり取り部分を考えねば... 明日中に予選問題の回答が出せるといいなぁ...

ちなみにグリチャレとは,1000CPUのグリッド上でみんなで大規模計算をする問題を解いて,その解答プログラフの速さを競うものであり,どうやら30チーム程度が参加している模様.解くべき問題は巨大な白黒画像中の黒い物体の数を数え上げるというもので,その入力画像自体は複数に分割されてグリッド上に分散されている.そして,分割されたファイルにまたがる物体の存在しない初級と,またがる物体のある上級の課題があるみたい.初級はローカル計算で数えた物体の数を足し合わせるだけで簡単だが,上級はエッジの情報を伝える必要があるため通信をうまくやれるかが勝負の分かれ目になりそう.

問題

「数字 2, 2, 3 と,加減乗除 +, -, *, /, 単項マイナス -, 論理演算 &, |, ^, ~ [and, or, xor, not], シフト <<, >> を用いて 0 ~ 10 の数を作れ.」などという問題を夕飯の調達中に考えていた.

とにかく ALU で実行できる演算と3つの即値で目的の数字を作るという単純明快な目的である.しかしながら,これは結構難しい問題であり,計算機にやらせようとしても計算時間がかかりすぎるので実際に解かせるのは難しい.(簡単なやり方はスタックマシンをシミュレートすることだろうけど...)とはいうものの,夕飯を食べ終わるまで考え続けた結果としてなかなか面白い答えを導くことに成功した.その結果を用いると,たとえば 1,1,1 と上の演算子で任意の数字を作れることになる.

原理の肝は,NOT が1の補数であり,単項マイナスが2の補数であることによる.すなわち, -n = ~n+1 という関係式が成り立つため,+1はいつでも作れる. これにさえ気づけば任意の数字を巣くることが可能であることもすぐに想像がつく.つまり, -~x = x + 1, ~-x = x - 1 を繰り返せばよいのである.

ちなみにこの事実は「ハッカーのたのしみ」の最初のほうに書かれていたりもし,知っている人は知っていることのようである.

頭が痛い...

今日は某大学でミーティングがあったのだが,ミーティング終了後大人5人がひとつの車にすし詰めになって帰るという状況が生じた.使われた車は天井が低く5ナンバーであるからして,後ろの3人は非常に窮屈である.そして自分はその後ろ3人の一人だったため今でも体というか頭が痛い状態....車の持ち主はこの3月に新しい車を買うそうで,是非とも大きな車にしてほしい.

ちなみに,前回のミーティングの際にも行きに同じメンバーですし詰めとなったのだが,このときには渋滞ありの検問に引っかかるというおまけもついて,ある意味完璧だった.

«Prev || 1 | 2 | 3 |...| 1068 | 1069 | 1070 |...| 1074 | 1075 | 1076 || Next»
Search
Feeds

Page Top