- 1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ]
- 前スレ
Cellプログラミングしちゃいなよ2
pc11.2ch.net/test/read.cgi/tech/1183091522/
- 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 ]
- だンゴサんの括約で棺桶スレが成立したな
|
 |
