ひょっとしてまじめに乱数作ってチェックサム取ってるの俺だけか？？
俺が団子さんに敵わないのもそのせい？？？

>>600
だから何なんだ？管理できるとかできないとかお前は一体何を言ってるんだ？
俺にはさっぱりわからない。

>>601
ちなみに、彼の珍理論で演算時間の短縮を図るには超次元立方体構造のレジスタや演算ユニットが必要だったりするから気にするなｗｗｗｗ

団子が天才。はい。だからもうだまれ

>>604
誰だおまえ？スピード狂オタクの分際で調子に乗るな。

MT配列は教科書通りの結果になるように都度更新してるけどtemperingをまっとうな方法でやってる自信はないな。

>>603
おいおい、GF(2) 系の演算の高速化や簡素化はコンピュータの得意分野だぞ？
今時の暗号なら当たり前の事だろ。実装した事ないのか？

だったら実装してみろよ
机上の空論はおなかいっぱい

さんすうや君は端数を処理するのにチートやらないと無理だって言ってるんだろ？
ならどのみち芽がない方法だ。

> GF(2) 系の演算の高速化や簡素化は

やってるよ。
MT[]のデータ状態に矛盾が起きない範囲でな。それが出来ないなら今回のコンテストは諦めろ。

青筋立てないで落ち着け。
どこのスレでも痛すぎる。正しい事を言っているかどうかじゃなくて。
答えて欲しい質問からは逃げるのに叩けるところはどうでもいいところまでしゃしゃり出てくる。

なんだ答えて欲しい質問って？

ゲハ厨学歴厨に何言っても手遅れ

話題変わるけど、spu-gdbってどうやって使うの？
elfspe使ってspe用のバイナリを直接実行できるんだけど、
spu-gdb mt_kadai とかやってもデバッグできない。

今までデバッグは全部コードインスペクションと、mt[]のダンプ取って
バグの箇所を推測するの2種類だけで全部やってた。

負け犬の遠吠え

>>614
SPUの実行イメージをPPEから読み出すローダーでも作れば良いのでは？

http://cell.fixstars.com/ps3linux/index.php/Libspeプログラムのデバッグ

>>612
※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
の意味について、
1. プログラム中でmt[]の内容を計算していたら良いのか、
2. 全乱数wordについてtempering後の値も計算していないといけないのか、
3. それともチェックサムだけ合ってればなんでもアリなのか、
を質問してみて、質問して回答が2だとヤバイ？

俺に聞くな。

ちなみに俺はgenrand_mineを繰り返し呼んでも安全なように設計してる。
ぶっちゃけ外側の最適化はサボってる

>>612
>>381 は本当？　>>389 == 最適化中は本当？　>>575 の捏造は本当？ｗ

鼻高々だな団子。

手元にある最新のコードよりわざと悪い結果を貼ってるのは本当。

晒す実行結果は前のバージョンだったり、わざとデチューンしたり、色々。

なんか参加賞あるし、暇だからやってみようかな

プログラム全然書けないけど
このスレ見ながら楽しくやってみよう

>>622
自分もそんな感じ。
勉強と思ってのんびりやろうぜ

>>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
に変更されている。

これが効いてくるのは、レジスタ幅ではなくむしろ並列計算だろ。

>>603
超次元立方体構造ってなんだよｗ

>>606
その教科書には、w 次 n 階の (T)GFSR も 1 階化すれば nw 次の
GFSR になって、1 階線形漸化式に帰着するとは書いてなかったかい？

>>609
>端数を処理するのにチートやらないと無理だって言ってるんだろ？
誰が無理だと言ったｗ
思いつかない＝無理なのか？

>>610
> > GF(2) 系の演算の高速化や簡素化は
>やってるよ。
MT の内側は全て GF(2) なわけだが。
それを踏まえて外側を如何に GF(2) の上に持っていくかの話だ。

>>598=202

ヒント： 外側の sum += が仮に sum ^= だとしたら？

> 同じ乱数列を生成してください。の条件に違反している
ちょｗｗｗ

だとしたら
>temperingをまっとうな方法でやってる自信はない
>MT[]のデータ状態に矛盾が起きない範囲でな。
団子道連れだな。

