ああ、herumi氏のことか。

ここじゃないと思うよ。
リアルGoogle社員の人の日記（あそこのこと）見て真似を始めたらしい。
交流があるそうな。

去年ぐらいから一連のやり取りヲチしてるけど
東大院出身と京大院出身の頭脳バトルは見てて面白い。


素晴らしいじゃないか。
俺もherumi氏と戦えるなら負けても悔いはない。

＃妨害ついでにXbyakのAtom新命令対応パッチまた送りつけてやるかﾋﾋﾋ

まてよ
60倍云々って・・・俺のカキコが初出の情報かもしれない・・・ｗｗｗｗ
まああの人は俺の日記読んでるからな

んー、わからん。誰だろ？ > real google の人
&日記更新してたんね。15cycle の latency の話だけど、
6cycle なのは命令実行後 LS に反映されるまでの latency
だから、命令解釈やら register file から各演算器の latch
への転送とかの 15cycle とは別物だよー。マジ長いねw

しょっちゅうherumi氏が日記のネタにしてるじゃないの

ヒント：「yajit」

俺も初めてアセンブラ触った動機がMMXで画像処理したい！で、
へるみさんのサイトに散々お世話になった。
なんか感慨深いなー。

>>704
チーム参戦型のICFPプロコンで、個人で上位を取っちゃうあの方ですね、わかります。

今日もサボリのタミフルが、何故かおとなしいな

呼んだら出てきちまうだろ！ｗ

くそー、13 切れねぇ orz

13が増えてきてるのが凄く脅威なんだが・・・
693、俺、だんごさんが13切ってて、227と709が13か

>>640
>それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに
>求めるアルゴリズムでも解明して下さいよｗｗｗ
暗号乱数とモンテカルロ乱数は別物だと何度もいっているだろバカ

>>647
>まあとりあえず脳内珍論はブログでやれ。
ブログに書くほどの内容でもないからここに書いているわけだがｗ

>>657
>テーブルのオフセットをアドレスを求めて値をロードするのも「演算」です。
これは痛すぎるだろ。tempering も線形写像なわけだが。

>>683
>それに比べればこちとらまだ青天井みたいなもんだよ。
青天井の意味知ってる？

どうせ団子理解できないだろうから教えてやるよ。
その前に md5sum = 770e20e29056b7e5d420fc46bdc5ee6a

>>637
>んで、頭弱い子は加算命令をXORとANDに分解してソフト的に
>加算すればいいと思ってるだろ？
>レジスタ足りる？むしろメモリ足りる？
お前が挫折したからって俺と一緒にするな。

数値の表記法は n 進表記だけじゃないんだぜ？

欲しいのは 2 進表記の sum なわけだが、最終的に変換可能で
あれば途中経過の表記法は何だって構わない。交番だっていい。
問題なのは、mod 2^32 がガロア体ではないことだ。

ループの内側がガロア体で、外側がガロア体ではなかったら、
そりゃ計数するのは非効率だろう。だったら、2^33 のガロア
拡大体の上で計数してみようという発想にはならんのかい？

33 次 M 系列の生成多項式 (33, 13) を使えば、十分実用的だ。

この系で 1 を計数する方法を考えれば明らか。
外側のループが ^= になっただろ？

>>628
>→「あり得ない仮定を持ち出す」
馬鹿が。

いくらお前でも、ガロア拡大体上での計数を前提としておけば、
tempering をループの外側に出せることも少し考えればわかるだろ？

そして、最後にシンドローム計算すれば 2 進表記に戻せる。

>>631
>ああ、ちなみに最初くらいに1ビット×128並列のビットスライス
>実装思いついたけど全然速くなかったよ。
馬鹿はここで諦める。

ガロア拡大体上での計数は、ビットスライスで行った方が効率が
良いは明らか。が、mt[] の更新をビットスライスで行うのはいささか
非効率。これは、MT が "ビットスライスではない" 計算機での効率を
狙ったものなので当然といえば当然。

ビットスライスではない計算機で扱える効率的な線形写像は、
行列 [[0ii,0ij]T,[Iij,Ojj]T] (つまりビットシフト) の掛け算と
要素どうしの掛け算(AND)と足し算(XOR)、その組み合わせだ。

それに対して、ビットスライスで扱いやすい線形写像の条件は、
行列中に "1" の出現頻度が少ないもの。至極当然。

ならば、最初に mt[] を別の空間に写像しておいて、その空間で
更新行列の "1" が少なくなるように設計すればいくらでも
(それこそ青天井に)効率は改善される。

