Cell
優勝しますた。部屋を片付けてテレビ置く場所を作ります。
http://as305.dyndns.org/~kik/public/mt_mine.c とりあえず置いてみた。実行環境がないんとasm化は大変だなあ。
平日かー。行けるかなー。28日は行けるけど。
ORIGNAL: sum=3c927c56, 292970508 ticks MINE: sum=3c927c56, 2313630 ticks ORIGNAL: sum=2e987a4d, 422626291 ticks MINE: sum=2e987a4d, 3328071 ticks ORIGNAL: sum=ef1b6aef, 310977433 ticks MINE: sum=ef1b6aef, 2454426 ticks ORIGNAL: sum=eedd251…
sum = 0; for (i = 0; i < 16; i++) { s0 = cntb(y[i]); s1 = cntb(y[i+16]); s2 = sumb(s0, s1) sum += s2 << i; }以上。じゃなくて、ところどころシャッフルにしたけどね。herumiさんと同じでまとめてやろうとすると、gccがレジスタ割り当てに失敗して酷い…
これは本当に偶然で、そうである必然性はないはずなのですが、 12 + 29 * 4 = 128になります。この関係があるために、上の回転量は1と-4とか-1と4とかになります。この関係をうまく使って、最初から適当にずらしておきます。 下のほうのビット並び替えを使っ…
普通に頭からビットを詰めていったら更新処理はこんな感じになります。 for (; count != 0; count -= 1) { <%= gen_update(0, 3, 4, 12, 12, "mask1") %> <%= gen_update(1, 4, 0, 12, 29, "mask2") %> <%= gen_update(2, 0, 1, 29, 29, "mask2") %> <%= gen…
本当は行列の計算を色々試してて気づいたんだけど y = y >> 1; y = y ^ (y >> 11);と y = y ^ (y >> 11); y = y >> 1;って、結果を見るとあまり差がないよね。ほんの少し正確に書くと word T1(word y) { return y ^ (y >> 11); }って関数を考える。T1の逆関…
69倍になったあとは、一ヶ月ずっとビット転置のやり方を考えてました。 ワード単位のときのような頭のおかしい配置方法があるんじゃないかと探してたんです。結局みつからなかったので、頭から順番にビットを詰めていく方法になりました。 qword mt_bs[32][5…
バイト単位じゃないともったいない。 z = si_lqx(spu_slqw(spu_gather(y), 4), mag_lut); r = spu_xor(spu_rlmaskqw(y,-1), z);これだと、ワード単位のgatherになっちゃって結果が4ビットしか得られないんですよ。 1命令使って、結果がたったの4ビットですよ…
みんなそうだと思うけど、even命令が大幅に過剰になっちまった。 しかも、僕のコードは1ワード1ロードシャッフル無しだから、それはもう多すぎてhttp://d.hatena.ne.jp/kikx/20090120これはループのアンロール前で内側に14回のループが残ってたんだけど、 こ…
革命的な方法はビット単位で計算したときにでてくるqwordの29ビット回転を1命令でやる方法です。 その話は次の次の次の次あたりかな。
謎の表の順番で更新すれば1ワード1ロードにできるのを擬似コードにしてみた。 ベクトル化はなし。 #define N 624 #define N 397 word mt[N]; word mtx[N]; void transform(word dst[N], word src[N]) { for (int i = 0; i < N; i++) { // 謎の表の通りに並び…
(y >> 1) ^ mag01[y & 1]をeven*1+odd*3でやる話。XORはevenでやらないといけないから右シフトは当然qword右シフトになる。 mag01[y & 1] は gb してテーブルルックアップすることにすると z = si_lqx(spu_slqw(spu_gather(y), 4), mag_lut); r = spu_xor(sp…
昨日の謎の表は56行と余り8ワードあるので、56行を4分割してベクトル化するベクトルの最初のワードに、最初の14行を割り当てる // 0: 509-282- 55-452-225-622-395-168-565-338-111 // 1: 508-281- 54-451-224-621-394-167-564-337-110 // 2: 507-280- 53-45…
ということで次回は (y >> 1) ^ mag01[y & 1]をeven*1+odd*3命令でやる話
// ---: 0- 1- 2- 3- 4- 5- 6- 7- 8- 9- 10 // 0: 509-282- 55-452-225-622-395-168-565-338-111 // 1: 508-281- 54-451-224-621-394-167-564-337-110 // 2: 507-280- 53-450-223-620-393-166-563-336-109 // 3: 506-279- 52-449-222-619-392-165-562-335-10…
黙ってたりしてたりするんじゃないのか？とりあえずテレビを置くスペースを確保して待ってるか…
まあこれでいっか。
というわけで、レポートを書き始めた。他の100倍を超えてる人がどれくらい頑張ってるかが問題だなあ。
今の方法じゃ全然だめじゃん。100倍超えて優勝間違いなしとか調子に乗ってた。昨日のアイディアを実装する前にこっちやんないと…
結局、TLEやらポーカーやらで一ヶ月も放置してたわけだが、二週間切ったので本気を出し始めた。ビット単位のベクトル化は一ヶ月の間ずっとエアコーディングしてたわけで、 書き始めると意外にさっくり動くものができた。しかし、実際にコーディングしてみて…
さぼっていたというかnethackやってたんだけど、ついつい昨日もnethackにつぶされてしまった。巷では84倍速とかいう話がでているようなので、そろそろ真面目に方針転換しようかな。 Fixstarsのお墨付きもできたわけだしな。
乱数であることには変わらないなんてのはデマだろう……mt[x][y] をx番ワードのy番ビットとして、出力の先頭3ビットが mt[0][9], mt[396][8], mt[623][8]こんな順番になってたら、8通り中4通りしか出現しないじゃないか。実際はテンパリングがあるから、最初の…
ころころ変わってた Hack the Cell の課題が落ち着いたような感じだが、スレの579のいってるやり方はさっぱり分からない。常識的に考えて、最初に思いつくのは な指数関数で加算を乗算にマップする方法だけど、 これは周期が になるのでだめだし、それ以前に…
まあとくに収穫はなかったけど、MTの周期性の証明は大体理解できた。
だいぶ伸びしろが減ってきた。 脳からひねり出さないと次の手が出てこない状態にはまだなってないが…
なので、もう書くことはない。
やっとmt[]の更新部分を実装できた。テンパリングのとこがまだ。予定してた速度は出たのでよしとする。 残りも実装した テンパリングの部分はまったく手付かずだったのだが、適当に実装した。やっとスタートラインに立てた感じの44倍速。ここからはasmvisの…
やっとこさ開発環境が使えるようになったので、色々試してたら、 これ以外ありえないだろっていういい方法を思いついた。まだ実装の途中だけど、優勝は間違い無しだね（えー
