すまん、黙っておく。
実は何も思いついてません。ﾋﾋﾋﾋﾋ

土日でエネルギー使い果たして失速するんですね、分かります

ホント今回「も」呆れる。団子痛すぎ。
でも今回は珍しく本人が非を認めたから許す。
もっとやれ。

本当に迷惑するから公開はやめてくれ
何故そんなことをする

じゃあ締切後に公開するよ。
どうせ提出しないコードだ。

>>848に述べられているところの必要性から公開するというなら
まずはフィックスターズに直接文句言ってくれよ
その後でコンテスト終了後に非アセンブラのコードを公開すればいい
それによってあなたの言う「再利用性」の要求は達成されるのでは？

確かに再利用可能なコードとアイディアの公開は必要な要素だと思うし賛同するけど
別にコンテスト中にそれを行って競技を潰さなければ達成できない目的ではないと思う
純粋に自分の信念から公開に踏み切ろうとするのならば、理解して欲しい
また、そんな可能性は無いとは思うが悪意や自己顕示欲からそれを行おうとするのは止めて欲しい
そんなことは分別のない子供のすることだし、恐らく貴方は子供ではないので。

>>855
あ、そうなのか。ありがとう
必死こいて>>856みたいな長文書いたのが恥ずかしい
気分を害してしまったら申し訳ないです

まあ、コンテストの上位を狙うにはどっちにしろ「役に立たない」と思うけどね。
公開予定のコードはもう開発凍結するよ。

無駄だとわかったことはやらない。

無駄でも挑戦するのがロマンだろ?
まぁ、コンテスト潰しはお勧めしない。
# 今回については、「もっとやれ」とは思わなくもないがw

まあ万人にフェアであるべきだよな

>>848
>俺がやらなきゃどうせ上位者（BSDライセンスでソース公開）はアセンブラばっかしのコードになるんだろ？
>アセンブラのコードなんて公開されてもソースの再利用性という面では意味が無いんだよ。

痛いやつだなｗ
参加者全員がソース公開の許可をしているんだから、運営側の判断で
全員のソースコードが取得可能になるとか、最速のコードの他にも十分早くて可読性の良いソースが
公開されるとかも可能性もあるだろ。

>高速化のテクニックを、アイディアを再利用性の高い形で世に出す必要がある。
これも大事だが、他の参加者が”自分で考えて”スキルを磨く事も大事なことだろ？

おまえが凄いのは認めてるやるから、人の”考える”楽しみを奪うなよ。

＞全員のソースコードが取得可能になるとか、最速のコードの他にも十分早くて可読性の良いソースが
＞公開されるとかも可能性もあるだろ。
おめでたいこって。

＞おまえが凄いのは認めてるやるから、人の”考える”楽しみを奪うなよ。
考える能力の低い奴に限ってそう言うよね。
充分能力があるなら、目の前にゴールへの地図があってもその過程を楽しむことができるのに。

>>838
俺は最初から Hack the MT だとおもてたよ。

真面目に乱数列を生成する方法については、IBM か SCE が最速のコードを
(しかも証明つきで)持っているのではないかと思えるわけだ。CELL の設計を
する際にそのくらいの検討はしているだろう。

それから、これは当てずっぽうだけれど、Folding@Home の乱数も MT では？
だとすると、SCE は広告費を掛けて最適化しているはず。勝ち目ないね。

ならば、C だけで(SIMD 使わずに)最速だしたら面白いんじゃね？ と思った。
実際問題、それを行うには「課題」をかなり曲解しないと無理なわけだが、
そこは数学屋と物理屋のスタンスの違いであるわけだ。

最初はそう思っていたけど、興味が変化したのは良くも悪くも >>628。

数学は演繹の学問。全ては真実であると証明されたことから導かれなければ
ならない。という意味では、
>→「あり得ない仮定を持ち出す」これは詭弁の○○箇条にもあったな
この指摘は正しい。

片や、物理は帰納の学問。全ては観測に基づく。もっともらしいと評価された
「事実」は、それを反証する観測がなされない限り「事実」であるとする。
そして時には妥協もする。物理屋は、「ありえない仮定」はよく用いる。
「仮想仕事」言葉くらいは聞いたことあるだろ？

数学屋と物理屋、どちらが上だ下だと論じるつもりは毛頭ないが、>>628 で
自ら「算術師」と名乗り、人を「さんすう屋」と呼ぶ「団子」に興味が移った。

「あり得ない仮定」が「あり得ない」とするのは、団子の「仮定」でしかない。
この仮定は、演繹の学問としては正しい方法ではない。

だから、>>713 でその仮定が間違えていることを証明した。それでも団子は
「机上の空論」といって譲らない。

ここで完全に興味を失った。

団子という人物を知った気になっていた。「数学屋＞さんすう屋＞＞＞算術師」
という事実が「観測された」と思っていた。

が、ここに来てどうだろう。最近の団子、俺と同じこと言っていないか？
つまり、最初から俺は団子に乗せられていたんだな。

完敗。

コードは団子同様、締め切り後に公開することにするよ。似たようなロジックで
SIMD 使われたら勝てる気がしない。

ごめんな。

>>820
>メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
mt19937ar.c は、線形合同法で生成した最初の種からしか数列生成できないだろ？
課題としては、mt19937ar.c と同じ数列が生成できれば良い、と読める。
だって、mt[] の初期値を投入する関数削除されちゃっているんだもん。

>>834
init_genrand_mine() の内容を勝手に変更されたら、それは mt19937ar.c が
生成する(できる)乱数列じゃないよね。そんな風にルール変更されたら
それこそアンフェアじゃないかい？

それから、任意の数だけ生成した乱数列の合計が計算できるということは、
任意の箇所で生成される乱数を計算できる(num_rand - 1 で計算した合計を
引き算すればよい)。つまり、「乱数列が生成できる」のと同じ意味になる。

そして、コンテストは sum を計算する速さで競う、と書いてある。

>>825
>乱数なんて所詮擬似的なモノです。
まさに。

そして、擬似乱数は「使う側」の資質も問われます。
今回は、「合計を計算するために」擬似乱数をつかった。
それだけの事だ。

>>830
ある程度真面目に計算するにしても、水平加算は最後の1回だろ？

>>837
>残念だがその方法には芽は無いようだ。
>散々罵倒したけど彼には感謝しないといけない。
>なあに、単純な理屈だったよ。

最後に捨て台詞吐いておくよ。

俺の発言には所々「嘘」が盛り込まれている。思考の過程で
「こりゃだめだ」と行き詰ったものな。

嘘を混ぜ込むのが団子の常套手段だろ？

そこを起点として少し考えれば、団子以外のやつは気づくと
思っていた。そして、団子は気づかないだろうと思っていた。

なあに、単純な理屈だよ。

俺は疑わしきは罰せよ、０か１かの代数ばっかし扱う畑育ちだから
数学記号とか読んでもモナー板専用の特殊文字の羅列にしか見えないわけで
最も愚かな解法で再実装してみてるが

各処理の演算コストモデルが完全に逆転してしまった。
マジでXORとシフトだけしかない世界だな

> 俺の発言には所々「嘘」が盛り込まれている。思考の過程で
> 「こりゃだめだ」と行き詰ったものな。
ああまさに俺の常套手段だ

なんちゅう厨房の会話だw

「同じ乱数列」が何を意味するのかは、Fixstarsに質問投げたから回答待ち。

>>865
>課題としては、mt19937ar.c と同じ数列が生成できれば良い、と読める。
うん、同じ乱数列を生成する速度を競ってるんだよね。
で、>>579の方法では、同じ数列を生成してるの？
「○○すれば同じ数列が取り出せる」というんだったら、○○も加えた時間を出してね？

>ある程度真面目に計算するにしても、水平加算は最後の1回だろ？
だから？
同じ乱数列を生成するのが課題で、課題を満たした上でチェックサムを取る順番なんて自由だろ？

何度も言うけど、課題は同じ乱数列の生成で、チェックサムはあくまでも同じ乱数列を
生成しているかを確認する手段に過ぎない。
デクリメンタが時間を計測する手段にしか過ぎないのと同じ。

>デクリメンタのオーバーフローを利用することは可能ですか？
>今回の出題の趣旨に反するので不可とします。

このFAQと同じ。
スタック解析してORIGINALの計算結果を探すとか、genrand_mine() を呼び出す前のデクリメンタの
値を書き換えるとか、 mt_kadai の動作に対するハックは幾つかあるけど、それが今回の課題の
回答として認められる訳ではない。

乱数生成しないでチェックサムだけ計算しようとしてるヤツは、ネットゲームでバグ技見つけて、
「バグも仕様のうち」とかぬかしてゲームを滅茶苦茶にするタイプか？

>>870
悪いけどな。

sum が計算できることと、数列が生成できることは >>865 に書いた通り
数学的には合同なんだ。

そして、mt19937ar.c の capability はかなり限られている。

>mt19937ar.c と同じ乱数列を生成してください。
つまり、mt19937ar.c が生成できない乱数は生成する必要がない。

仮に、>>688 のような評価方法が採られたとしても、最後の seed と mti
さえ保存しておけば、端数ぶんの sum をキャンセルして続きの sum を
計算すればおｋ。

もちろん、キャンセルするぶんのコストは掛かるが、num_rand >= 100000
とかいう条件を加味すれば十分にコストは回収できる。

>>>579の方法はただのチートで、ルールが「チェックサム合ってれば乱数
>生成しなくても良い」 ってなったらそれこそ根本的なルール変更だ。

俺が考えたチートは、全て課題を熟考した上でのことだ。

この段階で、mt19937ar.c の capability を変更することがあれば、それは
fixtars の勝手なルール変更であって、それこそ根本的なルール変更だ。

ごめんな。団子に入れ知恵しちまったのは俺だ。

優勝狙ってるならともかく、自分の好きな方法で好きに組めばいいじゃん

別に公的組織が開いてる大会ってわけじゃないから、心配なら純粋な最適化と数学的な方法の２バージョンだすとかもありじゃね？
ダメかもしれんが・・（確認は必要だな）

熱くなりすぎだ
回答待てば万事解決
流石にデクリメンタを書き換えてなんとかとは同列には出来んだろう
きちんと数学的に証明されたアルゴリズムを実装してるだけなんだから

それはそうと11.6まではいった
俺は当分もとのアルゴリズムのままで愚直に乱数列を生成しつつ10↓を目指して頑張るぜ

>>871
逆に聞こう
mt[]のデータレイアウトはmt19937ar.cと完全互換である必要あるか？

mt[]の配列見て思ったんだけど、こうやりたくて仕方がなかったよ。

union {
　　　vec_uint vec[N/4];
　　　unsigned int scl[N];
} MT_Array;

#define mt MT_Array.scl

結局別の方法考えたんでどうでも良くなった。
それはさておき、何がやって良くて何をやったらいけないか？その線引きって誰がやるの？
あまりに固定観念に縛られすぎてるんじゃないかと？

＞デクリメンタのオーバーフローを利用することは可能ですか？

みたいな論外な質問だってFAQにあがってるんだし、何ができるかどうかは
聞いたらいいんじゃないの？
自分だけの無用な追加ルールを作ってしまっても損でしかない

>>872
>sum が計算できることと、数列が生成できることは >>865 に書いた通り
>数学的には合同なんだ。
数学的に等価であるから何？これは数学コンテストじゃなくて最適化コンテストだよ？
同じ乱数列が作れるなら、実際に同じ乱数列を作って、その時間を計測して。

ただし、 >>579 はコンテストに参加しないらしいから、数学的な興味から課題とは違う解法を
見つけるのは別に問題ないよ。

でも、参加するヤツは、ちゃんと課題どおり乱数生成しようぜ。

回答どうなるかね。回答する側も悩んでるんじゃね？ｗ

プログラムの最適化を競う大会で、気が付いたら非常に高度な数学知識を持った人しか
上位入賞できないっていうのもなんだかなぁ

>「同じ乱数列」が何を意味するのかは、Fixstarsに質問投げたから回答待ち。

本当にごめんな。今回のは、そもそもは fixstars の「設問ミス」なんだよ。
>>865 に書いた「擬似乱数は『使う側』の資質も問われます」はそういう意味。

この段階で設問を変更するためには、センター試験同様「全員に参加賞出します」
くらいの覚悟が必要。

例えば、「ウォール街のランダムウォーク」を仮定して「株ロボ」コンテストが
行われる。しかし、乱数生成は線形合同法と宣言されている。

もちろん、みんな線形合同法をつついたチートをするわけだ。そしたら突然、
「乱数生成を MT にします」。そんな感じ。

>>874
たしかに>>579の考えた方法は、数学的に正しいらしいし、その方法を求められるのは凄いと思う。

でも、方法が凄くても凄くなくても、「同じ乱数列を生成する」という課題を満たしてない以上、
今回のコンテストの回答としては不適切だろ？
デクリメンタのオーバーフローと同列に扱って何の問題がある？

論理演算を最適化するためのブール代数学も数学の一つだよ。
「^ x ^」のアレだって数学的知識に基づくモノだけど、チートなの？

乱数を変形状態で生成したら駄目だなんて書いてないと思うんだぜ。
その辺の融通がきかないと、閉区間内の浮動小数を正規形でダイレクトに生成するdSFMTは、乱数じゃないみたいな話になっちまう。

>>877
>プログラムの最適化を競う大会で、気が付いたら非常に高度な数学知識を持った人しか
>上位入賞できないっていうのもなんだかなぁ

たぶんね、
>>819
>テキトーに当たり付けたパターンを再帰で全部試す馬鹿な方法使ってるから
>最適に近い方法見つけるのに1ヶ月くらいかかる。
に書いてある通り。

クラスタ計算機持っているやつが優勝する。
俺はかなり妥協した。

よし、Cellのクラスターをつくって勝負しよう！

【内輪話】
Twisted-GFSRのループ内で何かしら集計できるのはTempering後にMSBに相当するビット以外思い当たらなかった。
加算をXOR 1個で置き換えられるのはMSBしかないだろ？キャリーの計算とかめんどいよ。

んでもってUnslicingはTempering＋加算のサイクルに織り込んで一気にやっちまったほうがエレガントかつ速いと言う結論に達した。
SPUにはそれを高速にやるために有用な命令が存在する。

>>880
>論理演算を最適化するためのブール代数学も数学の一つだよ。
>「^ x ^」のアレだって数学的知識に基づくモノだけど、チートなの？

「同じ乱数列を生成してください」という課題なんだから、間でどんな数学を使っても、
同じ乱数列を生成していればOKだろ。

> 乱数を変形状態で生成したら駄目だなんて書いてないと思うんだぜ。
変形の程度によるだろうけど、明らかに違うビット列になってたら、「数学的に等価だから
同じ乱数列だ」なんてのは詭弁に聞こえる。

> その辺の融通がきかないと、閉区間内の浮動小数を正規形でダイレクトに生成するdSFMTは、乱数じゃないみたいな話になっちまう。
いや、今回のコンテストとどういう関係があるのかぜんぜん意味不明なんだが？
dSFMT は同じ乱数列じゃないから、今回の課題の回答としては明らかにアウトだけど、
回答としてアウトだということと乱数であるか否かとは全く関係ない話だ。

残念だけど、数学的に「同じ乱数列」である以上は、どうあがいても
「同じ乱数列」なんだよ。

2 進表記 32 ビットで計数しても GF(2^33) で計数しても同じであるのと一緒。

もっと分かりやすく言うと、ethernet を情報が流れるときに変調される
わけだけれど、その変調によって値が変化するわけではない。計算した
乱数をレジスタに格納するとき、CMOS のキャパシタのポテンシャルに
変換されるわけだけれど、それによって値が変化するわけではない。

ついでに、極論すると MT は GF(2^19937) の「カウンタ」でしかない。

おっと、「unslicing」の意味がわかってる人間はここには殆どいないか

なんか、根本的にみんなと感覚が違う気がしてきたな。。。

