- 1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ]
- 前スレ
Cellプログラミングしちゃいなよ2
pc11.2ch.net/test/read.cgi/tech/1183091522/
- 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 ]
- そんなのは中の人が判断すること。けちつけるくらいなら精進しる
|
 |