しかし、これだけだとビットスライスを用いる根拠としてはまだ
少し弱い。それは、mt[] のサイズがレジスタ数と比較して大きい
(load, store をスケジュールするのが大変)のと、"1" の割合を
減らせたとしても行列自体が大きいので、必然的に計算量は多いまま。

そこで、mt[] 自体を小さくすることを考えよう。

が、残念なことに MT は mt[](19968 bit)のうち、19937 bit が
直交していることが理論的に証明されている。

さて、どうしよう？

>>640
>なんにせよ10000≦num_rand＜UINT_MAXだからなぁ
答え書いてあるじゃないかーい。INT_MAX だけどな。

つまり、32bit の seed から始まる 31bit の空間は、19937bit の
空間の中で、非常に小さな部分空間でしかない。

その小さな部分空間では、19937bit の大部分が直交していない。
直交していないビットは、それこそ計算する必要はない。

課題アナル(仮称)の正体は、直交していないビットを探索するものに
他ならない。

だンゴサんの括約で棺桶スレが成立したな

>>579
なんでこんな大事なことばらしちゃうの？ｗ

一応、みんな判ってると思うが、Hack the Cell の課題が何か確認しておく。

http://cell.fixstars.com/challenge/challenge.html
課題は、メルセンヌ・ツイスタの最適化です。

注意事項
※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。

芽のない方法を芽がないと割り切る能力が欠落した人間の遠吠えはむなしいのう

>>717
机上の空論だよ

突っ込みどころのデパート。詭弁の集大成。

まったくもって今回の課題の解法として役に立たない。

>>710
あれ？202 も 13 切ってたの？ >>598-599 のやり取り見て、
まだ切ってないと思ってたよｗ
>>720
自分も >>599 が当てはまるとやばいんじゃないの？ｗ

連続投稿引っかかったｗｗ

最後に、端数をどうするかだ。

その前に、報告しておく。俺のアナルはもう検算フェーズに入ったぜ？
ざっくりと pmt[] の最悪値を見積もり始めた頃から勝算はあった
わけだが、解析結果を見ると想像以上に小さい。

これが何を意味するかわかるな？

第一に、mt[](pmt[]) の更新はほぼ O(rn^2) のコストであること。
r は線形写像行列に含まれる "1" の割合。n は行列のサイズ。

第二に、pmt[] から計数ベクトルへの写像行列を N-1 種類まるまる
用意してもメモリサイズ的に余裕ができたこと。

いまからマネしようとしても、解析の方法なんて想像もつかないだろ？
お前はご自慢の 59ms アナルでおとなしく全数探索でもしていろｗ

さーて、そろそろ実装でも始めますかｗｗｗ

>>721
単純にMTの式をMTを32ビット×4並列化したものではないということだよ。
配列状態とサマリの値が等価になる範囲で高速化出来る方法は全て駆使してる。

もうやることは終わってさじ加減次第かな。
部分的にスカスカな部分があったりするのでループ全体を見て命令数が減るようにバランス調整が必要だ。

>>719
自分に自信がないやつほど声がでかいってのは本当だったんだな。

>もうやることは終わってさじ加減次第かな。
青天井じゃなかったのかよ

>>722
机上の空論は結果を出してから言うことだ

>>724←これとかな

>>579
アンタ、糞団子と接するのは初めてかい?
まあ力抜いてアナル(r

だんごも>>579もすごいぜ
少なくとも議論の台に乗れるんだから
俺も工学系だから少なくとも理系ではあるんだが何を言ってるのか全くわからんｗ

とりあえずサイクルの話はあんまりしない方がいいとおもた
サイクルの話見ただけでどこの最適化やっててどこの最適化やってないか想像できるし

負け犬579をアボーンリストに追加しとけばいい
彼は全然役に立たないことしか言ってない。

まあ見えない敵と戦ってる馬鹿だから相手にするな

>>717
どうせ団子理解できないだろ？

>>718
>※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ
>乱数列を生成してください。

何をもって「同じ」とするか、だ。

tempering 前の数値も tempering 後の数値も、表記法が
異なるだけで、同じ数値なわけだ。tempering した方が
モンテカルロに用いる上では好都合な事が多いので
しているだけ。

>3. それともチェックサムだけ合ってればなんでもアリなのか、
>1. プログラム中でmt[]の内容を計算していたら良いのか、
>2. 全乱数wordについてtempering後の値も計算していないといけないのか、

これが 2 だったら、出題者が問題の意図理解していないよ orz
1 の判断は微妙だが、仮に 1 だとするとできる事は限られてくる、
つまりそんなコンテ誰が出ても結果は一緒。ツマンネ。

ハイ　おさらい。
http://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って

>>721
>>689は超えたよ。
結構苦労してアセンブラ書いたしね。

>>721(=>>693?)もだんごさんも、tempering後の値をまじめに計算して
add を繰り返してる訳じゃないのか・・・
とりあえず、チェックサムだけ合ってればOKなのか訊いてみて、
OKならまただんごさん超えに挑戦してみるよ。

>>728
アナルの力抜いておくよ。

>>730
ｶﾞｸﾌﾞﾙしている姿が見えて楽しいよｗ

693だけどtemperingは毎回やってる
というか処理の7割がtempering
泣きそう

話の腰をもんで悪いんだが
temperingってなんだ？

揉むな!ｗ

勘で出てきた乱数を32bit空間で偏りが無い様に再マッピングしてるんだと勝手に思ってた

マージャン用語です

テンパイ ＝【聴牌】
麻雀で、あと一枚必要な牌がくればあがることのできる状態。

これが、転じて何か事を成し遂げようとしたときの最終段階、、待ちの状態になったときに使うケースがあります。


てんぱる、てんぱってる。

スタンばる（スタンバイする）、、などと同じ和製語ですね。

さてさて。

一日静かだと思っていた矢先、団子登場。団子はよっほど俺の
アナルが好きなんだなｗ　頼むから寝込み襲ってくるなよ。

この手の作戦だと実装を後回しにした方が効率いいわけだが、
結果出せ出せウルセーやつがいるから、俺はそろそろ実装始める
ことにするよ。

その前にクソして寝る。

>>739
そうだったのか…
勘とはいえすごい的外れな嘘を教えてしまった
ごめんよ>>736

おおざっぱに、MTで乱数生成の為に行うアルゴリズムでビットシフトを行う操作のことだな
tempering

>>729
暗号論の世界にも差分解読法なんてのがあって、ビットの並びの特徴から演算をショートカットする
方法に関しては俺自身もいろいろ試したことがあってね。
んで、今回はそういうショートカットは全くもって役に立たない。

MTのTemperingはフェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。
RISCオペレーションで10命令程度のビット論理演算で構成できるとはいえ、
けっこううまい具合にビットがばらけるように考えてある。

加算ってさ、簡易的にはXORとANDの組み合わせで作れるわけだけど、
キャリーアップ先は、1ビット隣じゃん。
Tempering前と後じゃその1ビット隣すら全然別物になっちゃうんだよね。
だからTempering前の値をいくら「加算」しても無意味なんだ。

Temperingは少ない命令数ながら、うまく考えてあると思うよ。

暗号の実装の話になるけど、AltiVecのVPERMやSPUのSHUFBはAESのS-Boxを16並列で処理する
ことができるけど、SSEだと同様のシャッフル命令であるpshufb命令なんかを使うより別の方法のほうが速い。
今回の課題はそう言う観点で何が最適なアルゴリズムかを考えられる人でないと難しいと思う。

> フェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。
ち・が・う

>>739
(y << 15)んとこが16だったらアレしてこうして・・・とか思ったけど
なかなかうまくいかないもんだね

>>744
あらゆるフェイステイル型暗号のS-boxはビット論理演算の組み合わせだけで実装できるの知ってる？

お得意の bitslice か？　それと s-box の意義は全然別物だぞ？

フェイステイル型暗号におけるS-boxの役割は、簡単に言うと前後のビットの並びの相関性を破壊するための仕組み。
MTのTemperingも、Temperingを省いて合計値を計算しようとしても出来ないようにする程度には相関性を破壊できてる。

そりゃ、暗号も擬似乱数も拡散って意味ではなんだって拡散だし、
ほとんどが論理演算の組み合わせで実装できるだろうよ。
その程度の意味で、feistel の s-box と同じって言ったのか？

Tempering＝「調律」
スイーツ（笑）用語でいうとチョコレートコーティングの表面を滑らかにするための行程。

もちろん、そのまんまの意味で解釈しても意味はない。
ビットの並びの相関性をある程度破壊することに意味がある。
MTにおいては、相関を破壊することが、ビットの出現確率の均一化（Tempering）になる。


S-BoxのSはsubstitution
ようするにテーブルルックアップなわけだが。

たしかにTemperingとS-boxは別の単語だが、言葉をそのまま捉えても意味はない。
本質を理解しないといけない。

テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では
ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。
だから本質的に同じだって言ったんだよ。