プログラマとして、「同じ乱数列」という言葉を聴くと、「同じ (ワード|バイト|ビット) 列」という意味だと
解釈するのが当然だと思っていたんだが、数学屋は「数学的に等価」と解釈するのか？

>>884
>明らかに違うビット列になってたら

ビット列で数値を表現する方法も、数学的に考えられた一つの方法でしか
ないんだよ。

仮に１０００番目の乱数を取り出してといわれたときに、オリジナルと同じ値が取り出せるなら同じ乱数列ってことでいいんじゃね？

Tempering＋加算が爆速になったのはいいとしてGFSRの処理のほうがめんどいことになってる。なんとかサイクルを減らせないものか
ミスアラインロード・ストアがボトルネックになるのは結局同じだった。何かしら方策を考えないといけない。


>>887
BCDでも2進数でも浮動小数方式でも数値的に値を表してれば十分でないの？
データ構造なんて抽象化してナンボだよ。C++屋の考えだけど。

>>888
そんなこと100も承知で、>>887のように解釈してるんだよ。
どっちの解釈を求められていたかは、公式の回答待ちだ。


とりあえず、暗黙の了解が違いすぎるのはよく判った。
>>579 とは絶対に一緒にプログラム書きたくない。
「utf-8で文字列返して」って言ったら、平気でutf-8をbase64エンコードして返してきそうだ。

>>887
>数学屋は「数学的に等価」と解釈するのか？
数学屋も物理屋もプログラマも、目的のためには手段は選ばないと思うのだが。

例えにするのも憚られるが、IBM は契約書に書いてある以上の仕事は絶対に
しない。日本人的思考からすると、「もうこんな所と契約するか」と思う
だろうし、実際、俺もそう思ったけど、実社会では契約書に穴がある方が
馬鹿。それを認めないと、今のままの日本人的思考では、これから先、
日本は衰退する一方。

>「○○すれば同じ数列が取り出せる」というんだったら、
>○○も加えた時間を出してね？

逆に、これは意味がない。

フェルマーの最終定理が証明されたところで、それを応用できる分野は今のところ
見当たらない。しかし、それを証明する過程で得られた知見は何事にも代えがたい
大切なものである。

整数型の値を期待しているところでfloatで値を渡されるもの嫌だなｗ
１０．０も１０と変わらないとか言って

ひとつの掲示板でこうなんだから、他にも同じようなことやっているやつがいるだろう。
結局、グローバルスタンダードは、そこになるのかもね。

>>893
7進数でその数値を表した文字列を渡されるかもな。

>>891

return "utf-8";

まあ不満もあるけども
>データ構造なんて抽象化してナンボだよ。C++屋の考えだけど。
には100%同意だ
既定のインプットから既定のアウトプットを出してる以上文句は言えんとおもうね
元はと言えばfixstersが実装する関数をgenrand_int32と同じにしなかったのが問題なんだろうけどそれじゃあ速度は出ないからなぁ
それに定数時間じゃない以上まだ負けると決まったわけじゃないさ
実装レベルで出来ることだっていくらでもあるんだぜ？
まだまだきついが多分10サイクルは切れる

>>893
返すのは整数型の「合計値」だろ？

MTで得られた疑似乱数値なんて今回の値では中間値でしかないじゃん。
どのみち中間値なんて公開する必要ないんだから、データ構造がどうなってるかは

当のオリジナルのMTは、得られる乱数がビッグエンディアンかリトルエンディアンかすら規定してないぜ。

>>891
> >>579 とは絶対に一緒にプログラム書きたくない。

いや、マジな話ね。

そう言ってもらえるのは嬉しくて、「じゃ、後はお前に任せた」とかいって
意気揚々とハナクソほじっていると、締日 3 日位前に泣きつかれるんだよね。
勘弁してほしいのだが。

> 一緒にプログラム書きたくない。
の対象は今回のケースではfixtersの面々なんじゃないか？
FAQの"趣旨"なんて曖昧な表現で一体何がわかるってんだ．
fixtersは普段からこんな表現使って仕事してんのか？
契約書，仕様書にも厳密な記述無しで"趣旨"って書くのか？