話を戻すと、課題(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回目の不真面目計算が解析できれば、そこから芋づる式に
求まるんじゃないかと楽観視している。

ともかく、いまは解析結果待ち。

妄想はいいから。


> ヒント： 外側の sum += が仮に sum ^= だとしたら？

→「あり得ない仮定を持ち出す」
これは詭弁の○○箇条にもあったな

まあ珍理論持ち出しても無理だから諦めろ負け犬

くだらねーコンテストなんて目じゃねーぞ。

> その教科書には、w 次 n 階の (T)GFSR も 1 階化すれば nw 次の
> GFSR になって、1 階線形漸化式に帰着するとは書いてなかったかい？

で、それはSPUの命令を使って何命令で実装できますか？

> 思いつかない＝無理なのか？

所詮お前は口だけだな。
ハッタリは何も出来ない人間のためにあるものだぞ。
どう足掻いてもお前にはできない。

>>579
数学はよくわからんのだが、
自分が優勝だと勘違いしてるやつより期待してるからがんばれ！！

ああ、ちなみに最初くらいに1ビット×128並列のビットスライス実装思いついたけど
全然速くなかったよ。

これはどれぐらい高度な数学が必要なんだ？

さんすうやの詭弁は聞いて呆れる

>>632
これ読んで何書いてあるか解る程度。そのまんまだけど。
http://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数は（ｒｙ

いや、だから、団子はやらんでいいから黙ってろやｗ

>→「あり得ない仮定を持ち出す」
物事を簡単に考えるための迂回路だ。TT800から始めてろ。

>で、それはSPUの命令を使って何命令で実装できますか？
だから解析中だって言ってるだろうが。

解析結果？出てねーよ。

課題アナル(仮称)を prolog で実装した策略ミスだ。それは認める。
vsz は順調に(?)太っていってるから、あと 2,3 日ほっといてみるか。

59ms弱だよ。

前提からしてアホだろ
MT[n]のsumをTemperingしたものと TemperingFunction(MT[n])のsumは全くの別物

んで、頭弱い子は加算命令をXORとANDに分解してソフト的に加算すればいいと思ってるだろ？
レジスタ足りる？むしろメモリ足りる？

っていうか、脳みそ足りてる？

>>634
なんとなく分かりました。高度な数学というよりも新鮮なアルゴリズムに気がつくかどうかの問題だし、素数を探すプロジェクトとなんか似てますね。

団子はうざいが、
>>637
>レジスタ足りる？むしろメモリ足りる？
>
>っていうか、脳みそ足りてる？

これは笑ってしまった。く、くやしい。

なんにせよ10000≦num_rand＜UINT_MAXだからなぁ
何十年かかる計算を数学的解析によって短縮云々なら価値はあるが
数十ms程度で終わる計算相手にスピードを競うアプローチとしては無謀を通り越して馬鹿かと
5段階の1段階目だけで既に終わってる希ガス。



それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに求めるアルゴリズムでも解明して下さいよｗｗｗ
数十年来の課題ですｗｗ

fixstars側に十分な数学の知識がある人がいて
なおかつコンテストで生み出されるコードが後々の役に立つものであってほしいと願っているのなら
素直に乱数を作って加算するのが一番速くなるような問題になっているはず、
と信じたい

>>637

頭悪いな。お前が cite した文献に書いてあるじゃん。

> MT の解像度は最大可能な解像度と比べるとかなり悪くなっている
> MT の解像度は最大可能な解像度と比べるとかなり悪くなっている
> MT の解像度は最大可能な解像度と比べるとかなり悪くなっている

> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。
> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。
> この固定されてしまった j_1,...,j_L が乱数の質を決めるのだが、これがいただけない。

負け犬は遠吠えだけは達者だな

んで、計算時間は具体的にいくらですか？
O(n)のアプローチのほうが賢明ということもありますよ。


> 1. mt[] から pmt[] への線形写像を求める。
どうせこれだけで天文学的な時間かかるんだろ？ｗ

線形写像求めるだけで天文学的なんて、どこまでお花畑なんだぜ？

熱い・・・熱いぜお前ら
いいぞもっとやれ

>>645

いや断る。俺下痢。寝る。

・メモリ210KBが使用禁止
・チャネル使用不可（メインメモリ間のDMAももちろん不可）



まあとりあえず脳内珍論はブログでやれ。

線形写像 = 実機動作、高速
解析 = 事前作業、低速

机上の空論には
「Temperingはランダムテーブルルックアップで1回の操作で行うことができますが、
4Byte×2^32 = 16GByteのメモリが必要です」
みたいなオチがつくんだよね

>>648
> 線形写像 = 実機動作、高速
> 解析 = 事前作業、低速

その「線形写像」なんだけど、46KB未満のメモリ空間で確保できるLUTで
一体なにができるのｗｗｗｗ