cellプログラミングしちゃいなよ3

1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ] 前スレ Cellプログラミングしちゃいなよ2 pc11.2ch.net/test/read.cgi/tech/1183091522/ 511 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 21:45:34 ] >>509 そんなしょーもないことしてどうすんねん 優秀な学生の確保と活力ある社会人の引き抜きが目的だろ 512 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 21:48:52 ] うーむ・・・もはや手詰まりか 513 名前：202 mailto:sage [2009/01/18(日) 21:53:45 ] >>511 別に非関係者装って参戦してるとかそーゆーんじゃなくて、純粋に遊びで 挑戦してるらしいよ。 Cellのプロフェッショナルとしてのプライドをかけたお遊びねw マイミクのfixstars社員に「社内で5M切った奴いる？」って訊いてみたら？ 514 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 22:08:32 ] まあプロが俺に負けるわけにはいかんだろうがなぁ 515 名前：202 mailto:sage [2009/01/18(日) 22:21:31 ] ちょ、だんごさん4.8M切ってるのか。スゲー！ 516 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/18(日) 22:31:34 ] そこは驚くところじゃない まだ上はいるんじゃね？何となく。 517 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 22:52:28 ] >>473のコードを１命令変更しただけで4.8M切れたｗ さて、これをアセンブラに移してループの調整でも始めるかな。 518 名前：,,・´∀｀・,,）っ-○◎● mailto:でもなかったりする sage [2009/01/18(日) 22:56:16 ] だんごやさんピーンチ 519 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/18(日) 23:02:30 ] >>518 ちょっとﾜﾛﾀ。14cycleの時は１位との差が10000tick行くか行かないかの所まで 詰められたけど、ここまで来るとさすがに自信無いなぁ…。 520 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 00:24:58 ] >>479 実は載ってるところ少ないんだけど8サイクル以上位連続でロード/ストアしようとするとストールした記憶がある そこでいったんぶった切ってoddでそれ以外の事するかあけてしまった方が速くなったりとか 自分も去年かおととし気づいたことなんで厳密な事は覚えてないんだけど 521 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 00:52:56 ] ↑の制限は８サイクルよりは長いよ。でも 227 はそんな load/store はしてないと思う。 522 名前：202 mailto:sage [2009/01/19(月) 00:53:11 ] >>520 へぇ。 命令のバッファが空になるとLS命令をストールさせて命令をフェッチする とかそういうのがあるのかな？ 523 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 01:10:02 ] >>520 SPEのLSはポート一個しか無いので、DMAやload,storeが頻発すると、命令フェッチができなくなる場合がある。 Handbook の 3.1.1.3 に、優先度は、 DMA > load,store > 命令フェッチ と書いてある。 命令フェッチが必要な場合は、hbrp命令すると優先度が上げられる。 詳細は、 ttp://cell.scei.co.jp/j_download.html 「プロセッサにおける命令枯渇に起因する Synergistic Processor Elementの無限ストールの防止について」 あたりに書いてある気がするが、読んでもよくわからん。 524 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/19(月) 01:16:02 ] とりあえず詰ませてみたけど、asmvis 見てもどこでストールが起きてるのか 分からない状態。片っ端から nop/lnop 入れて検証するのかぁ…orz >>521 カンで16か20とみた。調子に乗ってループ展開しまくっていた頃だから、 知らない間にリミットを追えてしまったのかもしれませんね。 525 名前：202 mailto:sage [2009/01/19(月) 01:23:42 ] >>524 分岐ヒント命令のレイテンシが15cycleだから、それ以下の可能性が高い。 12cycle=24命令か8cycle=16命令分でオチるんじゃないかな。 526 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 01:42:57 ] >>523 DMA 用と load/store & ifetch 用の２ポートだった希ガス。 今回は DMA 関係ないけど、DMA は待たせられないからね。 で、load/store と ifetch でポート共有してるから、ifetch が ストールしないように、load/store は続けちゃだめよ、と。 527 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 08:09:41 ] 謎のデチューン（笑）で性能改善された説明になるな。 メモしておこう 528 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 12:42:42 ] 学生でやってるけど10倍すらキツい アセンブラ命令と複数対１命令で対応している組み込み命令は どの程度コンパイラによる最適化の影響を受けるの？ 基礎的な知識が圧倒的に足りていない件･･･orz 529 名前：,,・´∀｀・,,）っ[昼はカレー] mailto:sage [2009/01/19(月) 12:44:00 ] 要するに128バイト分の命令（32命令）をこなす間に8サイクル以上 LSにロード・ストアしないタイミングを確保すればいいらしい。 完全にEven/Oddが同時実行されてる場合はロード・ストアが1バッファあたり8命令を越えるとアウト。 2命令同時発行できないサイクルがあったりすれば1バッファを使いきるサイクル数が17以上に延びるので、その分は延びる。 たとえばEven側20命令、ロード・ストア12命令の32命令でも、バッファのフィルに必要な8サイクルを確保できる。 530 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 14:13:31 ] >>529 Handbook によると 「SPU instruction prefetches are 128 bytes per cycle.」 らしいので、32命令中に1サイクル空きがあればいいはず。 531 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 14:14:19 ] >>528 結果さえ同一ならバカ正直に「SIMD版MT」を実装する必要がない 532 名前：デフォルトの名無しさん [2009/01/19(月) 14:17:58 ] >>530 bitじゃなくてbyteかよ 533 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 14:30:33 ] そういえばDMAと命令フェッチが同じバスなんてことが書いてあるような 534 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 15:24:33 ] >>531ありがとうございます。>>209で言ってたようなことかな･･･ もういちど見直してみます 535 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 15:45:38 ] >>533 >>526 じゃなくて？ 536 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 16:12:20 ] >>530,532 LS の読み書き単位が 128byte だからね、たしか。 ただ、読み込み自体は 1cycle で終わっても、SPU の pipeline は 結構深くて、15cycle くらい前に fetch されてないとダメなはず。 他にも ifetch 起動条件とか色々あるよ。どっかに資料あると 思うけど、リンクとか張らないでみんな自力で頑張ろうぜｗ 537 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 18:04:15 ] www2.vipper.org/vip1074688.png.html 上から下までこうなってないところ捜す方がしんどい 538 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 18:47:38 ] あ、当たり前では？ 539 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 19:50:30 ] 俺も参加したいけど、どうせなら1位2位を争いたい。 でも団子屋さんみたいな暇人じゃないから勝てるわけもないので高みの見物。 540 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 19:51:04 ] ひまじんとはしつれいな 541 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 20:30:21 ] >>531 それ考えてるんだけど思いつかないんだよな アルゴリズム同じのまま使う命令の入れ替えと並び替えで15サイクルまでは来れたんだけど しかも現状じゃ隙間は残ってるのに依存性で詰められないところがあってもったいない ここにいる優勝候補さんたちは社会人部門だと信じてる 542 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 21:46:33 ] __builtin_expect()使っても意味ねー つか遅くなる 543 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 21:49:36 ] ！！！いままで使ってなかったんか！！！ｗ 544 名前：デフォルトの名無しさん mailto:sage [2009/01/19(月) 21:50:14 ] 今さら？ __builtin_expectでぐぐりゃそんな事例出てくるだろ。 545 名前：v127251.ppp.asahi-net.or.jp mailto:sage [2009/01/19(月) 21:54:45 ] だんごうぜー 546 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 21:59:07 ] ふゅーじゃーねいざん？ 547 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/19(月) 22:00:15 ] ループ内側の最適化は投げ出して、外側の整形作業に移るとしますか。 知らない間にリアルが２末マイルストーンとか言う無茶苦茶な事に なってたんで、現実逃避も程々にしとかないとマジでヤバイかも。。。 548 名前：デフォルトの名無しさん [2009/01/19(月) 22:00:49 ] なんで、こんなところに節穴がいるの？ 549 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 22:03:18 ] 俺の日記はリアルGateKeeperがよく読んでるけどね 550 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/19(月) 22:12:55 ] 今更になって>>389見て幻滅してきたorz メモリが無いと勝てる気がしない…。 551 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/19(月) 23:17:44 ] 15,000tick削減成功 いけるところまでやるか 552 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 00:57:49 ] とりあえず、>>389の一歩手前までたどり着いたのは良いんやけど、ここに なって拡張アセンブリが使い物にならない(>>458)事がハンデになってくる とは思わなかったorz >>551 まだ３日ほど楽しめそうですよｗ 553 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 01:35:27 ] >>552 一歩手前じゃなかったっぽい。見れば見るほど>>389が神に見えてきたorz 554 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 01:38:13 ] >>517 は何だったの？w 555 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 01:56:24 ] >>554 99.91%の壁の高さを痛感しているだけですよ、たぶん。 556 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 02:17:10 ] あー、>>389 の前提がおいらとは違うのか。 >>551 を見て >>389 は最適化途中だっただけと見てたんだが。 557 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 11:58:58 ] 素人だけど参加 命令書き換えとか、なかなか上手くいかないけど楽しいわコレｗ 558 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 16:16:18 ] >>557 命令自己書き換え(self modification)してんの？ 仕様書に書いてあるけど、その場合は sync しなきゃ だめだからあんま早くならない気がするなぁ… 559 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 17:53:14 ] 【Oddの】命令数削減法思いついた 560 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 19:24:19 ] 何命令くらいの所で頑張ってるんだろう？ 自分はもうこれ以上削れる気がしないけど… 561 名前：202 mailto:sage [2009/01/20(火) 19:56:42 ] だんごさんそのうち4M切りそうだなｗ 562 名前：202 mailto:sage [2009/01/20(火) 20:24:17 ] いや、でも4.7Mの壁は今までの壁と比べても相当キツイな。 提出日まで頑張っても超えられない気がしてきた。 563 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 20:45:21 ] なんですか4.7Mの壁って 564 名前：202 mailto:sage [2009/01/20(火) 20:49:02 ] >>563 余裕で切ってるってことかーーー！！！ マジで勝てる気がしねー。 565 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 22:03:02 ] 逆に遅くなったorz 566 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 22:08:50 ] だんご優勝できなかったらブログ閉鎖の方向でよさそうなのかな？ 567 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 22:13:22 ] なんでやねん 逆に優勝しちゃうといろいろまずいことならあるが 568 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 22:23:08 ] 3Mの壁が・・・。イチからやり直すか・・・orz 569 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 22:30:49 ] 16Gくらいメモリ使ったんですか？w 570 名前：202 mailto:sage [2009/01/20(火) 23:24:43 ] >>568 3Mって、、、俺らと同じ基準なら化け物スコアだな。 571 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 23:29:48 ] >>557 でも今日は酔っぱらってて自己書き換えの実装出来ないんだなー。 明日時間有ったら挑戦してみる。 572 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/20(火) 23:34:44 ] 30Mの勘違いの予感 573 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/20(火) 23:59:18 ] いつの間にか FAQ 更新されててﾜﾛﾀ > デクリメンタのオーバーフローを利用することは可能ですか？ > 今回の出題の趣旨に反するので不可能とします。 574 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 00:03:08 ] 不可能ではないと思うんだ。 575 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 00:06:04 ] 本日の捏造 spu-gcc43 -std=gnu99 -O3 -g -c -o mt_mine.o mt_mine.c spu-gcc43 -Wl,-Map,mt_kadai.map mt_kadai.o mt_mine.o mt19937ar.sep/mt19937ar.o -o mt_kadai ./mt_kadai ORIGNAL: sum=3c927c56, 294422087 ticks MINE: sum=3c927c56, 4694973 ticks ORIGNAL: sum=2e987a4d, 424720276 ticks MINE: sum=2e987a4d, 6772739 ticks ORIGNAL: sum=ef1b6aef, 312518235 ticks MINE: sum=ef1b6aef, 4983550 ticks ORIGNAL: sum=eedd2516, 290441206 ticks MINE: sum=eedd2516, 4631487 ticks ORIGNAL: sum=f7e967a8, 14385949 ticks MINE: sum=f7e967a8, 229457 ticks ORIGNAL: sum=1f37a7db, 214501370 ticks MINE: sum=1f37a7db, 3420537 ticks ORIGNAL: sum=c7d41f36, 295356889 ticks MINE: sum=c7d41f36, 4709875 ticks ORIGNAL: sum=aa9d2e9f, 259910600 ticks MINE: sum=aa9d2e9f, 4144655 ticks ORIGNAL: sum=8abd398a, 251178167 ticks MINE: sum=8abd398a, 4005396 ticks ORIGNAL: sum=a374bd58, 6118425 ticks MINE: sum=a374bd58, 97617 ticks 576 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/21(水) 00:19:26 ] >>575 目標修正、4.6Morz 577 名前：202 mailto:sage [2009/01/21(水) 00:54:43 ] ああくそ、やっと正しい答えが出た。 拡張インラインアセンブラ、かなり茨の道だわ。 レジスタ多いから、どのレジスタが期待値と違うのか判らん。 誰が悪いのか判らないアセンブリのデバッグしながら命令削るより、 C言語の上で一つでも多くのアイデアを実装した方が絶対効率的だ。 578 名前：202 mailto:sage [2009/01/21(水) 00:56:33 ] >>575 まだ4Mは切ってないようでｗ 大きな差が無くて安心した。 579 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:05:57 ] 今北。 課題は、MTの最適化ではなく、合計の計算の最適化なんだな。 後段の tempering は mt[] に影響を与えないので、tempering 後の 値を合計せずに、tempering 前の「とある値」を集計する。GF(2)の中で。 すると、tempering (相当の操作)は一回で済む。 ＜いまここ＞ 団子「スタートライン」ってこれのことだろ？ 次に、「とある値」を集計するだけの目的であれば mt[] を「真面目に」 計算する必要はなくって、かなり端折れる。(仮に、端折って計算した mt[] を pmt[]とする) どの計算が端折れるか、いま計算しているところ。 ＜もうすぐここ＞ 最後に、num_rand % 624 の端数ぶんをどう計算するかで手詰まり気味。 pmt[] から mt[] を計算し直そうとすると、mt[] を最初から計算する のとあまりコストが変わらない方法しか思いつかない orz いっそ、mt19937ar.c の mt[] を LS から探してしまおうか。 まず、num_rand % 624 となっている mti を探して、みつかった mt[] から pmt[] を検定する。 どうかな。 580 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:07:43 ] >>575 人間がレジスタを管理することなんて既に不可能と気づけよ。 581 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:12:12 ] >>579 あーぁ、GF(2) とか出してくるなよw 団子の「スタートライン」は全然そこじゃないって。 井戸の中で満足してる奴に餌与えちゃだめだってw 582 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:16:35 ] 井戸の中ｗ 583 名前：202 mailto:sage [2009/01/21(水) 01:21:54 ] >>579 ルールブレイカー発動か？ tempering前に何かを集計して・・・ということができれば劇的に 速くなるという発想はあったんだが、多分ムリだろと思ってやってないよ。 学がないもんで、GFを今Wikipediaで調べて、やっぱり意味不明だった。 584 名前：202 mailto:sage [2009/01/21(水) 01:24:09 ] >>580 Pythonでスクリプト組んで、アセンブラコードを半自動生成させてるから、 うまくいってるときは問題ないんだ。 一度計算結果が狂うと、どこが間違ってるのか全然判らなくなる。 585 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 01:46:28 ] >>202 Matsutomo et al.1994 にも、MK-tempering が GF(2) 行列の掛け算だ、 と書いてあるでしょ。 それから、MTが暗号乱数として脆弱なことは Matsumoto も認めることろ。 そこをつつかなくてどーするｗ 今すぐ ACM 逝って MT に批判的な論文嫁。 586 名前：579=585 mailto:sage [2009/01/21(水) 01:50:03 ] とかいいつつ、端数の処理が解決できなかったら俺の負け。 587 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 02:04:10 ] >>579 団子は何もしらないってことにまだ気付いてない。。。 588 名前：デフォルトの名無しさん [2009/01/21(水) 02:07:03 ] >>579 とりあえずそのままSIMD化しただけで放置してたんだが， そうゆうの面白そうなんでその方向性で考えてみるわ 589 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 02:25:40 ] ここが井戸か 590 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 03:40:48 ] ttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/0407-2.pdf 591 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 04:11:57 ] >>590 ポイントはここですか？w ＞ 「6.5.2 どこがフーリエ変換やねん」 592 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 09:33:19 ] ま　た　勘　違　い　の　【さ　ん　す　う　や】　か 算術師の花園へようこそ 593 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 10:18:06 ] ＞いっそ、mt19937ar.c の mt[] を LS から探してしまおうか。 このレベルのネタでいいなら、 num_randとseedの組を決めうちにして、switch(num_rand) { } で計算済みの結果返すようにしたら？ 変更されるらしいけどｗｗｗ アホの言ってることは要するにそのレベル。 螺旋の飛んださんすうやさんは計算機で如何実装するかという論点が欠けてる。 余談までに松本教授＆斎藤氏のＳＦＭＴがオリジナルのＭＴと比べて如何違うかって、最大の違いは Temperingの結果を都度（32bit×4要素分単位で）mt[]にフィードバックしてること。 それでうまい具合にビットレベルで数値がばらけてくれる。 逆にそれで依存関係が起きて128ビットを越えるＳＩＭＤでは効率的に実行できないわけだが。 >>580 ばかだな。レジスタ管理がどうとかなんて言ってないだろ。 ここまで全部コンパイラにやらせてるし 594 名前：557 mailto:sage [2009/01/21(水) 10:29:40 ] >>558 え、そうなの？ 仕様書あんまし読んでないからわかんないけど 俺がやってるのは例えばodd命令をeven命令に置き換えたりして 同時発行を促すとかそういうのなのだけど･･･ 595 名前：,,・´∀｀・,,）っ[タミフル] mailto:sage [2009/01/21(水) 10:45:30 ] oddをevenかよ。俺様はそれをやる段階じゃないな。 てか、件のＯｄｄ側の命令数削減法、実際やろうとするとレイテンシチェインが伸びて アンロールするレジスタ足りなくなる罠。本末転倒。 インフルエンザですが何か？ 596 名前：,,・´∀｀・,,）っ[タミフル] mailto:sage [2009/01/21(水) 10:55:31 ] >>578 俺が現在進行中のスコア貼ったことは一度も無い。 いまのところ3日前くらいのスコアばっかし貼ってる。 597 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 12:02:37 ] >>575が3日前だとして >>551の時点で15,000tick削減成功 だから少なくとも今は4.67M台未満ってことかな？ 598 名前：202 mailto:sage [2009/01/21(水) 12:11:40 ] やっぱりやる気でないから、数学的手法への挑戦はやめとく。 レジスタ上に一瞬とはいえ目的の乱数が出現する俺や団子さんに比べて、 数学的手法だと一瞬たりとも目的の乱数が出現しないから、 ※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。 の条件に違反しているという理由で reject される恐れもあるしね。 コード整理して、レポート書いて、提出しちゃおう。 599 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 12:18:46 ] レジスタ上に一瞬とはいえ目的の乱数が出現する俺や団子さんに比べて、 え？アレって出てるって言うのかな？ 俺はデータ構造的にあやしいことやってるけど。 600 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 12:20:02 ] >>593 結局自分で管理しないでコンパイラ任せじゃないか。 レジスタがいっぱいあるからといって自分で全て管理できるはずはないけど。 601 名前：202 mailto:sage [2009/01/21(水) 12:24:23 ] ひょっとしてまじめに乱数作ってチェックサム取ってるの俺だけか？？ 俺が団子さんに敵わないのもそのせい？？？ 602 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 12:31:58 ] >>600 だから何なんだ？管理できるとかできないとかお前は一体何を言ってるんだ？ 俺にはさっぱりわからない。 603 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 12:47:36 ] >>601 ちなみに、彼の珍理論で演算時間の短縮を図るには超次元立方体構造のレジスタや演算ユニットが必要だったりするから気にするなｗｗｗｗ 604 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 13:08:44 ] 団子が天才。はい。だからもうだまれ 605 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 13:43:41 ] >>604 誰だおまえ？スピード狂オタクの分際で調子に乗るな。 606 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 14:01:25 ] MT配列は教科書通りの結果になるように都度更新してるけどtemperingをまっとうな方法でやってる自信はないな。 607 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 14:48:01 ] >>603 おいおい、GF(2) 系の演算の高速化や簡素化はコンピュータの得意分野だぞ？ 今時の暗号なら当たり前の事だろ。実装した事ないのか？ 608 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 14:49:59 ] だったら実装してみろよ 机上の空論はおなかいっぱい 609 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 14:56:08 ] さんすうや君は端数を処理するのにチートやらないと無理だって言ってるんだろ？ ならどのみち芽がない方法だ。 610 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:07:30 ] > GF(2) 系の演算の高速化や簡素化は やってるよ。 MT[]のデータ状態に矛盾が起きない範囲でな。それが出来ないなら今回のコンテストは諦めろ。 611 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 15:21:50 ] 青筋立てないで落ち着け。 どこのスレでも痛すぎる。正しい事を言っているかどうかじゃなくて。 答えて欲しい質問からは逃げるのに叩けるところはどうでもいいところまでしゃしゃり出てくる。 612 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:35:50 ] なんだ答えて欲しい質問って？ 613 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 15:35:58 ] ゲハ厨学歴厨に何言っても手遅れ 614 名前：202 mailto:sage [2009/01/21(水) 15:38:49 ] 話題変わるけど、spu-gdbってどうやって使うの？ elfspe使ってspe用のバイナリを直接実行できるんだけど、 spu-gdb mt_kadai とかやってもデバッグできない。 今までデバッグは全部コードインスペクションと、mt[]のダンプ取って バグの箇所を推測するの2種類だけで全部やってた。 615 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:40:07 ] 負け犬の遠吠え 616 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:43:17 ] >>614 SPUの実行イメージをPPEから読み出すローダーでも作れば良いのでは？ cell.fixstars.com/ps3linux/index.php/Libspeプログラムのデバッグ 617 名前：202 mailto:sage [2009/01/21(水) 15:43:37 ] >>612 ※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。 の意味について、 1. プログラム中でmt[]の内容を計算していたら良いのか、 2. 全乱数wordについてtempering後の値も計算していないといけないのか、 3. それともチェックサムだけ合ってればなんでもアリなのか、 を質問してみて、質問して回答が2だとヤバイ？ 618 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 15:46:17 ] 俺に聞くな。 ちなみに俺はgenrand_mineを繰り返し呼んでも安全なように設計してる。 ぶっちゃけ外側の最適化はサボってる 619 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 19:26:33 ] >>612 >>381 は本当？　>>389 == 最適化中は本当？　>>575 の捏造は本当？ｗ 620 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 19:29:02 ] 鼻高々だな団子。 621 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 19:41:11 ] 手元にある最新のコードよりわざと悪い結果を貼ってるのは本当。 晒す実行結果は前のバージョンだったり、わざとデチューンしたり、色々。 622 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 19:47:57 ] なんか参加賞あるし、暇だからやってみようかな プログラム全然書けないけど このスレ見ながら楽しくやってみよう 623 名前：557 mailto:sage [2009/01/21(水) 20:34:12 ] >>622 自分もそんな感じ。 勉強と思ってのんびりやろうぜ 624 名前：579 mailto:sage [2009/01/21(水) 21:15:27 ] >>593 >switch(num_rand) { } で計算済みの結果返すようにしたら？ 全然ネタのレベル同じじゃないだろｗ >変更されるらしいけどｗｗｗ その上でのネタなわけだが。 >最大の違いはTemperingの結果を都度（32bit×4要素分単位で） >mt[]にフィードバックしてること。 ハズレ。 余談に余談を重ねると、MT と SFMT は GFSR である点で同一。 tempering のコストを MT の更新側に振っただけ。 >逆にそれで依存関係が起きて128ビットを越えるＳＩＭＤでは これも違うな。 MT の漸化式は g(w)_MT = w_0 A + w_1 B + w_M なわけだが、 SFMT は g(w)_SFMT = w_0 A + w_M B + w_{N-2} C + w_{N-1} D に変更されている。 これが効いてくるのは、レジスタ幅ではなくむしろ並列計算だろ。 625 名前：579 mailto:sage [2009/01/21(水) 21:16:53 ] >>603 超次元立方体構造ってなんだよｗ >>606 その教科書には、w 次 n 階の (T)GFSR も 1 階化すれば nw 次の GFSR になって、1 階線形漸化式に帰着するとは書いてなかったかい？ >>609 >端数を処理するのにチートやらないと無理だって言ってるんだろ？ 誰が無理だと言ったｗ 思いつかない＝無理なのか？ >>610 > > GF(2) 系の演算の高速化や簡素化は >やってるよ。 MT の内側は全て GF(2) なわけだが。 それを踏まえて外側を如何に GF(2) の上に持っていくかの話だ。 626 名前：579 mailto:sage [2009/01/21(水) 21:17:46 ] >>598=202 ヒント： 外側の sum += が仮に sum ^= だとしたら？ > 同じ乱数列を生成してください。の条件に違反している ちょｗｗｗ だとしたら >temperingをまっとうな方法でやってる自信はない >MT[]のデータ状態に矛盾が起きない範囲でな。 団子道連れだな。 627 名前：579 mailto:sage [2009/01/21(水) 21:19:00 ] 話を戻すと、課題(MTのsumを求める)は、次のように分解できる。 1. mt[] から pmt[] への線形写像を求める。 2. for (num_rand / N) 不真面目な計算。 3. pmt[] から(num_rand / N反復後の) mt[] を戻す。 4. for (num_rand % N) 真面目な計算。 5. tempering 厳密に言えば、mt[] と num_rand から不真面目な計算をして O(1) で sum を求める事も理論的には可能。が、その理論を 解析している時間はないわけ。 が、たかが 32N 次元程度の GF(2) 上のベクトルであれば、2 の 不真面目な計算を機械的に求めることも非現実的ではない。 いまそれを解析しているところ。 問題としているのは 3 の操作で、pmt[] が mt[] の線形写像で ある以上、完全に mt[] を元に戻すことはムリ。4 の計算も 不真面目化すればよいのだけれど、そのままでは num_rand % N に 応じて N 種類の不真面目計算方法が発生してしまってコード サイズ的にムリ。 なので、別の方法での不真面目計算を考えているところ。 O((num_rand % N) ^ 2) であれば解は見つかった。が、これだと 条件「num_rand が 10000 以上」に対してコスト・リスク大きすぎ。 まあ、1回目の不真面目計算が解析できれば、そこから芋づる式に 求まるんじゃないかと楽観視している。 ともかく、いまは解析結果待ち。 628 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:30:52 ] 妄想はいいから。 > ヒント： 外側の sum += が仮に sum ^= だとしたら？ →「あり得ない仮定を持ち出す」 これは詭弁の○○箇条にもあったな まあ珍理論持ち出しても無理だから諦めろ負け犬 くだらねーコンテストなんて目じゃねーぞ。 629 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:35:49 ] > その教科書には、w 次 n 階の (T)GFSR も 1 階化すれば nw 次の > GFSR になって、1 階線形漸化式に帰着するとは書いてなかったかい？ で、それはSPUの命令を使って何命令で実装できますか？ > 思いつかない＝無理なのか？ 所詮お前は口だけだな。 ハッタリは何も出来ない人間のためにあるものだぞ。 どう足掻いてもお前にはできない。 630 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 21:38:07 ] >>579 数学はよくわからんのだが、 自分が優勝だと勘違いしてるやつより期待してるからがんばれ！！ 631 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:39:12 ] ああ、ちなみに最初くらいに1ビット×128並列のビットスライス実装思いついたけど 全然速くなかったよ。 632 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 21:39:43 ] これはどれぐらい高度な数学が必要なんだ？ 633 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:41:31 ] さんすうやの詭弁は聞いて呆れる 634 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 21:58:01 ] >>632 これ読んで何書いてあるか解る程度。そのまんまだけど。 www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1441-14.pdf 1 ticks = 40clkで、PLAYSTATION 3のSPUのクロック数は3192MHz動作です。 num_rand = 58156364のとき、genrand_mineの実行時間は4.7MTicks程度かかりました。 このとき、genrand_mineの実行時間は何秒かかったでしょう？ これは簡単なさんすう（笑）の問題 でさ、pmt[]（笑）求めるのに何十秒かかるのかねぇｗｗｗ さんすうや（笑）は計算時間がいくらかかるか、メモリがいくら必要かそういう観点が欠如してるから困る。 その上机上論ばかり並べる。できることをしない。だからできない。 まあ、時間がかかりすぎてSPU Decrementerがラップアラウンドしてくれば、見た目のTick数は（ｒｙ 635 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 21:59:50 ] いや、だから、団子はやらんでいいから黙ってろやｗ 636 名前：579 mailto:sage [2009/01/21(水) 22:02:50 ] >→「あり得ない仮定を持ち出す」 物事を簡単に考えるための迂回路だ。TT800から始めてろ。 >で、それはSPUの命令を使って何命令で実装できますか？ だから解析中だって言ってるだろうが。 解析結果？出てねーよ。 課題アナル(仮称)を prolog で実装した策略ミスだ。それは認める。 vsz は順調に(?)太っていってるから、あと 2,3 日ほっといてみるか。 637 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:12:27 ] 59ms弱だよ。 前提からしてアホだろ MT[n]のsumをTemperingしたものと TemperingFunction(MT[n])のsumは全くの別物 んで、頭弱い子は加算命令をXORとANDに分解してソフト的に加算すればいいと思ってるだろ？ レジスタ足りる？むしろメモリ足りる？ っていうか、脳みそ足りてる？ 638 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:15:06 ] >>634 なんとなく分かりました。高度な数学というよりも新鮮なアルゴリズムに気がつくかどうかの問題だし、素数を探すプロジェクトとなんか似てますね。 639 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:22:43 ] 団子はうざいが、 >>637 >レジスタ足りる？むしろメモリ足りる？ > >っていうか、脳みそ足りてる？ これは笑ってしまった。く、くやしい。 640 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:24:26 ] なんにせよ10000≦num_rand＜UINT_MAXだからなぁ 何十年かかる計算を数学的解析によって短縮云々なら価値はあるが 数十ms程度で終わる計算相手にスピードを競うアプローチとしては無謀を通り越して馬鹿かと 5段階の1段階目だけで既に終わってる希ガス。 それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに求めるアルゴリズムでも解明して下さいよｗｗｗ 数十年来の課題ですｗｗ 641 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:25:19 ] fixstars側に十分な数学の知識がある人がいて なおかつコンテストで生み出されるコードが後々の役に立つものであってほしいと願っているのなら 素直に乱数を作って加算するのが一番速くなるような問題になっているはず、 と信じたい 642 名前：579 mailto:sage [2009/01/21(水) 22:26:22 ] >>637 頭悪いな。お前が cite した文献に書いてあるじゃん。 > MT の解像度は最大可能な解像度と比べるとかなり悪くなっている > MT の解像度は最大可能な解像度と比べるとかなり悪くなっている > MT の解像度は最大可能な解像度と比べるとかなり悪くなっている > この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。 > この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。 > この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。 643 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:30:54 ] 負け犬は遠吠えだけは達者だな んで、計算時間は具体的にいくらですか？ O(n)のアプローチのほうが賢明ということもありますよ。 > 1. mt[] から pmt[] への線形写像を求める。 どうせこれだけで天文学的な時間かかるんだろ？ｗ 644 名前：579 mailto:sage [2009/01/21(水) 22:34:24 ] 線形写像求めるだけで天文学的なんて、どこまでお花畑なんだぜ？ 645 名前：デフォルトの名無しさん [2009/01/21(水) 22:35:19 ] 熱い・・・熱いぜお前ら いいぞもっとやれ 646 名前：579 mailto:sage [2009/01/21(水) 22:36:17 ] >>645 いや断る。俺下痢。寝る。 647 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:36:36 ] ・メモリ210KBが使用禁止 ・チャネル使用不可（メインメモリ間のDMAももちろん不可） まあとりあえず脳内珍論はブログでやれ。 648 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:38:54 ] 線形写像 = 実機動作、高速 解析 = 事前作業、低速 649 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:40:06 ] 机上の空論には 「Temperingはランダムテーブルルックアップで1回の操作で行うことができますが、 4Byte×2^32 = 16GByteのメモリが必要です」 みたいなオチがつくんだよね 650 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:42:01 ] >>648 > 線形写像 = 実機動作、高速 > 解析 = 事前作業、低速 その「線形写像」なんだけど、46KB未満のメモリ空間で確保できるLUTで 一体なにができるのｗｗｗｗ 651 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:42:56 ] 線形写像の意味わかってる？ 652 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:45:43 ] 線形写像を実装する方法をソフトウェア工学ではLUT（ルックアップテーブル）って言うんだよ。 Cellはローカルメモリが小さいから一般的には不向きと言われる。 653 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:47:26 ] ほうほう、じゃそれはアルゴリズムで実装することはできないんだな？ｗ 654 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:47:47 ] おいおい団子ちゃんよ、高校の"さんすう"からやり直したらどうなのさ 655 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:50:24 ] ＞ほうほう、じゃそれはアルゴリズムで実装することはできないんだな？ｗ 君の「アルゴリズム」が何を指すのかわかりませんが LUTもアルゴリズムの一つです 656 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:51:42 ] すまん、「LUT でなく、演算で求めることは、できないんだな？ｗ」だ。 657 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:53:19 ] テーブルのオフセットをアドレスを求めて値をロードするのも「演算」です。 658 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 22:56:17 ] むしろNOP系の命令以外は全て演算なんじゃないの？ 659 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 22:58:02 ] ま、何でもいーや。線形写像＝ＬＵＴね。tempering も LUT でやってくれｗ 660 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:04:17 ] だんご大丈夫か？ ＞ インフルエンザ 661 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:04:22 ] ﾌﾟｯ まさかビット論理演算の組み合わせだけでやろうとしてるのか？ それはそれで何もパフォーマンス上の優位性ねーし まあ何がアホかって、結局のところ>>637なんだけど 662 名前：202 mailto:sage [2009/01/21(水) 23:04:55 ] >>656 俺は専門卒なので難しい数学は判らないのだが、 元の計算式自体が「LUTではない方法」で、 結局難しい用語を持ち出してる数学屋の言ってることは 「元の計算式と同じ事をするより短い別の計算式を見つければおｋ」 って事？ それなら、最初に計算式とにらめっこして、「俺には無理」と判断してる。 Prologで何ができるのか知らないけど、元の計算式より計算量の少ない 式が出てくるっていう根拠が数学屋にはあるの？ 663 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:05:31 ] >>660 みなぎってきたｗｗｗｗｗｗ とりあえず今週一杯サボるｗｗｗｗｗ 664 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:07:00 ] >>662 結局は>>649的な実用性のない発想だから気にすることはない。知識におぼれて本質が見えてない人間が暴れてるだけ。 665 名前：202 mailto:sage [2009/01/21(水) 23:09:32 ] MTの初期値が固定されていたら何かを打ち破る抜け口がありそうな気がするけど、 init_genrand() の引数と num_rand が未知の場合、「乱数のチェックサム」の計算を ショートカットするのは無理そうというのがソフト屋の直感。 数学屋と違って何の根拠もないし、自分でもそんなに信じてない直感だけどな。 666 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:12:40 ] >「元の計算式と同じ事をするより短い別の計算式を見つければおｋ」 そういうことだ。Tempering より短い写像式を見つければＯＫ。 って、Tempering も十分短いから無理っぽいけどなーｗ 667 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:13:08 ] 暴れているのはだんごである 668 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:14:37 ] だんごは鳥インフルエンザ 669 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:16:59 ] 中の人二人いて煽り担当とプログラミング担当がいるコテの人はずるいと思います。 670 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:17:29 ] >>666 たとえば A XOR (B AND C) これをたとえばMUXを使って式変形するとどうなる？ って、このレベルの試みは俺もとっくにやってるわけだが。 671 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:19:12 ] >>669 ３人じゃね？両方○も居た希ガス 672 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:20:22 ] >>671 団子三兄弟ってやつか 673 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:24:56 ] そんなに必死にならなくても大丈夫だよ、団子さんより頭の悪い人だっていっぱいいるから 674 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:28:06 ] >>673とかな 675 名前：673 mailto:sage [2009/01/21(水) 23:30:02 ] >>674 まぁ、本当のことだから何もいえないけどね 676 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:31:53 ] B = A XOR D が成立するとき A XOR (B AND C)　＝　spu_sel(A, D, C) これ、豆知識な 677 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:44:40 ] 結論から言うと>>676は今回使うところはどこにもありません。 たとえるなら、RPGで毒の沼に入ってもダメージを受けない装備を手に入れたけど この先毒沼なんてどこにもありませんって感じかな。 ↑ これの元ネタ解った奴は俺のドッペルゲンガー 678 名前：デフォルトの名無しさん mailto:sage [2009/01/21(水) 23:52:10 ] >>676 そういうのを代数学の知識で証明できるようになりたい 679 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:52:33 ] 知ってると思うけど団子の中の人は広大の松本研究室とメールやりとりしたことがある。 結論を言うとseedとnum_randからpmt(笑)を求めるための一意な論理式なんて存在しないよ。 あっても計算時間・メモリ容量的に実用的なモノではない。 680 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/21(水) 23:53:34 ] >>678 カルノー図書けば一発じゃないか 681 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:02:26 ] >一意な論理式なんて存在しないよ。 いや、存在はするんだってば。実用的なのが見つからないってだけで。 682 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:04:44 ] Cell使ってしらみつぶしに探しちゃえば？ 683 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 00:05:41 ] その上、端数を処理するのにチートしないと実用的な性能出ないんだろ？ しねばいいのにｗｗｗ それに比べればこちとらまだ青天井みたいなもんだよ。 684 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:11:57 ] どうせMT高速化やるなら、ついでに多変量正規乱数までやってくれよ デキバイによっては金出すぜ 685 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:15:40 ] 出来栄え? 686 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:16:46 ] あーそれだ 日本語苦手だ許せ 687 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:21:04 ] > こちとらまだ青天井みたいなもんだよ。 13cycle 切れた訳でもあるまいにｗ 688 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 00:26:07 ] たとえばさ、 「genrand_mineが呼ばれる前には、必ずinit_genrand_mineされると仮定してかまわない」 とはあるが、関数を呼ぶ直前にinit_genrand_mineを呼ぶなんて言ってないんだぜ。 たとえば極端な話、 init_genrand_mine(seed); hash = genrand_mine(num_rand) + genrand_mine(num_rand2); みたいな鬼畜な条件での測定にしてきて、サマリ値不整合で失格続出になるかもしれないんだぜ？ 俺はどう転んでも言いように丁寧な実装してるけど、 仮定して構わないって言ってること以外は仮定しちゃ駄目だと思うんだぜ。 とりあえず誰か質問してきてよ 689 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 00:27:52 ] >>687 58156364 / 4 * 13 / 40 = 4725204.575(ticks) だけど何か？ 690 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 00:30:14 ] 既に12clk/qword台の闘いなんだぜ？ 691 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 00:36:13 ] >>688 あー、それは俺も思った。 あと、num_randの期待値も。 下限10,000だけじゃ外側、内側の比重設定に困る。 692 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/22(木) 01:08:36 ] 今日もEven13clockの壁を突破できなかった。なんか極大点に達してるような 気がするので、どこまで戻せば正しい道に戻れるか探してる所です。 693 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 01:15:57 ] コアの部分でEven:12.5、Odd12.1サイクル位 革新がない限りこれ以上どうにもなる気がしない 694 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/22(木) 01:18:27 ] >>580 レジスタ１２６個使えるんで、カラーリングの必要が無いから楽ですよ。 >>614 stqr + printf でデバッグしてます。バグが出たときは svn diff。 695 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 01:24:15 ] >>693 ループの内側スカスカだったりするだろ？ 696 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 01:31:34 ] >>688 その場合って mti もちゃんと更新して、mti が０じゃない ところからでも再開できるようにしてんの？ 697 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 01:32:40 ] 全部アセンブリで詰めてるから隙間なんて150サイクルの間にOdd4個あるだけだよ 698 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 01:36:34 ] >>696 当然 699 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 02:13:27 ] evenだけ12切る方法思いついたがOddが恐ろしいことになる 700 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 03:57:56 ] 刹那な午後の人が hack the cell 始めてる〜 ＆ここも見てるっぽい。 いやー、さんざん勉強させて貰ったんで、なんか感慨深い感じ。 701 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:13:25 ] ああ、herumi氏のことか。 ここじゃないと思うよ。 リアルGoogle社員の人の日記（あそこのこと）見て真似を始めたらしい。 交流があるそうな。 去年ぐらいから一連のやり取りヲチしてるけど 東大院出身と京大院出身の頭脳バトルは見てて面白い。 素晴らしいじゃないか。 俺もherumi氏と戦えるなら負けても悔いはない。 ＃妨害ついでにXbyakのAtom新命令対応パッチまた送りつけてやるかﾋﾋﾋ 702 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:29:35 ] まてよ 60倍云々って・・・俺のカキコが初出の情報かもしれない・・・ｗｗｗｗ まああの人は俺の日記読んでるからな 703 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 04:46:51 ] んー、わからん。誰だろ？ > real google の人 &日記更新してたんね。15cycle の latency の話だけど、 6cycle なのは命令実行後 LS に反映されるまでの latency だから、命令解釈やら register file から各演算器の latch への転送とかの 15cycle とは別物だよー。マジ長いねw 704 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:51:42 ] しょっちゅうherumi氏が日記のネタにしてるじゃないの ヒント：「yajit」 705 名前：202 mailto:sage [2009/01/22(木) 09:29:56 ] 俺も初めてアセンブラ触った動機がMMXで画像処理したい！で、 へるみさんのサイトに散々お世話になった。 なんか感慨深いなー。 706 名前：202 mailto:sage [2009/01/22(木) 09:31:57 ] >>704 チーム参戦型のICFPプロコンで、個人で上位を取っちゃうあの方ですね、わかります。 707 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 16:11:09 ] 今日もサボリのタミフルが、何故かおとなしいな 708 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 16:16:48 ] 呼んだら出てきちまうだろ！ｗ 709 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 20:26:42 ] くそー、13 切れねぇ orz 710 名前：202 mailto:sage [2009/01/22(木) 21:07:07 ] 13が増えてきてるのが凄く脅威なんだが・・・ 693、俺、だんごさんが13切ってて、227と709が13か 711 名前：579 mailto:sage [2009/01/22(木) 21:08:07 ] >>640 >それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに >求めるアルゴリズムでも解明して下さいよｗｗｗ 暗号乱数とモンテカルロ乱数は別物だと何度もいっているだろバカ >>647 >まあとりあえず脳内珍論はブログでやれ。 ブログに書くほどの内容でもないからここに書いているわけだがｗ >>657 >テーブルのオフセットをアドレスを求めて値をロードするのも「演算」です。 これは痛すぎるだろ。tempering も線形写像なわけだが。 >>683 >それに比べればこちとらまだ青天井みたいなもんだよ。 青天井の意味知ってる？ 712 名前：579 mailto:sage [2009/01/22(木) 21:10:55 ] どうせ団子理解できないだろうから教えてやるよ。 その前に md5sum = 770e20e29056b7e5d420fc46bdc5ee6a >>637 >んで、頭弱い子は加算命令をXORとANDに分解してソフト的に >加算すればいいと思ってるだろ？ >レジスタ足りる？むしろメモリ足りる？ お前が挫折したからって俺と一緒にするな。 数値の表記法は n 進表記だけじゃないんだぜ？ 欲しいのは 2 進表記の sum なわけだが、最終的に変換可能で あれば途中経過の表記法は何だって構わない。交番だっていい。 問題なのは、mod 2^32 がガロア体ではないことだ。 713 名前：579 mailto:sage [2009/01/22(木) 21:11:18 ] ループの内側がガロア体で、外側がガロア体ではなかったら、 そりゃ計数するのは非効率だろう。だったら、2^33 のガロア 拡大体の上で計数してみようという発想にはならんのかい？ 33 次 M 系列の生成多項式 (33, 13) を使えば、十分実用的だ。 この系で 1 を計数する方法を考えれば明らか。 外側のループが ^= になっただろ？ >>628 >→「あり得ない仮定を持ち出す」 馬鹿が。 いくらお前でも、ガロア拡大体上での計数を前提としておけば、 tempering をループの外側に出せることも少し考えればわかるだろ？ そして、最後にシンドローム計算すれば 2 進表記に戻せる。 714 名前：579 mailto:sage [2009/01/22(木) 21:11:51 ] >>631 >ああ、ちなみに最初くらいに1ビット×128並列のビットスライス >実装思いついたけど全然速くなかったよ。 馬鹿はここで諦める。 ガロア拡大体上での計数は、ビットスライスで行った方が効率が 良いは明らか。が、mt[] の更新をビットスライスで行うのはいささか 非効率。これは、MT が "ビットスライスではない" 計算機での効率を 狙ったものなので当然といえば当然。 ビットスライスではない計算機で扱える効率的な線形写像は、 行列 [[0ii,0ij]T,[Iij,Ojj]T] (つまりビットシフト) の掛け算と 要素どうしの掛け算(AND)と足し算(XOR)、その組み合わせだ。 それに対して、ビットスライスで扱いやすい線形写像の条件は、 行列中に "1" の出現頻度が少ないもの。至極当然。 ならば、最初に mt[] を別の空間に写像しておいて、その空間で 更新行列の "1" が少なくなるように設計すればいくらでも (それこそ青天井に)効率は改善される。 715 名前：579 mailto:sage [2009/01/22(木) 21:12:34 ] しかし、これだけだとビットスライスを用いる根拠としてはまだ 少し弱い。それは、mt[] のサイズがレジスタ数と比較して大きい (load, store をスケジュールするのが大変)のと、"1" の割合を 減らせたとしても行列自体が大きいので、必然的に計算量は多いまま。 そこで、mt[] 自体を小さくすることを考えよう。 が、残念なことに MT は mt[](19968 bit)のうち、19937 bit が 直交していることが理論的に証明されている。 さて、どうしよう？ >>640 >なんにせよ10000≦num_rand＜UINT_MAXだからなぁ 答え書いてあるじゃないかーい。INT_MAX だけどな。 つまり、32bit の seed から始まる 31bit の空間は、19937bit の 空間の中で、非常に小さな部分空間でしかない。 その小さな部分空間では、19937bit の大部分が直交していない。 直交していないビットは、それこそ計算する必要はない。 課題アナル(仮称)の正体は、直交していないビットを探索するものに 他ならない。 716 名前：デフォルトの名無しさん [2009/01/22(木) 21:23:46 ] だンゴサんの括約で棺桶スレが成立したな 717 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:33:32 ] >>579 なんでこんな大事なことばらしちゃうの？ｗ 718 名前：202 mailto:sage [2009/01/22(木) 21:36:40 ] 一応、みんな判ってると思うが、Hack the Cell の課題が何か確認しておく。 ttp://cell.fixstars.com/challenge/challenge.html 課題は、メルセンヌ・ツイスタの最適化です。 注意事項 ※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。 719 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:39:22 ] 芽のない方法を芽がないと割り切る能力が欠落した人間の遠吠えはむなしいのう 720 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:42:03 ] >>717 机上の空論だよ 突っ込みどころのデパート。詭弁の集大成。 まったくもって今回の課題の解法として役に立たない。 721 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:45:16 ] >>710 あれ？202 も 13 切ってたの？ >>598-599 のやり取り見て、 まだ切ってないと思ってたよｗ >>720 自分も >>599 が当てはまるとやばいんじゃないの？ｗ 722 名前：579 mailto:sage [2009/01/22(木) 21:47:43 ] 連続投稿引っかかったｗｗ 最後に、端数をどうするかだ。 その前に、報告しておく。俺のアナルはもう検算フェーズに入ったぜ？ ざっくりと pmt[] の最悪値を見積もり始めた頃から勝算はあった わけだが、解析結果を見ると想像以上に小さい。 これが何を意味するかわかるな？ 第一に、mt[](pmt[]) の更新はほぼ O(rn^2) のコストであること。 r は線形写像行列に含まれる "1" の割合。n は行列のサイズ。 第二に、pmt[] から計数ベクトルへの写像行列を N-1 種類まるまる 用意してもメモリサイズ的に余裕ができたこと。 いまからマネしようとしても、解析の方法なんて想像もつかないだろ？ お前はご自慢の 59ms アナルでおとなしく全数探索でもしていろｗ さーて、そろそろ実装でも始めますかｗｗｗ 723 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:50:46 ] >>721 単純にMTの式をMTを32ビット×4並列化したものではないということだよ。 配列状態とサマリの値が等価になる範囲で高速化出来る方法は全て駆使してる。 もうやることは終わってさじ加減次第かな。 部分的にスカスカな部分があったりするのでループ全体を見て命令数が減るようにバランス調整が必要だ。 724 名前：579 mailto:sage [2009/01/22(木) 21:51:09 ] >>719 自分に自信がないやつほど声がでかいってのは本当だったんだな。 725 名前：579 mailto:sage [2009/01/22(木) 21:52:11 ] >もうやることは終わってさじ加減次第かな。 青天井じゃなかったのかよ 726 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:52:40 ] >>722 机上の空論は結果を出してから言うことだ 727 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:53:13 ] >>724←これとかな 728 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:53:27 ] >>579 アンタ、糞団子と接するのは初めてかい? まあ力抜いてアナル(r 729 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:00:14 ] だんごも>>579もすごいぜ 少なくとも議論の台に乗れるんだから 俺も工学系だから少なくとも理系ではあるんだが何を言ってるのか全くわからんｗ とりあえずサイクルの話はあんまりしない方がいいとおもた サイクルの話見ただけでどこの最適化やっててどこの最適化やってないか想像できるし 730 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:00:24 ] 負け犬579をアボーンリストに追加しとけばいい 彼は全然役に立たないことしか言ってない。 まあ見えない敵と戦ってる馬鹿だから相手にするな 731 名前：579 mailto:sage [2009/01/22(木) 22:05:16 ] >>717 どうせ団子理解できないだろ？ >>718 >※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ >乱数列を生成してください。 何をもって「同じ」とするか、だ。 tempering 前の数値も tempering 後の数値も、表記法が 異なるだけで、同じ数値なわけだ。tempering した方が モンテカルロに用いる上では好都合な事が多いので しているだけ。 >3. それともチェックサムだけ合ってればなんでもアリなのか、 >1. プログラム中でmt[]の内容を計算していたら良いのか、 >2. 全乱数wordについてtempering後の値も計算していないといけないのか、 これが 2 だったら、出題者が問題の意図理解していないよ orz 1 の判断は微妙だが、仮に 1 だとするとできる事は限られてくる、 つまりそんなコンテ誰が出ても結果は一緒。ツマンネ。 732 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:06:35 ] ハイ　おさらい。 pc11.2ch.net/test/read.cgi/tech/1158559031/l50 SSE実行できないCellでSSEの実測をしたという捏造の瞬間ｗｗｗｗｗ 864 名前： ・∀・）っ-○◎● [sage] 投稿日： 2007/06/17(日) 16:22:27 movd xmm0, eax movd eax, xmm0 movd xmm0, eax movd eax, xmm0 movd xmm0, eax movd eax, xmm0 movd xmm0, eax movd eax, xmm0 こんな感じで繰り返せば一応往復のレイテンシは計測できるよね で、何クロックかかるのかな？ 答えてね。俺より頭いい子ならすぐわかるはず。 もっとも俺は実測結果あるけど 866 名前： デフォルトの名無しさん [sage] 投稿日： 2007/06/17(日) 16:26:12 CellでSSEって 733 名前：202 mailto:sage [2009/01/22(木) 22:08:13 ] >>721 >>689は超えたよ。 結構苦労してアセンブラ書いたしね。 >>721(=>>693?)もだんごさんも、tempering後の値をまじめに計算して add を繰り返してる訳じゃないのか・・・ とりあえず、チェックサムだけ合ってればOKなのか訊いてみて、 OKならまただんごさん超えに挑戦してみるよ。 734 名前：579 mailto:sage [2009/01/22(木) 22:09:04 ] >>728 アナルの力抜いておくよ。 >>730 ｶﾞｸﾌﾞﾙしている姿が見えて楽しいよｗ 735 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:09:26 ] 693だけどtemperingは毎回やってる というか処理の7割がtempering 泣きそう 736 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:15:59 ] 話の腰をもんで悪いんだが temperingってなんだ？ 737 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:17:17 ] 揉むな!ｗ 738 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:20:06 ] 勘で出てきた乱数を32bit空間で偏りが無い様に再マッピングしてるんだと勝手に思ってた 739 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:21:20 ] マージャン用語です テンパイ ＝【聴牌】 麻雀で、あと一枚必要な牌がくればあがることのできる状態。 これが、転じて何か事を成し遂げようとしたときの最終段階、、待ちの状態になったときに使うケースがあります。 てんぱる、てんぱってる。 スタンばる（スタンバイする）、、などと同じ和製語ですね。 740 名前：579 mailto:sage [2009/01/22(木) 22:22:14 ] さてさて。 一日静かだと思っていた矢先、団子登場。団子はよっほど俺の アナルが好きなんだなｗ　頼むから寝込み襲ってくるなよ。 この手の作戦だと実装を後回しにした方が効率いいわけだが、 結果出せ出せウルセーやつがいるから、俺はそろそろ実装始める ことにするよ。 その前にクソして寝る。 741 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:23:20 ] >>739 そうだったのか… 勘とはいえすごい的外れな嘘を教えてしまった ごめんよ>>736 742 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:27:12 ] おおざっぱに、MTで乱数生成の為に行うアルゴリズムでビットシフトを行う操作のことだな tempering 743 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:30:00 ] >>729 暗号論の世界にも差分解読法なんてのがあって、ビットの並びの特徴から演算をショートカットする 方法に関しては俺自身もいろいろ試したことがあってね。 んで、今回はそういうショートカットは全くもって役に立たない。 MTのTemperingはフェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。 RISCオペレーションで10命令程度のビット論理演算で構成できるとはいえ、 けっこううまい具合にビットがばらけるように考えてある。 加算ってさ、簡易的にはXORとANDの組み合わせで作れるわけだけど、 キャリーアップ先は、1ビット隣じゃん。 Tempering前と後じゃその1ビット隣すら全然別物になっちゃうんだよね。 だからTempering前の値をいくら「加算」しても無意味なんだ。 Temperingは少ない命令数ながら、うまく考えてあると思うよ。 暗号の実装の話になるけど、AltiVecのVPERMやSPUのSHUFBはAESのS-Boxを16並列で処理する ことができるけど、SSEだと同様のシャッフル命令であるpshufb命令なんかを使うより別の方法のほうが速い。 今回の課題はそう言う観点で何が最適なアルゴリズムかを考えられる人でないと難しいと思う。 744 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:31:58 ] > フェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。 ち・が・う 745 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:34:09 ] >>739 (y << 15)んとこが16だったらアレしてこうして・・・とか思ったけど なかなかうまくいかないもんだね 746 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:36:08 ] >>744 あらゆるフェイステイル型暗号のS-boxはビット論理演算の組み合わせだけで実装できるの知ってる？ 747 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:37:44 ] お得意の bitslice か？　それと s-box の意義は全然別物だぞ？ 748 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:39:16 ] フェイステイル型暗号におけるS-boxの役割は、簡単に言うと前後のビットの並びの相関性を破壊するための仕組み。 MTのTemperingも、Temperingを省いて合計値を計算しようとしても出来ないようにする程度には相関性を破壊できてる。 749 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:45:37 ] そりゃ、暗号も擬似乱数も拡散って意味ではなんだって拡散だし、 ほとんどが論理演算の組み合わせで実装できるだろうよ。 その程度の意味で、feistel の s-box と同じって言ったのか？ 750 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:53:59 ] Tempering＝「調律」 スイーツ（笑）用語でいうとチョコレートコーティングの表面を滑らかにするための行程。 もちろん、そのまんまの意味で解釈しても意味はない。 ビットの並びの相関性をある程度破壊することに意味がある。 MTにおいては、相関を破壊することが、ビットの出現確率の均一化（Tempering）になる。 S-BoxのSはsubstitution ようするにテーブルルックアップなわけだが。 たしかにTemperingとS-boxは別の単語だが、言葉をそのまま捉えても意味はない。 本質を理解しないといけない。 テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。 だから本質的に同じだって言ったんだよ。 751 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:07:52 ] >テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では >ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。 へー、すごいなｗ。いや、LUT を使わない実装が標準とか思わないほうがいいぞ？ 暗号作ってる方は簡単なシフト＋ビット論理演算で求められないように sbox を 導入してるのに、なんか可哀想になってきちゃうよ。 まぁ確かに本質的には両方拡散だから同じだしなｗ 752 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:30:18 ] >>751 RSAのRivest Cipher(RC)シリーズとかMD5なんてS-boxを使わずにスワップを繰り返す 暗号・ハッシュアルゴリズムの代表格なわけだが？ RC6はAESの最終候補まで残ったぞ。 753 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:36:19 ] なんで軒並み落ちてって、今 feistel ばっかなのか考えようぜｗ 754 名前：デフォルトの名無しさん [2009/01/22(木) 23:37:45 ] >>743 よわかりませんが、M系列で「加算」する場合もキャリーは１ット隣なのでしょうか？ 755 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:42:56 ] >>754 最低限言えることは、SPUには任意の位置のビットにキャリーアップしてくれるような特殊な算術加算命令はないということだ。 まあそういうことだ。 ハードウェアに不向きなことをやらせて性能を出そうという方が間違い。 756 名前：デフォルトの名無しさん [2009/01/22(木) 23:49:49 ] なんだかよくわかりませんが、よくわかりました。 ありがとうございました。 757 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:55:21 ] 関係ないけどJNBのトークンって暗号形式なんだったっけ？ 758 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:59:44 ] そろそろ詭弁の○○ヶ条で〆てくれ 759 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:06:08 ] >>753 そこはAESばっか、に訂正しろよ。 AESが世界的に選ばれてるのはAESがAESだからだ。 AESに選ばれなかったfeistel暗号の信頼性を保証する根拠にするのは間違いだな。 とっくに死んだはずのDESが何故かワンタイムパスワードとして現役で使われてたりするくらいだし。 そのレベルで言うならMD5やRC4だって未だに使われてるんだぜ。 iがつかないニンテンドーDSだとWi-FiはWEP（RC4）強制だしｗｗｗｗｗ それに比べれば国産暗号のMISTYとかCamelliaなんてまだまだマイナー杉。 松井さんには悪いが。 760 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:11:09 ] ん？ DES も Feistel だろ？ MISTY1 も Camellia も NESSIE とってるが。 ＆ MD5 と RC4 をこれから新規に採用する規格があったら驚きだが？ 761 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:17:04 ] ちなみに、SHA-3 コンペでも feistel 使われてるぞｗ 762 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:18:28 ] 当たり前のこと言ってどうすんだ。鍵長考えてものを言え。 引き合いに出すならRC6あたりだろ。 RijndaelがAESに選ばれたのはその一つとしてDESみたいな複雑なビットシャッフル演算がなくて 専用ハードウェアでなくても実装コストが軽いからだ。 別にRC6の暗号強度が否定されたわけではない。 763 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:30:55 ] すまん、ちょっと読み違えてた。が、時間がない。また今度w あ、俺も RC6 の暗号強度を否定するつもりは毛頭ないよ。 764 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:33:43 ] そもそも別にLUTよりビット演算のほうがコストパフォーマンスが優れてるなんて言う気はない。 不毛すぎ 今回のTemperingを通す前にサマリ計算が出来るかどうかだが 実用的な計算時間をはじき出すのは「無理」と言えるレベルの相関性の破壊は達成できてるというのが 俺の見解。 俺個人は国産暗号マンセーの立場なので君に付き合ってRSAの腐れの擁護する気もない。 ちなみにSHA-3候補として俺が注目してるのはこれ ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf ＃あとAESは厳密にはSPNSであってFeistelには分類されない。 765 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:37:12 ] 日本語でおｋ 766 名前：デフォルトの名無しさん [2009/01/23(金) 00:39:15 ] 当たり前のこと言ってどうすんだ。 767 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:43:44 ] 個人的にCamelliaのSSE4向け実装とか開発中 おれ松井さん好きだし ＞Fixstarsさん 来年の課題はCamelliaでお願いします。 768 名前：復活 mailto:sage [2009/01/23(金) 01:17:25 ] >>764 俺の見解は、拡散って意味では tempering も sbox も同じってのには同意。 だが、シフト＋ビット論理演算ではできない substitution を実現するために sbox を導入してんだから、それを安易に同列に扱うのは理解できん。 あ、国産マンセーは俺も一緒。来年 Camellia いいねぇw 769 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:09:19 ] ま、とりあえず俺の情報源のひとつ晒しておくわ。 暗号アルゴリズム及び関連技術の評価報告 cryptrec.nict.go.jp/cryptrec_03_0424_outrep.htm S-boxを使わないRC6はかなり高い評価を得てるよ。 一般的なバイトマシン・ワードマシンでビット演算でやったらめちゃくちゃコストかかる演算を LUTなら簡単に実装出来たりする。S-boxの多くは、RISCプロセッサのビット演算にそのまんま展開すると とんでもない演算数がかかったりするんだが、それは暗号理論的な堅牢性の根拠としては弱いと思うよ。 バイトマシン・ワードマシンじゃなくて、ビットマシンとかASIC・FPGAだったら？ たとえばDESのS-boxはAND/OR/NOT/XORの基本的な1ビット論理演算で たったの平均56ゲートで構成出来る。 これは具体的にいうと32ビットワードの全加算回路に必要なトランジスタ数よりもかなり少ない。 AESのS-boxは・・・実装についての論文あったけど、いくらだったか忘れた。 （総当たりで最短を検索するプログラムが手元にあるけど8ビット×8ビットのS-boxは計算時間的に流石にきつい） 見方を変えようか AESやCamelliaはS-boxを除けば、DESのIP・E・P・FPでやってるような複雑なビット単位の 攪拌処理をやらずに、世界最高水準の安全性を実現してるわけだ。 更にいうと、CamelliaはS-boxは実質的に8ビット入力×8ビット出力のものがたった1つだけしかない。 その点でみてソフトウェアでの実装の複雑さと暗号的な強度は別モノと考えてる。 770 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/23(金) 02:17:31 ] >>710 とりあえず13clock切れた。けど謎のストールに阻まれ停滞中orz 771 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:34:03 ] 本命：団子 対抗：>>202,>>227 大穴：>>579 772 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:44:12 ] Camelliaの教科書的実装より引用。 俺はなんでこれでAESなみの強度が得られるのか疑問だったよ。 #define SBOX1(n) SBOX[(n)] #define SBOX2(n) (Byte)((SBOX[(n)]>>7^SBOX[(n)]<<1)&0xff) #define SBOX3(n) (Byte)((SBOX[(n)]>>1^SBOX[(n)]<<7)&0xff) #define SBOX4(n) SBOX[((n)<<1^(n)>>7)&0xff] 2と3は1の出力値をローテートしてるだけ。4は入力値をローテートしてるだけ。 なんでこれで「AESなみの暗号強度を実現できる」（中の人談）のか >>771 というか、どうやら俺が見つけた最適化方法は既にこのスレで13clk切った連中は見つけてると思うよ。 あとは実装勝負なわけだが、アセンブラ相手にCで勝てる気はしない。 具体的にいうと現時点では>>693よりは遅い。ガチ。 （てかこの人が最速っぽい） ただ俺にとっては今回の挑戦はどこまでもHack the spu-gcc43なのだ。 アセンブラ使わないと優勝できないのはわかってるが、アセンブラを使うのは俺的に負けなのである。 Cのみで挑戦する人向けに特別賞でも用意してくれるなら俺は喜んで表彰台にあがってやるぜ。 （herumi氏も参戦してきたことで、それですら負ける気がしてきた） 773 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:47:12 ] まあ、どうやってコンパイラの副作用を抑え込んだのかっていうのはソースにびっしり書いてたりするから 俺が上位に残ってたら参考にしてくれ、的な。 774 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:55:35 ] >>769 俺の言いたい事は >>768 で言ったが、「今 feistel ばっか」とかが 気に食わないんかな？ sbox ＝ 堅牢と言ってるんではなくて、堅牢さと 速度を両立するのに sbox が向いてると言いたいだけなんだが。 シフト＋ビット論理演算だけで同等の堅牢さを実現するよりも、 sbox の方が早くし易いし、小さくもし易いって理解なんだけど。 だから NIST にしろ NESSIE にしろ、feistel 系ばっかなんでしょ。 それだけ別物だから俺には tempering と sbox を同列には扱えん。 以上。 775 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:55:47 ] >>772 俺はアセンブリじゃないと絶対に出来ないことをやってるから他の点の実装が一緒なら有利かもしれん 正直な話このスレで結構な数のヒント貰ったからこれがないと負けてた 776 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 03:46:15 ] この程度ならあんまり影響っていうレベルで、Cで組む人にアドバイス。 （というかC＋組み込み関数で俺に挑もうと考えてる奴は流石にいないだろう） 特にイライラしたのは、even側の命令減らしたいのに値のロードにimmidiate load（evenロード)に勝手に展開しやがること。 qword型でしてるのにimmidiate load。 どうやらQWORDの全要素が同一の値だと勝手にimm loadに展開しやがるらしい。 んで、volatileにしたらアドレスからロード（Odd）に展開してくれるようになった。 とか、いろいろ。 あと、AND/OR/XORなどで使う値はhalfwordに即値指定すれば命令数を減らせる。 俺としてはまた方針を変えてパイプラインを詰め直そうと思っている。 現時点で片方のパイプが全部埋まるところまでCで詰めることができてるわけで >>774 残念だが同意できない。 標準規格においてダントツのトップに君臨するAESはFeistel系アルゴリズムとちょっと似てるが分類上別物。 あと示したとおり、Camelliaは普通のFeistel型暗号で従来4つ以上のLUT（S-Box）が必要な処理を 1つのLUTとローテートで水増ししてるけど、その点で強度に問題があるといわれたことは無い。 単一のS-boxにビット演算を少し組み合わせるだけで、強度を得るのに必要なS-boxの数を 実質的に減らすことができるのだから、シフト・論理演算・定数の組み合わせでS-boxを使わずに 性能と強度を得るのが不可能とは思わん。 実際問題、S-boxを使わないRC6は多くのFeistel暗号より高速で、なおかつ十分な堅牢性がある。 S-boxがハードウェアの負担が小さいってこと自体同意できない。 モバイル向けのプロセッサにはAESのS-boxすらデータキャッシュに収まりきらないくらい小さいものもある。 CamelliaがSBOXを最小の実装でたったの256バイトのLUTだけで構成出来るように配慮されてるのは ミリワットクラスの組み込みCPUでの実装を視野に入れてるからだ。 CamelliaのS-boxが小さいことは、キャッシュメモリが小さいアーキテクチャにやさしいということでもある で、それでいて十分な強度という評価を得ている。 777 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 04:24:16 ] うーん、論点がどこなんだかイマイチ解らん。 feistel の sbox と spn の sbox は別物なのか？ 俺も不可能とは思ってないし否定もしないよ＞RC6 負担が小さいとも思ってない。堅牢性と共に、早く 出来ることも小さくする事も可能なのが重要なだけ。 AES の sbox も 256 だったと思うのだが違うのか？ 俺には tempering と sbox を同列に扱うのは理解 できないし、「みたいなもん」なんて説明には到底 同意できんから異は唱えるが、別に団子がそれで 間違ってないって思うのはどーでもいーよ。 ってか、こんな話誰もついてこねーよなw でもさー、団子も sbox 系とシフト・論理演算系を 綺麗に別けてねーかw　やっぱ別なんじゃね？w 778 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 05:11:28 ] >>770 みんなすげぇなぁ。 おいら even -1 したら、odd +3 = total +1 で意味なかったよ orz 779 名前：202 mailto:sage [2009/01/23(金) 09:21:02 ] >>778 wwwwwwwwwwwww すっげーヒントあげたいけど、その壁は自分で超えろ。 780 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 09:41:39 ] >>778 大丈夫、私もその辺で挫折した。つーか、飽きたw 781 名前：202 mailto:sage [2009/01/23(金) 09:42:23 ] >>693が、58156364 / 4 * 12.5 / 40 = 4543466 か。 この数値が出せてたら俺より速い。 >>775 の意味も判る。 現時点でこのスレだと、 優勝、準優勝候補 : >>693 , 俺 優勝候補を抜く可能性のあるヒト: >>568, >>579 だんごさんと >>579 の話にはついていけなかったんだが、 とりあえず >>579 の Prolog が導き出した解法のサイクル数が 出るまではインラインアセンブラで限界まで行った者勝ちっぽいな。 782 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 11:13:19 ] まー普通に考えても、ここに書き込んでないやつで優れた奴もいるだろ〜から 優勝候補をこのスレ内で絞るってのも無理があると思うんだけどな 783 名前：202 mailto:sage [2009/01/23(金) 11:46:04 ] >>782 もちろんその可能性は否定しない。このスレを読まないと、「命令数どこまで減らせる」という 指標がない状態でチキンレースに参加しないといけないからキツイけど、このスレをROMってるなら 命令数がどこまで減らせるか判るね。 784 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 11:59:48 ] >>781 おい、俺様を優勝・準優勝の可能性からはずすな！ いや外してもいいや。こっから先の手の内は明かすわけにはいかない とりあえずカードは残してる。 785 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 12:06:20 ] >784 だって亀田兄弟的ポジションじゃんｗ 786 名前：202 mailto:sage [2009/01/23(金) 12:08:22 ] >>784 まじかよ・・・ >>693の12.5がもう限界だと思ってた。 787 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:16:58 ] >>786 全然関係ないけどさ Oddへの置き換えなしだとEven側は18くらいかかるわけだけど、これを17に減らす方法って気づいた？ 788 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:27:55 ] mt[n] = mt[m] ^ (x >> 1) ^ (((x & 1) == 1)? 0x9908b0dfUL : 0); ↓ x = rotr(x, 1); mt[n] = mt[m] ^ x ^ ((x > 0x7FFFFFFF)? (0x1908b0dfUL) : 0); ※これを使ってもチキンレースには参加できません。課題が別モノなら有用だったかも これ問題公開されてから3日くらいで考えたネタだけど、最終的に高速化の候補としては外れた方法だから敢えて紹介しておく。 あとブロック単位じゃなくてスカラ単位で取り出す場合はこっちのほうが速いかもしれない。レイテンシ的な意味で。 789 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:44:24 ] ^ x ^ ↑このへんがむかつく 790 名前：202 mailto:sage [2009/01/23(金) 13:24:28 ] >>787 evenの命令数削減は無意識だから、どうやったら even18 になるか悩んだ。 andc ともう一つ命令を使うヤツか？ もう一つの命令で予約違反してるけど、将来のSPUで動かなくなっても 構わないと判断したよ。 791 名前：202 mailto:sage [2009/01/23(金) 13:26:21 ] andcじゃなくてselでも良いのか。 792 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 13:48:27 ] >>202 なに言ってんだ？w 793 名前：202 mailto:sage [2009/01/23(金) 13:54:00 ] いっか、トップランカーには無意味な情報だからバラしちゃえ。 spu_and( matrix_a, spu_cmpeq( spu_and( x , 1 ) , 1 ) ) ↓ spu_andc( matrix_a, spu_subx( z, z, x ) ) 794 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 13:58:00 ] コンテスト参加してんのお前らだけじゃねーぞ 少しは考えろ 795 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 14:00:30 ] ってか、202 には >>788 の答えは見えてないのか？ 796 名前：202 mailto:sage [2009/01/23(金) 14:00:57 ] >>794 悪い。調子乗りすぎた。 締め切りまで黙ってる。 797 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 14:03:11 ] >>793 そ　　ん　　な　　方　　法　　も　　あ　　っ　　た　　の　　か 第一オペランド破壊する命令はうまく考えて使わないと困るんだよね。 >>788見つけたときは俺SUGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEって思った 798 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 14:06:19 ] >>797 こんなので思うな!w 799 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 21:14:51 ] 8bit×4の水平加算とかあるけど何に使うんだコレ SSEのPSADBW/MPSADBWと同じく、動画の動き検出とかに使うんだろ？ それしか思いつかない。 悲しいことに今回の課題でも役に立たない。 如何あがいても垂直加算のほうが性能出る。 これがもしもOddで処理されるならまた使い方も違ったんだけど。 800 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 21:23:56 ] absdb/avgb/sumb あたりは動画のためだぁな。 801 名前：579 mailto:sage [2009/01/23(金) 21:43:31 ] ORIGNAL: sum=26842941, 20235458 ticks MINE: sum=26842941, 296432 ticks ORIGNAL: sum=ff298dc7, 29209150 ticks MINE: sum=ff298dc7, 416484 ticks ORIGNAL: sum=e41976b4, 21287451 ticks MINE: sum=e41976b4, 359310 ticks ORIGNAL: sum=1d20a3cf, 19895914 ticks MINE: sum=1d20a3cf, 271577 ticks ORIGNAL: sum=7ab6f153, 1012083 ticks MINE: sum=7ab6f153, 80442 ticks ORIGNAL: sum=d528faae, 14662211 ticks MINE: sum=d528faae, 226395 ticks ORIGNAL: sum=f2e9b16f, 20421921 ticks MINE: sum=f2e9b16f, 285473 ticks ORIGNAL: sum=c38c3ffb, 17745083 ticks MINE: sum=c38c3ffb, 312869 ticks ORIGNAL: sum=4a476dd4, 17155127 ticks MINE: sum=4a476dd4, 268986 ticks ORIGNAL: sum=817388cd, 412802 ticks MINE: sum=817388cd, 60522 ticks 課題アナル(仮称)間違えていたよ orz ところで、いつまでも仮称だとアナルが可愛そうなので、正式名称を ハックtheアナルに決めたよ。ついでに処理系と実装も変えたけど。 802 名前：579 mailto:sage [2009/01/23(金) 21:44:09 ] $ diff mt19937ar.sep/mt19937ar.c~ mt19937ar.sep/mt19937ar.c 52c52 < #define MATRIX_A 0x9908b0dfUL /* constant vector a */ --- > #define MATRIX_A 0x9908b0cfUL /* constant vector a */ $ uname -mrsv Linux 2.6.18-6-powerpc64 #1 SMP Fri Dec 12 23:54:31 UTC 2008 ppc64 $ cat /proc/cpuinfo processor : 0 cpu : PPC970FX, altivec supported clock : 2700.000000MHz revision : 3.1 (pvr 003c 0301) processor : 1 cpu : PPC970FX, altivec supported clock : 2700.000000MHz revision : 3.1 (pvr 003c 0301) timebase : 33333333 platform : PowerMac machine : PowerMac7,3 motherboard : PowerMac7,3 MacRISC4 Power Macintosh detected as : 336 (PowerMac G5) pmac flags : 00000000 L2 cache : 512K unified pmac-generation : NewWorld ですが、何か？ 803 名前：579 mailto:sage [2009/01/23(金) 21:45:05 ] ちなみに、実装は C99 な。本当の意味でのな。altivec も使っていない。 32bit ビットスライスｗでこの程度。端数の処理はまったく最適化していない。 SIMD 化したらもっと早くなるかなぁ（棒 >>720 >突っ込みどころのデパート。詭弁の集大成。 で、 >>729 >だからTempering前の値をいくら「加算」しても無意味なんだ。 言いたいことはそれだけ？ >>579 >tempering 前の「とある値」を集計する。GF(2)の中で。 >すると、tempering (相当の操作)は一回で済む。 誰も tempering 前の値を「そのまま」加算するとは言っていないぜ？ 加算するとも言っていない。首尾一貫してるだろ？ >>730 >彼は全然役に立たないことしか言ってない。 ｵﾏｴﾓﾅｰ >>771 そんなに俺のアナル大きい？ >>781=202 俺？優勝する可能性？ないよ。出ないしｗ 804 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 21:56:21 ] >>801 おいORIGANALが本来のターゲットより一桁以上速いぞw でも、多項式取り違えてたとはいえ、すげえ伸び率だね。 805 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:05:25 ] よくできた捏造だな でもターゲットはＰｏｗｅｒPCじゃなくて「SPU」 806 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:08:25 ] よ、よく出来てるのか？ｗ 807 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:09:26 ] > 俺？優勝する可能性？ないよ。出ないしｗ これを書くのはもうちょっとあとの方が面白かったかなｗ 808 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:09:33 ] >>805 たしかに>>732より、よくできてるのは間違いないな 809 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:11:27 ] ゲハ板で発狂してるアスペル君が勝手に勘違いしただけだろそれ 810 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:12:40 ] さすがに俺もそう思う。団子はウザイけど >>732 は無罪。 811 名前：808 mailto:sage [2009/01/23(金) 22:15:00 ] そうだったのか。団子ごめん 812 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:16:23 ] PPUとSPUが同じコードシーケンスで実行できるとかアホなこと言いやがんだもん ＰＰＵに18issueの命令帯域が必要になるぞって言ったら、十分とかいいやがるし しまいには、SSEがｘ86のフォーマットとはかけ離れてるとかｗｗｗ あの命令フォーマットがｘ86でなくてなんなんだよ 813 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:37:38 ] 大丈夫だよ。あのコピペで団子は間違ってないってみんな分かってるから。 団子が間違いを認めなくてウザい事もかなりあるがな。 あと接頭辞のように付いてくる「知り合いに誰々がいる」って下りもウザい。 知り合いが有名なだけで、別にスネ夫が偉いわけじゃないだろう。 814 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:38:02 ] 「サマリだけ求めるショートサーキット禁止」 とか胴元が慌てて言い出したら爽快だな。 つか出題者があたまわるいってことになるが。 815 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:45:01 ] 俺もそろそろトランザム（笑）発動しちゃおうかな そろそろ勘のいい人は愚直な方法がいくらばかばかしいことに気づいてるかも知れない頃だし >>814 関数抜ける前にMTの配列に書き戻しさえすれば等価な実装でもかまわないのでは？ 816 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:59:23 ] ルールを根本変更されると正直悲しい。そしてキツい。 単なるチキンレースなら降りる。 817 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 23:18:26 ] 課題見直しで延期とかになったら面白い。 MTの配列を毎回舐める必要がない前提ならトランザム（笑）可能なことは気づいてた。 それをやるとアルゴリズムが根本から変わるけど コアループ抜けてからMT配列に書き戻せばちゃんと再実行も可能。 818 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 23:32:24 ] >>734の言うとおりになったな 819 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 23:39:57 ] 俺もロジックジェネレータ改造したそろそろ走らせようかな テキトーに当たり付けたパターンを再帰で全部試す馬鹿な方法使ってるから最適に近い方法見つけるのに1ヶ月くらいかかる。 俺の試算だと 820 名前：202 mailto:sage [2009/01/24(土) 00:00:50 ] ごめん、もうプログラムは書かないから、言わせてくれ。 >>816 そもそも、課題は乱数生成を最適化しろというもので、最初からどこまでサイクル数を 減らせるかというチキンレースなんだぞ？ >>579の方法はただのチートで、ルールが「チェックサム合ってれば乱数生成しなくても良い」 ってなったらそれこそ根本的なルール変更だ。 俺はHack the Cellに参加したんだ。単なる数学コンテストなら降りる。 821 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 00:18:10 ] 様々な分野に対する知見が求められる、それだけのことじゃないか? 822 名前：202 mailto:sage [2009/01/24(土) 00:22:59 ] >>821 課題を100回読んでよ。　つ cell.fixstars.com/challenge/challenge.html どこに「乱数のチェックサムを計算してください」って書いてある？ 「課題は、メルセンヌ・ツイスタの最適化です。」 「メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。」 823 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 00:25:25 ] しかしCellって本当に早い？使ったことないけど フィクターのサイトにあるパフォーマス例と同じ処理をXeonで組んでみたら 10倍速いのできたんだが・・・ 824 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 00:29:55 ] >>693だけど なんか裏で本気出してる間にお通夜モードになっとる とりあえず12.0まではきた まだ0.3位は詰めれるかもしれない で、大会中止とかルール変更とかなったらおれはどうすればいいんだ 825 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 00:30:33 ] >>820 おちつけ > ルールが「チェックサム合ってれば乱数生成しなくても良い」 乱数なんて所詮擬似的なモノです。 mt[]の配列以外のワークメモリを別に確保して、その上で乱数生成もやる それが認められるなら高速化はいくらでもやりようがある。 CUDAの1SMあたりのレジスタ本数は32ビット×8192＝32KB 配列の要素を全部レジスタに割り当てて計算し、あとでメモリ上のmt[]に書き戻した方が効率がいい。 mt[]の配列をレジスタに割り当てて計算したらMT互換ではないのか？決してそんなことではない。 レジスタに余裕があるアーキテクチャでは、最適化の過程でそんなことは自動でやってくれる 処理系も存在する。 【というわけで】 mt[]を舐めることさえやめれば、いくらかは高速化の余地があるよ。 たとえば、コアループの内側でmt[]のいくつかレジスタに割り当ててしまって、 全部レジスタ上でこね回すとすれば、128ビット×156本のレジスタが必要になり、SPUの128本本数では足りない。 そんなことをSPUで実際やれば56本固定で食っちまう。せいぜいロード・ストア回数が減るくらいしか実用性はないし アンロールに使えるワークレジスタが実質的に減ってしまって逆に性能低下になりかねない。 そこでだ、レジスタを節約しつつ、スループットを稼げるように、データのレイアウトそのものを弄ってしまえばいいんじゃないかと。 ワークメモリはレジスタに割当て続ける必要はなく、LS上の空きにスワップしていい。 もちろん、これはさんすうやではなく、計算機屋としての理屈だ。 どこまでが王道でどこからが邪道なのか、無用な線引きを脳内で作ってしまっても「勝ち」はないわけで とりあえず中の人に明確化してもらいたいところだ。 俺はgcc43って指定してあるのにアセンブラ使用可になった時点で最早ルールなんてないもんだと思ったが。 826 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 00:33:09 ] ごめん文が微妙に抜けてた ×そんなことをSPUで実際やれば56本固定で食っちまう。 ○224要素くらいまでを割り当てるにしても、そんなことをSPUで実際やれば56本固定で食っちまう。 827 名前：202 mailto:sage [2009/01/24(土) 00:38:54 ] >>825 別に、mt[] をいじるなとは言ってないし、一部の計算をメモリ上じゃなくてレジスタ上で やるのは俺もやってる。 だが、>>579はそもそもMT擬似乱数の生成自体全くやってないように思えた。 mt[]を変形してMT擬似乱数を生成しているだけなら俺の勘違いだ。噛み付いてスマン。 828 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 00:41:37 ] ネタばらししちゃうけど13切った奴はみんな部分的に8並列とか16並列とかやってるだろ？ spu_shuffle使ってパック・アンパックしてやってるだろ？ それがアリなら何でもアリだよ。 たとえばさ、32ビットの疑似乱数の上位16ビットと下位16ビットが別々のレジスタ上に分かれてたら、乱数じゃないの？ んで、上下が分かれた状態で別々に合計値の計算してもいいよね？ それが速いかどうかは別にして（っていうかcarryの計算が増える分速くない） 829 名前：202 mailto:sage [2009/01/24(土) 00:46:45 ] >>828 ごめん、それ気づかなかったわｗｗｗｗ てか、コンテスト参加者でまだ13cycle切ってない、これから頑張る人も居るんだから、 ネタばらしは止めようぜ。 830 名前：202 mailto:sage [2009/01/24(土) 00:51:07 ] 俺は、 >>598 や >>601 でいってるとおり、まじめに genrand_int32() の戻り値を 計算した上でチェックサムをとってる。 乱数を複数のレジスタに分割するのはどうなんだろうな？ たまたま場所が離れているだけで、ビット単位では元の乱数を生成しているんだし、 別にいい気もするが、、、グレーだな。 831 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 00:58:17 ] じゃあそのグレーな方法を使わせてもらうよ。 x86で64ビット整数をどうやって扱ってるか知ってる？ 下位32ビットがeax、上位がedxだ。 整数を扱うのは2進でなくともたとえばBCDでもｲｲと思うわけ 浮動小数の仮数部で23ビットを表現してもいい。 なあに、genrand_int32()の形式で要素を抽出するAPIを別途用意すれば問題ない 832 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/24(土) 01:26:29 ] とりあえずストール地獄からの脱出に成功。 明日も出勤だけど>>824目指して頑張る。 ところで、 for (int i = 0; i < num_rand; i+=2) { sum += genrand_int32(); sum -= genrand_int32(); } とかやってみたらチート対策になったりしないのかな？かな？ 833 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 01:27:20 ] 俺はチートはしないよ 834 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 01:56:42 ] init_genrand_mine を変更するなとは書いてあるけど、 init_genrand_mine で初期化されたベクタでテストするとは 書いてないわけだが。 835 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 02:00:54 ] トランザム＝通常の3倍の性能 あとはわかるな？ 836 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 02:00:58 ] だんごいい加減ネタばれひどいだろ 13は切ってるけど、>>828の方法は使ってない あんたが天才なのは結構だけど、コンテスト終わってからにしろよ 837 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 02:04:33 ] 残念だがその方法には芽は無いようだ。 散々罵倒したけど彼には感謝しないといけない。 なあに、単純な理屈だったよ。 838 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 02:25:51 ] Hack the Cell と見せ掛けて Hack the spu-gcc43、 と思ったら Hack the MT だったでござる。 839 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 02:32:37 ] ツンデレ？ 840 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 02:34:18 ] おう 841 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 02:46:25 ] このブレイクスルーは、ある意味でCellの特性を最大限生かしたものになる。 もちろんMTの互換性・再実行性も保障できる。 つまり、アセンブラなんて最初から必要なかったんだよ。 いや、それでも詰めるには必要だけど 842 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 02:48:32 ] 実装するのと極めるのは別物だからな 843 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 03:01:18 ] いいや、最後にはSIMDerだからこそできるテクニックがものを言うと思うよ。 844 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 03:28:16 ] なんか色々台無しだね。>>321 の予想通りという事かね。 845 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 03:44:22 ] どのみち最速で無い（愚直にmt[]を舐めるだけ）の方法は近々俺の日記で公開してやろうと思っている。 Fixstarsはなんでmt[]をvec_uint4との共用体にしといてくれなかったのか？ 実はそこに答えがあったのだ。 846 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 03:49:22 ] >>845 既に気付いてる人間からしたら、滅茶苦茶迷惑なんですけど。 847 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 03:50:25 ] おいおい あんまりいらんことするな 12サイクルに到達してない人間の努力は全否定か ついでに10倍速で参加賞出さなきゃいけないFixstersの身にもなれと 848 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 03:55:15 ] >>847 10倍到達した人が多い場合は上位からってルールがあったはず どのみち優勝不可能なコードなんだから文句無いだろ？ 俺がやらなきゃどうせ上位者（BSDライセンスでソース公開）はアセンブラばっかしのコードになるんだろ？ アセンブラのコードなんて公開されてもソースの再利用性という面では意味が無いんだよ。 高速化のテクニックを、アイディアを再利用性の高い形で世に出す必要がある。 俺は俺の信念で、アセンブラ許可したFixstarsをこき下ろす 849 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 05:55:21 ] アセンブラ無しなら自分が最速で、もっとも優れたテクニックやアイディアを持ってると思ってるあたりが痛いよな…… 850 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 06:14:29 ] 新しいコードだとTempering相当処理は0.5命令/Word切った。 別のところが増えちゃってるんですけどね。 言ったろ？トランザム発動するって。 851 名前：,,・´∀｀・,,）っ-○◎● mailto:ということにしておきたい sage [2009/01/24(土) 06:48:26 ] すまん、黙っておく。 実は何も思いついてません。ﾋﾋﾋﾋﾋ 852 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 07:47:25 ] 土日でエネルギー使い果たして失速するんですね、分かります 853 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 07:53:17 ] ホント今回「も」呆れる。団子痛すぎ。 でも今回は珍しく本人が非を認めたから許す。 もっとやれ。 854 名前：557 mailto:sage [2009/01/24(土) 08:00:42 ] 本当に迷惑するから公開はやめてくれ 何故そんなことをする 855 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 08:04:54 ] じゃあ締切後に公開するよ。 どうせ提出しないコードだ。 856 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 08:22:01 ] >>848に述べられているところの必要性から公開するというなら まずはフィックスターズに直接文句言ってくれよ その後でコンテスト終了後に非アセンブラのコードを公開すればいい それによってあなたの言う「再利用性」の要求は達成されるのでは？ 確かに再利用可能なコードとアイディアの公開は必要な要素だと思うし賛同するけど 別にコンテスト中にそれを行って競技を潰さなければ達成できない目的ではないと思う 純粋に自分の信念から公開に踏み切ろうとするのならば、理解して欲しい また、そんな可能性は無いとは思うが悪意や自己顕示欲からそれを行おうとするのは止めて欲しい そんなことは分別のない子供のすることだし、恐らく貴方は子供ではないので。 857 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 08:24:13 ] >>855 あ、そうなのか。ありがとう 必死こいて>>856みたいな長文書いたのが恥ずかしい 気分を害してしまったら申し訳ないです 858 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 08:35:03 ] まあ、コンテストの上位を狙うにはどっちにしろ「役に立たない」と思うけどね。 公開予定のコードはもう開発凍結するよ。 無駄だとわかったことはやらない。 859 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 09:34:56 ] 無駄でも挑戦するのがロマンだろ? まぁ、コンテスト潰しはお勧めしない。 # 今回については、「もっとやれ」とは思わなくもないがw 860 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 10:48:45 ] まあ万人にフェアであるべきだよな 861 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 12:11:49 ] >>848 >俺がやらなきゃどうせ上位者（BSDライセンスでソース公開）はアセンブラばっかしのコードになるんだろ？ >アセンブラのコードなんて公開されてもソースの再利用性という面では意味が無いんだよ。 痛いやつだなｗ 参加者全員がソース公開の許可をしているんだから、運営側の判断で 全員のソースコードが取得可能になるとか、最速のコードの他にも十分早くて可読性の良いソースが 公開されるとかも可能性もあるだろ。 >高速化のテクニックを、アイディアを再利用性の高い形で世に出す必要がある。 これも大事だが、他の参加者が”自分で考えて”スキルを磨く事も大事なことだろ？ おまえが凄いのは認めてるやるから、人の”考える”楽しみを奪うなよ。 862 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 16:32:27 ] ＞全員のソースコードが取得可能になるとか、最速のコードの他にも十分早くて可読性の良いソースが ＞公開されるとかも可能性もあるだろ。 おめでたいこって。 ＞おまえが凄いのは認めてるやるから、人の”考える”楽しみを奪うなよ。 考える能力の低い奴に限ってそう言うよね。 充分能力があるなら、目の前にゴールへの地図があってもその過程を楽しむことができるのに。 863 名前：579 mailto:sage [2009/01/24(土) 16:44:32 ] >>838 俺は最初から Hack the MT だとおもてたよ。 真面目に乱数列を生成する方法については、IBM か SCE が最速のコードを (しかも証明つきで)持っているのではないかと思えるわけだ。CELL の設計を する際にそのくらいの検討はしているだろう。 それから、これは当てずっぽうだけれど、Folding@Home の乱数も MT では？ だとすると、SCE は広告費を掛けて最適化しているはず。勝ち目ないね。 ならば、C だけで(SIMD 使わずに)最速だしたら面白いんじゃね？ と思った。 実際問題、それを行うには「課題」をかなり曲解しないと無理なわけだが、 そこは数学屋と物理屋のスタンスの違いであるわけだ。 最初はそう思っていたけど、興味が変化したのは良くも悪くも >>628。 数学は演繹の学問。全ては真実であると証明されたことから導かれなければ ならない。という意味では、 >→「あり得ない仮定を持ち出す」これは詭弁の○○箇条にもあったな この指摘は正しい。 片や、物理は帰納の学問。全ては観測に基づく。もっともらしいと評価された 「事実」は、それを反証する観測がなされない限り「事実」であるとする。 そして時には妥協もする。物理屋は、「ありえない仮定」はよく用いる。 「仮想仕事」言葉くらいは聞いたことあるだろ？ 864 名前：579 mailto:sage [2009/01/24(土) 16:45:31 ] 数学屋と物理屋、どちらが上だ下だと論じるつもりは毛頭ないが、>>628 で 自ら「算術師」と名乗り、人を「さんすう屋」と呼ぶ「団子」に興味が移った。 「あり得ない仮定」が「あり得ない」とするのは、団子の「仮定」でしかない。 この仮定は、演繹の学問としては正しい方法ではない。 だから、>>713 でその仮定が間違えていることを証明した。それでも団子は 「机上の空論」といって譲らない。 ここで完全に興味を失った。 団子という人物を知った気になっていた。「数学屋＞さんすう屋＞＞＞算術師」 という事実が「観測された」と思っていた。 が、ここに来てどうだろう。最近の団子、俺と同じこと言っていないか？ つまり、最初から俺は団子に乗せられていたんだな。 完敗。 コードは団子同様、締め切り後に公開することにするよ。似たようなロジックで SIMD 使われたら勝てる気がしない。 ごめんな。 865 名前：579 mailto:sage [2009/01/24(土) 16:59:59 ] >>820 >メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。 mt19937ar.c は、線形合同法で生成した最初の種からしか数列生成できないだろ？ 課題としては、mt19937ar.c と同じ数列が生成できれば良い、と読める。 だって、mt[] の初期値を投入する関数削除されちゃっているんだもん。 >>834 init_genrand_mine() の内容を勝手に変更されたら、それは mt19937ar.c が 生成する(できる)乱数列じゃないよね。そんな風にルール変更されたら それこそアンフェアじゃないかい？ それから、任意の数だけ生成した乱数列の合計が計算できるということは、 任意の箇所で生成される乱数を計算できる(num_rand - 1 で計算した合計を 引き算すればよい)。つまり、「乱数列が生成できる」のと同じ意味になる。 そして、コンテストは sum を計算する速さで競う、と書いてある。 >>825 >乱数なんて所詮擬似的なモノです。 まさに。 そして、擬似乱数は「使う側」の資質も問われます。 今回は、「合計を計算するために」擬似乱数をつかった。 それだけの事だ。 >>830 ある程度真面目に計算するにしても、水平加算は最後の1回だろ？ 866 名前：579 mailto:sage [2009/01/24(土) 17:29:39 ] >>837 >残念だがその方法には芽は無いようだ。 >散々罵倒したけど彼には感謝しないといけない。 >なあに、単純な理屈だったよ。 最後に捨て台詞吐いておくよ。 俺の発言には所々「嘘」が盛り込まれている。思考の過程で 「こりゃだめだ」と行き詰ったものな。 嘘を混ぜ込むのが団子の常套手段だろ？ そこを起点として少し考えれば、団子以外のやつは気づくと 思っていた。そして、団子は気づかないだろうと思っていた。 なあに、単純な理屈だよ。 867 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 17:36:51 ] 俺は疑わしきは罰せよ、０か１かの代数ばっかし扱う畑育ちだから 数学記号とか読んでもモナー板専用の特殊文字の羅列にしか見えないわけで 最も愚かな解法で再実装してみてるが 各処理の演算コストモデルが完全に逆転してしまった。 マジでXORとシフトだけしかない世界だな 868 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 17:39:41 ] > 俺の発言には所々「嘘」が盛り込まれている。思考の過程で > 「こりゃだめだ」と行き詰ったものな。 ああまさに俺の常套手段だ 869 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 19:40:59 ] なんちゅう厨房の会話だw 870 名前：202 mailto:sage [2009/01/24(土) 19:41:14 ] 「同じ乱数列」が何を意味するのかは、Fixstarsに質問投げたから回答待ち。 >>865 >課題としては、mt19937ar.c と同じ数列が生成できれば良い、と読める。 うん、同じ乱数列を生成する速度を競ってるんだよね。 で、>>579の方法では、同じ数列を生成してるの？ 「○○すれば同じ数列が取り出せる」というんだったら、○○も加えた時間を出してね？ >ある程度真面目に計算するにしても、水平加算は最後の1回だろ？ だから？ 同じ乱数列を生成するのが課題で、課題を満たした上でチェックサムを取る順番なんて自由だろ？ 871 名前：202 mailto:sage [2009/01/24(土) 19:48:05 ] 何度も言うけど、課題は同じ乱数列の生成で、チェックサムはあくまでも同じ乱数列を 生成しているかを確認する手段に過ぎない。 デクリメンタが時間を計測する手段にしか過ぎないのと同じ。 >デクリメンタのオーバーフローを利用することは可能ですか？ >今回の出題の趣旨に反するので不可とします。 このFAQと同じ。 スタック解析してORIGINALの計算結果を探すとか、genrand_mine() を呼び出す前のデクリメンタの 値を書き換えるとか、 mt_kadai の動作に対するハックは幾つかあるけど、それが今回の課題の 回答として認められる訳ではない。 乱数生成しないでチェックサムだけ計算しようとしてるヤツは、ネットゲームでバグ技見つけて、 「バグも仕様のうち」とかぬかしてゲームを滅茶苦茶にするタイプか？ 872 名前：579 mailto:sage [2009/01/24(土) 20:05:22 ] >>870 悪いけどな。 sum が計算できることと、数列が生成できることは >>865 に書いた通り 数学的には合同なんだ。 そして、mt19937ar.c の capability はかなり限られている。 >mt19937ar.c と同じ乱数列を生成してください。 つまり、mt19937ar.c が生成できない乱数は生成する必要がない。 仮に、>>688 のような評価方法が採られたとしても、最後の seed と mti さえ保存しておけば、端数ぶんの sum をキャンセルして続きの sum を 計算すればおｋ。 もちろん、キャンセルするぶんのコストは掛かるが、num_rand >= 100000 とかいう条件を加味すれば十分にコストは回収できる。 >>>579の方法はただのチートで、ルールが「チェックサム合ってれば乱数 >生成しなくても良い」 ってなったらそれこそ根本的なルール変更だ。 俺が考えたチートは、全て課題を熟考した上でのことだ。 この段階で、mt19937ar.c の capability を変更することがあれば、それは fixtars の勝手なルール変更であって、それこそ根本的なルール変更だ。 ごめんな。団子に入れ知恵しちまったのは俺だ。 873 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:06:45 ] 優勝狙ってるならともかく、自分の好きな方法で好きに組めばいいじゃん 別に公的組織が開いてる大会ってわけじゃないから、心配なら純粋な最適化と数学的な方法の２バージョンだすとかもありじゃね？ ダメかもしれんが・・（確認は必要だな） 874 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:13:04 ] 熱くなりすぎだ 回答待てば万事解決 流石にデクリメンタを書き換えてなんとかとは同列には出来んだろう きちんと数学的に証明されたアルゴリズムを実装してるだけなんだから それはそうと11.6まではいった 俺は当分もとのアルゴリズムのままで愚直に乱数列を生成しつつ10↓を目指して頑張るぜ 875 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:14:37 ] >>871 逆に聞こう mt[]のデータレイアウトはmt19937ar.cと完全互換である必要あるか？ mt[]の配列見て思ったんだけど、こうやりたくて仕方がなかったよ。 union { 　　　vec_uint vec[N/4]; 　　　unsigned int scl[N]; } MT_Array; #define mt MT_Array.scl 結局別の方法考えたんでどうでも良くなった。 それはさておき、何がやって良くて何をやったらいけないか？その線引きって誰がやるの？ あまりに固定観念に縛られすぎてるんじゃないかと？ ＞デクリメンタのオーバーフローを利用することは可能ですか？ みたいな論外な質問だってFAQにあがってるんだし、何ができるかどうかは 聞いたらいいんじゃないの？ 自分だけの無用な追加ルールを作ってしまっても損でしかない 876 名前：202 mailto:sage [2009/01/24(土) 20:16:35 ] >>872 >sum が計算できることと、数列が生成できることは >>865 に書いた通り >数学的には合同なんだ。 数学的に等価であるから何？これは数学コンテストじゃなくて最適化コンテストだよ？ 同じ乱数列が作れるなら、実際に同じ乱数列を作って、その時間を計測して。 ただし、 >>579 はコンテストに参加しないらしいから、数学的な興味から課題とは違う解法を 見つけるのは別に問題ないよ。 でも、参加するヤツは、ちゃんと課題どおり乱数生成しようぜ。 877 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:19:26 ] 回答どうなるかね。回答する側も悩んでるんじゃね？ｗ プログラムの最適化を競う大会で、気が付いたら非常に高度な数学知識を持った人しか 上位入賞できないっていうのもなんだかなぁ 878 名前：579 mailto:sage [2009/01/24(土) 20:19:39 ] >「同じ乱数列」が何を意味するのかは、Fixstarsに質問投げたから回答待ち。 本当にごめんな。今回のは、そもそもは fixstars の「設問ミス」なんだよ。 >>865 に書いた「擬似乱数は『使う側』の資質も問われます」はそういう意味。 この段階で設問を変更するためには、センター試験同様「全員に参加賞出します」 くらいの覚悟が必要。 例えば、「ウォール街のランダムウォーク」を仮定して「株ロボ」コンテストが 行われる。しかし、乱数生成は線形合同法と宣言されている。 もちろん、みんな線形合同法をつついたチートをするわけだ。そしたら突然、 「乱数生成を MT にします」。そんな感じ。 879 名前：202 mailto:sage [2009/01/24(土) 20:24:31 ] >>874 たしかに>>579の考えた方法は、数学的に正しいらしいし、その方法を求められるのは凄いと思う。 でも、方法が凄くても凄くなくても、「同じ乱数列を生成する」という課題を満たしてない以上、 今回のコンテストの回答としては不適切だろ？ デクリメンタのオーバーフローと同列に扱って何の問題がある？ 880 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:25:11 ] 論理演算を最適化するためのブール代数学も数学の一つだよ。 「^ x ^」のアレだって数学的知識に基づくモノだけど、チートなの？ 乱数を変形状態で生成したら駄目だなんて書いてないと思うんだぜ。 その辺の融通がきかないと、閉区間内の浮動小数を正規形でダイレクトに生成するdSFMTは、乱数じゃないみたいな話になっちまう。 881 名前：579 mailto:sage [2009/01/24(土) 20:25:37 ] >>877 >プログラムの最適化を競う大会で、気が付いたら非常に高度な数学知識を持った人しか >上位入賞できないっていうのもなんだかなぁ たぶんね、 >>819 >テキトーに当たり付けたパターンを再帰で全部試す馬鹿な方法使ってるから >最適に近い方法見つけるのに1ヶ月くらいかかる。 に書いてある通り。 クラスタ計算機持っているやつが優勝する。 俺はかなり妥協した。 882 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:28:18 ] よし、Cellのクラスターをつくって勝負しよう！ 883 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:31:41 ] 【内輪話】 Twisted-GFSRのループ内で何かしら集計できるのはTempering後にMSBに相当するビット以外思い当たらなかった。 加算をXOR 1個で置き換えられるのはMSBしかないだろ？キャリーの計算とかめんどいよ。 んでもってUnslicingはTempering＋加算のサイクルに織り込んで一気にやっちまったほうがエレガントかつ速いと言う結論に達した。 SPUにはそれを高速にやるために有用な命令が存在する。 884 名前：202 mailto:sage [2009/01/24(土) 20:33:57 ] >>880 >論理演算を最適化するためのブール代数学も数学の一つだよ。 >「^ x ^」のアレだって数学的知識に基づくモノだけど、チートなの？ 「同じ乱数列を生成してください」という課題なんだから、間でどんな数学を使っても、 同じ乱数列を生成していればOKだろ。 > 乱数を変形状態で生成したら駄目だなんて書いてないと思うんだぜ。 変形の程度によるだろうけど、明らかに違うビット列になってたら、「数学的に等価だから 同じ乱数列だ」なんてのは詭弁に聞こえる。 > その辺の融通がきかないと、閉区間内の浮動小数を正規形でダイレクトに生成するdSFMTは、乱数じゃないみたいな話になっちまう。 いや、今回のコンテストとどういう関係があるのかぜんぜん意味不明なんだが？ dSFMT は同じ乱数列じゃないから、今回の課題の回答としては明らかにアウトだけど、 回答としてアウトだということと乱数であるか否かとは全く関係ない話だ。 885 名前：579 mailto:sage [2009/01/24(土) 20:35:28 ] 残念だけど、数学的に「同じ乱数列」である以上は、どうあがいても 「同じ乱数列」なんだよ。 2 進表記 32 ビットで計数しても GF(2^33) で計数しても同じであるのと一緒。 もっと分かりやすく言うと、ethernet を情報が流れるときに変調される わけだけれど、その変調によって値が変化するわけではない。計算した 乱数をレジスタに格納するとき、CMOS のキャパシタのポテンシャルに 変換されるわけだけれど、それによって値が変化するわけではない。 ついでに、極論すると MT は GF(2^19937) の「カウンタ」でしかない。 886 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:35:30 ] おっと、「unslicing」の意味がわかってる人間はここには殆どいないか 887 名前：202 mailto:sage [2009/01/24(土) 20:38:47 ] なんか、根本的にみんなと感覚が違う気がしてきたな。。。 プログラマとして、「同じ乱数列」という言葉を聴くと、「同じ (ワード|バイト|ビット) 列」という意味だと 解釈するのが当然だと思っていたんだが、数学屋は「数学的に等価」と解釈するのか？ 888 名前：579 mailto:sage [2009/01/24(土) 20:40:38 ] >>884 >明らかに違うビット列になってたら ビット列で数値を表現する方法も、数学的に考えられた一つの方法でしか ないんだよ。 889 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:41:23 ] 仮に１０００番目の乱数を取り出してといわれたときに、オリジナルと同じ値が取り出せるなら同じ乱数列ってことでいいんじゃね？ 890 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:42:41 ] Tempering＋加算が爆速になったのはいいとしてGFSRの処理のほうがめんどいことになってる。なんとかサイクルを減らせないものか ミスアラインロード・ストアがボトルネックになるのは結局同じだった。何かしら方策を考えないといけない。 >>887 BCDでも2進数でも浮動小数方式でも数値的に値を表してれば十分でないの？ データ構造なんて抽象化してナンボだよ。C++屋の考えだけど。 891 名前：202 mailto:sage [2009/01/24(土) 20:45:47 ] >>888 そんなこと100も承知で、>>887のように解釈してるんだよ。 どっちの解釈を求められていたかは、公式の回答待ちだ。 とりあえず、暗黙の了解が違いすぎるのはよく判った。 >>579 とは絶対に一緒にプログラム書きたくない。 「utf-8で文字列返して」って言ったら、平気でutf-8をbase64エンコードして返してきそうだ。 892 名前：579 mailto:sage [2009/01/24(土) 20:47:33 ] >>887 >数学屋は「数学的に等価」と解釈するのか？ 数学屋も物理屋もプログラマも、目的のためには手段は選ばないと思うのだが。 例えにするのも憚られるが、IBM は契約書に書いてある以上の仕事は絶対に しない。日本人的思考からすると、「もうこんな所と契約するか」と思う だろうし、実際、俺もそう思ったけど、実社会では契約書に穴がある方が 馬鹿。それを認めないと、今のままの日本人的思考では、これから先、 日本は衰退する一方。 >「○○すれば同じ数列が取り出せる」というんだったら、 >○○も加えた時間を出してね？ 逆に、これは意味がない。 フェルマーの最終定理が証明されたところで、それを応用できる分野は今のところ 見当たらない。しかし、それを証明する過程で得られた知見は何事にも代えがたい 大切なものである。 893 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:47:37 ] 整数型の値を期待しているところでfloatで値を渡されるもの嫌だなｗ １０．０も１０と変わらないとか言って 894 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:51:19 ] ひとつの掲示板でこうなんだから、他にも同じようなことやっているやつがいるだろう。 結局、グローバルスタンダードは、そこになるのかもね。 895 名前：202 mailto:sage [2009/01/24(土) 20:51:43 ] >>893 7進数でその数値を表した文字列を渡されるかもな。 896 名前：579 mailto:sage [2009/01/24(土) 20:51:47 ] >>891 return "utf-8"; 897 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 20:52:47 ] まあ不満もあるけども >データ構造なんて抽象化してナンボだよ。C++屋の考えだけど。 には100%同意だ 既定のインプットから既定のアウトプットを出してる以上文句は言えんとおもうね 元はと言えばfixstersが実装する関数をgenrand_int32と同じにしなかったのが問題なんだろうけどそれじゃあ速度は出ないからなぁ それに定数時間じゃない以上まだ負けると決まったわけじゃないさ 実装レベルで出来ることだっていくらでもあるんだぜ？ まだまだきついが多分10サイクルは切れる 898 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 20:53:10 ] >>893 返すのは整数型の「合計値」だろ？ MTで得られた疑似乱数値なんて今回の値では中間値でしかないじゃん。 どのみち中間値なんて公開する必要ないんだから、データ構造がどうなってるかは 当のオリジナルのMTは、得られる乱数がビッグエンディアンかリトルエンディアンかすら規定してないぜ。 899 名前：579 mailto:sage [2009/01/24(土) 21:05:16 ] >>891 > >>579 とは絶対に一緒にプログラム書きたくない。 いや、マジな話ね。 そう言ってもらえるのは嬉しくて、「じゃ、後はお前に任せた」とかいって 意気揚々とハナクソほじっていると、締日 3 日位前に泣きつかれるんだよね。 勘弁してほしいのだが。 900 名前：デフォルトの名無しさん [2009/01/24(土) 21:09:48 ] > 一緒にプログラム書きたくない。 の対象は今回のケースではfixtersの面々なんじゃないか？ FAQの"趣旨"なんて曖昧な表現で一体何がわかるってんだ． fixtersは普段からこんな表現使って仕事してんのか？ 契約書，仕様書にも厳密な記述無しで"趣旨"って書くのか？ 901 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:10:47 ] 面白くなってきたな 物事を様々な側面から捉える力ってのは大事だと思う 902 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 21:13:23 ] Cellのスケールメリット上重要な位置づけだったPS3があの惨状なのに Cellオンリーのリーディングカンパニーの時点で、どうやろなと思ってる。 決算報告書とか意味不明だし。 黒字なのか赤字なのかすら読めない。 903 名前：579 mailto:sage [2009/01/24(土) 21:14:41 ] >契約書，仕様書にも厳密な記述無しで"趣旨"って書くのか？ ネトゲには「こちらが想定したのと違う方法で...」って書いてあるんだろ？ やったことないから詳しくは知らんが。 想定なんて、後付でどうにでもなる。 そんなレベルのコンテストだとしたら、始めから出る価値ないよ。 904 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:16:26 ] >>875 おまえが捨てたやり方は全部公開ってか？ 調子乗りすぎ。 905 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:20:27 ] ,,・´∀｀・,,）っ-○◎● このＡＡ、[ ´ ｀ ]の部分と[, ・ ・ ]の部分、どっちが目なんだよ？ 前から気になってしょうがない。 あいまいな事をするなよな 906 名前：579 mailto:sage [2009/01/24(土) 21:22:30 ] 579って、「こんにゃく」って読めるよね。 907 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:23:10 ] >>902 面白そうだから決算書見てみたよ 当期純利益が34百万とあるから黒字だな しかし大雑把な決算書だな 株式会社の要件満たすため、とりあえず出してるだけといったところだ 908 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 21:23:58 ] ×リーディングカンパニー ○自称リーディングカンパニー ｘ86とかTeslaとか手広くやります、とかなら俺も心揺れた 909 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:26:52 ] >>906 こん　な　くそ　って呼んでた 910 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:27:13 ] Cellは家電やゲームのほうだと微妙だが スパコンの方だとかなり活躍しているじゃない 911 名前：579 mailto:sage [2009/01/24(土) 21:29:20 ] 906 は 579 ではありません。 アナルコンニャクより。 912 名前：579 mailto:sage [2009/01/24(土) 21:35:09 ] >>911 は俺だが、話を戻すとして。 >>877 >非常に高度な数学知識を持った人しか プログラマという人種は高度な数学的知識を持っていたらいけないの? 数学的知識のないプログラマは、ただの奴隷だよ orz 913 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:43:42 ] >>912 もちろん数学知識は必要だし、他にも英語やらいろいろ求められる。 ただ、今回のコンテストに話をしぼったときに、ｓｕｍの計算の数学的な解法にたどり着けない人に 入賞の機会すら与えられないのはどうなのって話。 まあ、参加者の半数が納得できるなら問題ないと思うけどね。 914 名前：579 mailto:sage [2009/01/24(土) 21:52:42 ] >>913 Cマガ電脳倶楽部で、どれだけ数学的知識の差に泣かされたことか。 当時中学生〜高校生。 915 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 21:57:32 ] なんだ？ 高卒が暴れてんのか？ｗ 916 名前：579 mailto:sage [2009/01/24(土) 22:05:11 ] >>915 そうだね。高校は間違いなく卒業したよ。いやガチで。 お前が末期癌で担ぎ込まれたときの主治医が俺かも知れないけどな。 917 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:15:53 ] SPUのアセンブラを自分で書くのが億劫（レジスタが多すぎて混乱しまくりんぐ）な俺が勝つには 極限られた人間しか思いつかないようなブレイクスルーが必要だったわけだが。 逆に、いつから「フォーマット」が決まった上でのアセンブラチキンレースになったんだ？ 918 名前：579 mailto:sage [2009/01/24(土) 22:16:01 ] お前が包茎手術をする時の執刀医が俺かも知れない。 が、そんなことはどうでも良い。 アイソトープを使う上で、物理屋諸君には大変お世話になった。 物理を理解する上で、数学屋諸君の知見は非常に役に立った。 シミュレーションを進める上で、松本先生(の開発されたMT)には 大変お世話になった。 その上で、今回の設問は、松本先生を馬鹿にしているようにしか 思えないわけだ。 919 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:17:38 ] たとえば、Cellのパイプラインをよく回す最適化という点では、 なにもしていない579のコードが、他のよく最適化したコードの10倍速いとなったとき、 Cellとは関係ないけど、アルゴリズムを考えた579さん優勝〜というのは、非常に変な話だ。 でも、実際に速いなら無視できない。特別賞でもなんでもいいからあげればいいかな？ 579のコードで、しかもCell特有の最適化を多少してあったら、文句ないだろうか？ 920 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:20:50 ] そんなのは中の人が判断すること。けちつけるくらいなら精進しる 921 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:26:14 ] >>919 ちなみに俺はCell特有と言ってもいい命令を駆使して再設計してるよ。 今まで全くつかってなかった命令だ。 逆に従来のやり方だとSSEでもできることしかやってない。 922 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:29:46 ] >>921 再設計するのは勝手だが、大会終わるまで古い方法はさらすなよｗ 大丈夫だと思うけど、一応な 923 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:32:07 ] >>922に一票 924 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:35:57 ] 古い方法もブレイクスルー来たんだけどね。 今やってる方法がアリならこれもありじゃんって感じで。 晒しちゃうと手の内を一部明かすことになるのでやらない。スコアも一切出さない。 ただ一ついえるのは12とか13とかとは全く意味の無い数字になってしまった。 何もかも方法が違う。 925 名前：579 mailto:sage [2009/01/24(土) 22:40:25 ] >>924 スコア明かすことは、そのまんま pmt[] のサイズを晒すことに なっちゃうんだよねｗ 926 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:42:57 ] >>925 あんま団子にエサやるなって。 めちゃくちゃ釣れやすいんだから 927 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:49:12 ] >>925 そんなものは無いから。 おもっくそ泥っ臭い方法でやってるし。それこそSIMDのパワーにものいわせた頭の悪い方法で。 配列なんてレイアウトが変わったくらいでmt[]のサイズとほとんど変わらん 敢えて言っちゃうけど、160 qword分 928 名前：579 mailto:sage [2009/01/24(土) 22:57:54 ] >>927 レイアウト変えただけで、mt[] とは等次元空間ですな。 そのやり方ができるのであれば、(演繹的には)それに越したことは ないと思います。俺は自信なかったからチートしたけど。それとて、 fixstars に文句言われる筋合いはないけどな(帰納的には)。 脱帽です。 929 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:04:02 ] 別に数学的なんちゃら考えなくてもだんごの言うくらいには命令減らせるよ データレイアウトが思いっきり変わるから和を出すときは別として 乱数列を出す時に毎回展開とかやってられんけどな 930 名前：579 mailto:sage [2009/01/24(土) 23:09:03 ] >>929 12 とか 13cycle の 1/3 まで減らせるの？ それとも、俺また釣られているの？ もう誰もちんじれない 931 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:09:22 ] 全加算じゃなきゃ馬鹿らしすぎてやっとられんわ しかしこの配列構造は大好きです 932 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:15:04 ] というか>>929には気づかれたようだ 933 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:16:06 ] 試算だとその方法でtemperingにかかるのはQWORD当たり大体0.6サイクルを切る位 残念ながらだんごよりは2〜3割遅いけどな 俺はとりあえずもとの方法で最適化を続けるけど後はFixsters次第 934 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:17:13 ] すまん ×QWORD当たり大体0.6サイクルを切る位 ○WORD当たり大体0.6サイクルを切る位 935 名前：202 mailto:sage [2009/01/24(土) 23:18:07 ] 俺も、Fixstarsの回答しだいでは両方出すかも。。。 936 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:21:52 ] >>933 GFのほうを作り込んでるけどシャッフルによるパッキングのサイクル数を抑えられないので トータルだと似たり寄ったりな性能になりそうな予感。 しかし最後の加算は美しすぎてアドレナリン出てくるぜｗｗｗｗ 937 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:30:08 ] 579の思い置き去りの展開かよw 938 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:31:34 ] 0.6は計算ミス どうやら0.5位だなぁ 殆ど同じ方法かもしれん 939 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:31:42 ] 当たり前だ。1割も理解してない。 力業 is Justice. 940 名前：202 mailto:sage [2009/01/24(土) 23:57:59 ] やべぇ、俺もチートの方実装したくなってきた。 まだ12.5cycle切ってないんだが、、、 941 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 00:00:17 ] チートじゃねぇ 【邪道】だ 942 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 00:09:26 ] うーん。 3倍はﾌｶｼでした。サーセンｗｗｗｗｗ 943 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 00:40:32 ] Fixstersから返事があるまでCell Challengeやろうぜ！ 944 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:05:59 ] 枯渇でストールするのは単なるバグなので、それを考慮してアセンブラチューン するのはあまり生産的では無いね。90nm版のCellでしか発生しないんだから。 ま、90nm版以外を身近に手にする事は将来にも無いかもしれないけどね。(ｗ 945 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:11:05 ] 散々罵って結局だんごも579の方法でやってるのか？ 946 名前：202 mailto:sage [2009/01/25(日) 01:16:06 ] >>945 ちがうよ、数学できない俺でもできる方法。 947 名前：202 mailto:sage [2009/01/25(日) 01:16:55 ] ちがうか、だんごさんは2種類やってるのか。 948 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:21:16 ] 3種類だ。 949 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:26:45 ] >>984 579のやり方は机上の空論だって言ってたのは？ 950 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:38:25 ] 950 951 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:38:31 ] 俺は都度擬似乱数の生成を行ってから加算してる。そこだけは拘る。 952 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:42:17 ] 579に謝れよ団子 953 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:47:13 ] 繰り返す 【俺は都度擬似乱数の生成を行ってから加算してる】 どんな方法にせよTempering前にサマリ求めるのがアリだとは思わないからな 954 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:51:31 ] ありとかなしとか話題すげ替えんなよ 579はオツムがよわいとか能無しだとか言ってたろ？ 机上の空論じゃなかったんだから否を認めろよ 955 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/25(日) 01:56:23 ] やっと12clockになる方法思いついた。けど、そこから先のEvenを減らす道が 見えなくて困ってる所です。やっぱりレイアウト葬らないと壁を越えられない のかなぁ…。 >>912 数学の教養が無くても、転職してから１．５週で数十万行の構造把握して、 そこからバグ率を低く保って行く位の事なら出来てますよ。 つーか、今日になって（マイルストーン一ヶ月前なのに）コアな部分の 動作変更するとか言い出す上司がいて、バグの対処諸々考えてたら頭が 回らなくなってきました。初回からコケないことを祈るしか無いですｗ 956 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:57:46 ] 本物の頭の弱い子だね。 俺の意図とは無関係に本人が煽りだと思ってないわけでそれ以上は何も言うことは無いだろう。 「カード」そのものは彼が登場する前から用意してたものだよ。 957 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:00:59 ] 否を認めろよ ってくらいだからな 958 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:05:59 ] 頭が弱いのを認めとくとして >>俺の意図とは無関係に本人が煽りだと思ってない ってどう有意味だ？いやまじめに。 959 名前：デフォルトの名無しさん [2009/01/25(日) 02:16:49 ] 次 pc11.2ch.net/test/read.cgi/tech/1232817361/l50 960 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:23:21 ] >>958 ようするに団子は本当はできるのわかってて煽ってたってことだよ。 よく恥ずかしげもなくそんな言い訳できるわ。さすが糞団子だな！ 961 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 02:40:23 ] GF(2)の解法が全然別物ということが判明したので俺も俺で思い過ごしだったということだ 962 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 09:57:55 ] 拡大体 963 名前：579 mailto:sage [2009/01/25(日) 13:19:30 ] >>949 >>952 >>954 今回は俺の負ということで、もう、ゆるして。 >>955 冬山の知識が無くても、入隊してから１．５週で一個中隊の編成把握して、 そこから致死率を低く保って行く位の事なら出来てますよ。 つーか、今日になって（三本木までもうすぐなのに）コアな部分の 編成変更するとか言い出す少佐がいて、凍死の対処諸々考えてたら頭が 回らなくなってきました。初回からコケないことを祈るしか無いですｗ いかだ作って川を下るとか言い始めるんですね。わかります。 964 名前：579 mailto:sage [2009/01/25(日) 13:24:09 ] ×三本木 ○田代元湯 965 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:23:05 ] うーむ、もはや何の話をしてるのかすら外野の俺には分からなくなってきたｗ。 966 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:25:08 ] 八甲田山死の彷徨だろ 陸軍史くらい勉強しとけよ 967 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:32:29 ] >>966 確かに、プログラマにはデスマーチの知識も必要だな。 968 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:35:35 ] ああ、そういう意味なのか、やっと分かった。 （そういう比喩を持ち出した訳は） 969 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:36:20 ] なんか、学歴厨と学歴僻み厨の争いみたいな展開だな。 正直、どっちもどっち。 数学や哲学が分からん奴は、勉強してから発言しなきゃ不毛だしただの馬鹿野郎。 頭の中の話を主として話をしてる奴は、とりあえず現実とのスリ合わせが下手な駄目人間。 970 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:50:22 ] >579 MATRIX_Aの変更が重要なん？ 971 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 19:54:16 ] MATRIX_Aの変形って意味なら>>788の方法でもやってるね。 MATRIX_AとのXORはMersenne TwisterのTwisterたる所以だ。 ビット単位の行列問題に帰着すれば、なぜMATRIX_Aなのかわかるかもしれない。 972 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 20:04:30 ] 拡大体云々はRSA暗号のクラックにも有用視されてる方法だな ちょっとモチベーション低下気味なんで文献あさってるけど面白すぎる 973 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 20:30:21 ] 早くFixstarsには答えを出して欲しいところだな 俺はどっちになっても続けるけど脱落する奴もいそうだ 974 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 22:45:03 ] >971 そうじゃなくて、579が>>801-802で書いたのはMATRIX_Aを変えたMTと、彼の方法の速度比較じゃん。 (だからsumも変わってる) オリジナルMTのsumを高速化するのは結局無理だったんじゃないの？と。 975 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 22:55:03 ] Twist抜いたMTなんてMTじゃないですわ。 MATRIX_Aはビットストリームを改変する一種のsaltとして機能してるらすぃ 余談だが「Saltを加えたDES」（2chのトリップで使われてるcrypt(3)のそれ）は差分解読がやりにくいなんて 現役の数学者が言ってたよ。 976 名前：デフォルトの名無しさん [2009/01/26(月) 17:33:50 ] ↑こいつ何者？ 977 名前：デフォルトの名無しさん mailto:sage [2009/01/26(月) 18:24:59 ] アイちゃん 978 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/26(月) 22:32:55 ] とりあえず公式見解が出るまでコーディング作業はお休み。 >>967 デスマに巻き込まれるとゆとりが無い分行動が不安定になってくるんですね。 # ４日連続勤務時間中にFPSやってる上司とか見て発狂しそうになってますｗ 979 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/26(月) 23:19:02 ] saltをとは何かを考える、 日本語でいえば「お塩学」 ファッキンライト ﾃﾝｷｭｰ 980 名前：579 mailto:sage [2009/01/27(火) 01:09:23 ] >>970 >>974 アナルに突っ込んだ行列が間違えていただけの話。 ハックtheアナルの結果でたから、再トライした結果がこれ。 ORIGNAL: sum=3c927c56, 20051002 ticks MINE: sum=3c927c56, 480600 ticks ORIGNAL: sum=2e987a4d, 28979324 ticks MINE: sum=2e987a4d, 680855 ticks ORIGNAL: sum=ef1b6aef, 21517023 ticks MINE: sum=ef1b6aef, 573675 ticks ORIGNAL: sum=eedd2516, 19761023 ticks MINE: sum=eedd2516, 446886 ticks ORIGNAL: sum=f7e967a8, 981473 ticks MINE: sum=f7e967a8, 116481 ticks ORIGNAL: sum=1f37a7db, 14592172 ticks MINE: sum=1f37a7db, 365659 ticks ORIGNAL: sum=c7d41f36, 20085705 ticks MINE: sum=c7d41f36, 465866 ticks ORIGNAL: sum=aa9d2e9f, 17899900 ticks MINE: sum=aa9d2e9f, 495607 ticks ORIGNAL: sum=8abd398a, 17074673 ticks MINE: sum=8abd398a, 434344 ticks ORIGNAL: sum=a374bd58, 415390 ticks MINE: sum=a374bd58, 86607 ticks 981 名前：579 mailto:sage [2009/01/27(火) 01:09:50 ] >>722 >ざっくりと pmt[] の最悪値を見積もり始めた頃から勝算はあった >わけだが、解析結果を見ると想像以上に小さい。 大口たたいたものの、MATRIX_A 直したら、ごらんこのザマだ。 最後の評価なんて最低合格ラインの 10 倍満たしていない。 ぶっちゃけ、46KiB の制約に収まるかも怪しい。 SIMD 化すればまだ可能性はあるかもしれないけど、俺は燃え尽きた。 団子にはかなわないよ。悔しいけどな。 982 名前：579 mailto:sage [2009/01/27(火) 01:21:13 ] >>978 上司の気持ちもわからんでもないな。 >>202 >>227 まだ若いみたいだから教えておくけど、開発の現場で 一番必要とされているスキルは何だかわかるかい？ ウンコみたいなコードを読み取るスキルでもなく、バグの少ない良質な コードを生産するスキルでもない。 正しい日本語と、寛容な気持ちだよ。 そのうちわかる日が来るさ。頼むから、俺みたいなクサレジジィには ならないでくれ。 "Der Alte wuerfelt nicht." 983 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/27(火) 01:25:37 ] ん？シミュと実機じゃTick値の意味が違うのか？？？？？？ 984 名前：579 mailto:sage [2009/01/27(火) 01:33:35 ] 先週5日間連続＋今日1日、勤務時間中にLBPやっていた俺が言うのもなんだが。 985 名前：579 mailto:sage [2009/01/27(火) 01:35:14 ] >>983 つか、PowerPC なんで。SPU への移植性なんて考えていないよｗ tb_get(get_tbだっけ?)は /usr/include/asm/time.h からかっぱらってきた。 986 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 01:47:54 ] 結果出してから大口叩けばよかったのに 987 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/27(火) 01:49:14 ] びびらせんなｗｗｗｗｗｗ 988 名前：デフォルトの名無しさん [2009/01/27(火) 07:47:08 ] 579の欺瞞によりダンゴさん始まったな 989 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 10:41:15 ] >>988 まてまて、スカラと最適化済みベクタで差の出にくい 普通の PowerPC で >>980 だとしたら、SPU じゃさらに ４倍差開くと見ていいだろ。 >>287 >>288 の通りなんじゃねーの？ 990 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 14:50:11 ] >>989 PPC970だろ？ちょっとコードの書き方変えるだけでも差は出るよ。 ループはあまり得意ではなくて、タイトな部分があればアウトオブオーダで並列実行できるから アルゴリズムレベルでたいしたことは無くてもそれだけで性能が伸びてしまうこともある。 991 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 14:53:04 ] SIMD化で性能単純4倍と考えるのも愚かだ。 ミスアラインロードの連発で性能出ないことだってある。オリジナルMTがそうであるようにね。 テーブルも16バイトアラインしたら容量オーバーかもしれないね。 992 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 17:24:41 ] そろそろ皆さんハッタリのネタが無くなって静かになっちゃいましたねｗ 993 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 17:39:59 ] 10cycを切ることはありえない 994 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 18:58:49 ] >>993 ﾆﾔﾆﾔ 995 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 19:15:53 ] >>981 ってかさぁ、１０倍満たしてないし、どうせ参加しないんだったら コードさらしてみてよ。ハッタリじゃないんだったらさｗ 996 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 19:39:44 ] 「Hack the 579コード」のはじまりです 997 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 19:43:25 ] 推測するに>>802はミスにより既約でなくなったんジャマイカ? つか64ビット整数で処理したら速くならない? 998 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 19:50:02 ] >>997 実は、PPC970は64bit ALU×2で、かつAltiVecの並列演算できるユニット少ないから ALUでやったほうが小回りが利いて速いことがある。 999 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 20:03:39 ] よっしゃ!! 8.5 cycle 切った!!! 1000 名前：1000 mailto:let's transpose! sage [2009/01/27(火) 20:04:06 ] 「Hack the ハッタリ」 第２章 -> pc11.2ch.net/test/read.cgi/tech/1232817361/l50 1001 名前：１００１ [Over 1000 Thread] このスレッドは１０００を超えました。 もう書けないので、新しいスレッドを立ててくださいです。。。

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef