cellプログラミングしちゃいなよ3

1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ] 前スレ Cellプログラミングしちゃいなよ2 pc11.2ch.net/test/read.cgi/tech/1183091522/ 751 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:07:52 ] >テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では >ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。 へー、すごいなｗ。いや、LUT を使わない実装が標準とか思わないほうがいいぞ？ 暗号作ってる方は簡単なシフト＋ビット論理演算で求められないように sbox を 導入してるのに、なんか可哀想になってきちゃうよ。 まぁ確かに本質的には両方拡散だから同じだしなｗ 752 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:30:18 ] >>751 RSAのRivest Cipher(RC)シリーズとかMD5なんてS-boxを使わずにスワップを繰り返す 暗号・ハッシュアルゴリズムの代表格なわけだが？ RC6はAESの最終候補まで残ったぞ。 753 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:36:19 ] なんで軒並み落ちてって、今 feistel ばっかなのか考えようぜｗ 754 名前：デフォルトの名無しさん [2009/01/22(木) 23:37:45 ] >>743 よわかりませんが、M系列で「加算」する場合もキャリーは１ット隣なのでしょうか？ 755 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:42:56 ] >>754 最低限言えることは、SPUには任意の位置のビットにキャリーアップしてくれるような特殊な算術加算命令はないということだ。 まあそういうことだ。 ハードウェアに不向きなことをやらせて性能を出そうという方が間違い。 756 名前：デフォルトの名無しさん [2009/01/22(木) 23:49:49 ] なんだかよくわかりませんが、よくわかりました。 ありがとうございました。 757 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:55:21 ] 関係ないけどJNBのトークンって暗号形式なんだったっけ？ 758 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:59:44 ] そろそろ詭弁の○○ヶ条で〆てくれ 759 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:06:08 ] >>753 そこはAESばっか、に訂正しろよ。 AESが世界的に選ばれてるのはAESがAESだからだ。 AESに選ばれなかったfeistel暗号の信頼性を保証する根拠にするのは間違いだな。 とっくに死んだはずのDESが何故かワンタイムパスワードとして現役で使われてたりするくらいだし。 そのレベルで言うならMD5やRC4だって未だに使われてるんだぜ。 iがつかないニンテンドーDSだとWi-FiはWEP（RC4）強制だしｗｗｗｗｗ それに比べれば国産暗号のMISTYとかCamelliaなんてまだまだマイナー杉。 松井さんには悪いが。 760 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:11:09 ] ん？ DES も Feistel だろ？ MISTY1 も Camellia も NESSIE とってるが。 ＆ MD5 と RC4 をこれから新規に採用する規格があったら驚きだが？ 761 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:17:04 ] ちなみに、SHA-3 コンペでも feistel 使われてるぞｗ 762 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:18:28 ] 当たり前のこと言ってどうすんだ。鍵長考えてものを言え。 引き合いに出すならRC6あたりだろ。 RijndaelがAESに選ばれたのはその一つとしてDESみたいな複雑なビットシャッフル演算がなくて 専用ハードウェアでなくても実装コストが軽いからだ。 別にRC6の暗号強度が否定されたわけではない。 763 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:30:55 ] すまん、ちょっと読み違えてた。が、時間がない。また今度w あ、俺も RC6 の暗号強度を否定するつもりは毛頭ないよ。 764 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:33:43 ] そもそも別にLUTよりビット演算のほうがコストパフォーマンスが優れてるなんて言う気はない。 不毛すぎ 今回のTemperingを通す前にサマリ計算が出来るかどうかだが 実用的な計算時間をはじき出すのは「無理」と言えるレベルの相関性の破壊は達成できてるというのが 俺の見解。 俺個人は国産暗号マンセーの立場なので君に付き合ってRSAの腐れの擁護する気もない。 ちなみにSHA-3候補として俺が注目してるのはこれ ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf ＃あとAESは厳密にはSPNSであってFeistelには分類されない。 765 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:37:12 ] 日本語でおｋ 766 名前：デフォルトの名無しさん [2009/01/23(金) 00:39:15 ] 当たり前のこと言ってどうすんだ。 767 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:43:44 ] 個人的にCamelliaのSSE4向け実装とか開発中 おれ松井さん好きだし ＞Fixstarsさん 来年の課題はCamelliaでお願いします。 768 名前：復活 mailto:sage [2009/01/23(金) 01:17:25 ] >>764 俺の見解は、拡散って意味では tempering も sbox も同じってのには同意。 だが、シフト＋ビット論理演算ではできない substitution を実現するために sbox を導入してんだから、それを安易に同列に扱うのは理解できん。 あ、国産マンセーは俺も一緒。来年 Camellia いいねぇw 769 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:09:19 ] ま、とりあえず俺の情報源のひとつ晒しておくわ。 暗号アルゴリズム及び関連技術の評価報告 cryptrec.nict.go.jp/cryptrec_03_0424_outrep.htm S-boxを使わないRC6はかなり高い評価を得てるよ。 一般的なバイトマシン・ワードマシンでビット演算でやったらめちゃくちゃコストかかる演算を LUTなら簡単に実装出来たりする。S-boxの多くは、RISCプロセッサのビット演算にそのまんま展開すると とんでもない演算数がかかったりするんだが、それは暗号理論的な堅牢性の根拠としては弱いと思うよ。 バイトマシン・ワードマシンじゃなくて、ビットマシンとかASIC・FPGAだったら？ たとえばDESのS-boxはAND/OR/NOT/XORの基本的な1ビット論理演算で たったの平均56ゲートで構成出来る。 これは具体的にいうと32ビットワードの全加算回路に必要なトランジスタ数よりもかなり少ない。 AESのS-boxは・・・実装についての論文あったけど、いくらだったか忘れた。 （総当たりで最短を検索するプログラムが手元にあるけど8ビット×8ビットのS-boxは計算時間的に流石にきつい） 見方を変えようか AESやCamelliaはS-boxを除けば、DESのIP・E・P・FPでやってるような複雑なビット単位の 攪拌処理をやらずに、世界最高水準の安全性を実現してるわけだ。 更にいうと、CamelliaはS-boxは実質的に8ビット入力×8ビット出力のものがたった1つだけしかない。 その点でみてソフトウェアでの実装の複雑さと暗号的な強度は別モノと考えてる。 770 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/23(金) 02:17:31 ] >>710 とりあえず13clock切れた。けど謎のストールに阻まれ停滞中orz 771 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:34:03 ] 本命：団子 対抗：>>202,>>227 大穴：>>579 772 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:44:12 ] Camelliaの教科書的実装より引用。 俺はなんでこれでAESなみの強度が得られるのか疑問だったよ。 #define SBOX1(n) SBOX[(n)] #define SBOX2(n) (Byte)((SBOX[(n)]>>7^SBOX[(n)]<<1)&0xff) #define SBOX3(n) (Byte)((SBOX[(n)]>>1^SBOX[(n)]<<7)&0xff) #define SBOX4(n) SBOX[((n)<<1^(n)>>7)&0xff] 2と3は1の出力値をローテートしてるだけ。4は入力値をローテートしてるだけ。 なんでこれで「AESなみの暗号強度を実現できる」（中の人談）のか >>771 というか、どうやら俺が見つけた最適化方法は既にこのスレで13clk切った連中は見つけてると思うよ。 あとは実装勝負なわけだが、アセンブラ相手にCで勝てる気はしない。 具体的にいうと現時点では>>693よりは遅い。ガチ。 （てかこの人が最速っぽい） ただ俺にとっては今回の挑戦はどこまでもHack the spu-gcc43なのだ。 アセンブラ使わないと優勝できないのはわかってるが、アセンブラを使うのは俺的に負けなのである。 Cのみで挑戦する人向けに特別賞でも用意してくれるなら俺は喜んで表彰台にあがってやるぜ。 （herumi氏も参戦してきたことで、それですら負ける気がしてきた） 773 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:47:12 ] まあ、どうやってコンパイラの副作用を抑え込んだのかっていうのはソースにびっしり書いてたりするから 俺が上位に残ってたら参考にしてくれ、的な。 774 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:55:35 ] >>769 俺の言いたい事は >>768 で言ったが、「今 feistel ばっか」とかが 気に食わないんかな？ sbox ＝ 堅牢と言ってるんではなくて、堅牢さと 速度を両立するのに sbox が向いてると言いたいだけなんだが。 シフト＋ビット論理演算だけで同等の堅牢さを実現するよりも、 sbox の方が早くし易いし、小さくもし易いって理解なんだけど。 だから NIST にしろ NESSIE にしろ、feistel 系ばっかなんでしょ。 それだけ別物だから俺には tempering と sbox を同列には扱えん。 以上。 775 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:55:47 ] >>772 俺はアセンブリじゃないと絶対に出来ないことをやってるから他の点の実装が一緒なら有利かもしれん 正直な話このスレで結構な数のヒント貰ったからこれがないと負けてた 776 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 03:46:15 ] この程度ならあんまり影響っていうレベルで、Cで組む人にアドバイス。 （というかC＋組み込み関数で俺に挑もうと考えてる奴は流石にいないだろう） 特にイライラしたのは、even側の命令減らしたいのに値のロードにimmidiate load（evenロード)に勝手に展開しやがること。 qword型でしてるのにimmidiate load。 どうやらQWORDの全要素が同一の値だと勝手にimm loadに展開しやがるらしい。 んで、volatileにしたらアドレスからロード（Odd）に展開してくれるようになった。 とか、いろいろ。 あと、AND/OR/XORなどで使う値はhalfwordに即値指定すれば命令数を減らせる。 俺としてはまた方針を変えてパイプラインを詰め直そうと思っている。 現時点で片方のパイプが全部埋まるところまでCで詰めることができてるわけで >>774 残念だが同意できない。 標準規格においてダントツのトップに君臨するAESはFeistel系アルゴリズムとちょっと似てるが分類上別物。 あと示したとおり、Camelliaは普通のFeistel型暗号で従来4つ以上のLUT（S-Box）が必要な処理を 1つのLUTとローテートで水増ししてるけど、その点で強度に問題があるといわれたことは無い。 単一のS-boxにビット演算を少し組み合わせるだけで、強度を得るのに必要なS-boxの数を 実質的に減らすことができるのだから、シフト・論理演算・定数の組み合わせでS-boxを使わずに 性能と強度を得るのが不可能とは思わん。 実際問題、S-boxを使わないRC6は多くのFeistel暗号より高速で、なおかつ十分な堅牢性がある。 S-boxがハードウェアの負担が小さいってこと自体同意できない。 モバイル向けのプロセッサにはAESのS-boxすらデータキャッシュに収まりきらないくらい小さいものもある。 CamelliaがSBOXを最小の実装でたったの256バイトのLUTだけで構成出来るように配慮されてるのは ミリワットクラスの組み込みCPUでの実装を視野に入れてるからだ。 CamelliaのS-boxが小さいことは、キャッシュメモリが小さいアーキテクチャにやさしいということでもある で、それでいて十分な強度という評価を得ている。 777 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 04:24:16 ] うーん、論点がどこなんだかイマイチ解らん。 feistel の sbox と spn の sbox は別物なのか？ 俺も不可能とは思ってないし否定もしないよ＞RC6 負担が小さいとも思ってない。堅牢性と共に、早く 出来ることも小さくする事も可能なのが重要なだけ。 AES の sbox も 256 だったと思うのだが違うのか？ 俺には tempering と sbox を同列に扱うのは理解 できないし、「みたいなもん」なんて説明には到底 同意できんから異は唱えるが、別に団子がそれで 間違ってないって思うのはどーでもいーよ。 ってか、こんな話誰もついてこねーよなw でもさー、団子も sbox 系とシフト・論理演算系を 綺麗に別けてねーかw　やっぱ別なんじゃね？w 778 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 05:11:28 ] >>770 みんなすげぇなぁ。 おいら even -1 したら、odd +3 = total +1 で意味なかったよ orz 779 名前：202 mailto:sage [2009/01/23(金) 09:21:02 ] >>778 wwwwwwwwwwwww すっげーヒントあげたいけど、その壁は自分で超えろ。 780 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 09:41:39 ] >>778 大丈夫、私もその辺で挫折した。つーか、飽きたw 781 名前：202 mailto:sage [2009/01/23(金) 09:42:23 ] >>693が、58156364 / 4 * 12.5 / 40 = 4543466 か。 この数値が出せてたら俺より速い。 >>775 の意味も判る。 現時点でこのスレだと、 優勝、準優勝候補 : >>693 , 俺 優勝候補を抜く可能性のあるヒト: >>568, >>579 だんごさんと >>579 の話にはついていけなかったんだが、 とりあえず >>579 の Prolog が導き出した解法のサイクル数が 出るまではインラインアセンブラで限界まで行った者勝ちっぽいな。 782 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 11:13:19 ] まー普通に考えても、ここに書き込んでないやつで優れた奴もいるだろ〜から 優勝候補をこのスレ内で絞るってのも無理があると思うんだけどな 783 名前：202 mailto:sage [2009/01/23(金) 11:46:04 ] >>782 もちろんその可能性は否定しない。このスレを読まないと、「命令数どこまで減らせる」という 指標がない状態でチキンレースに参加しないといけないからキツイけど、このスレをROMってるなら 命令数がどこまで減らせるか判るね。 784 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 11:59:48 ] >>781 おい、俺様を優勝・準優勝の可能性からはずすな！ いや外してもいいや。こっから先の手の内は明かすわけにはいかない とりあえずカードは残してる。 785 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 12:06:20 ] >784 だって亀田兄弟的ポジションじゃんｗ 786 名前：202 mailto:sage [2009/01/23(金) 12:08:22 ] >>784 まじかよ・・・ >>693の12.5がもう限界だと思ってた。 787 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:16:58 ] >>786 全然関係ないけどさ Oddへの置き換えなしだとEven側は18くらいかかるわけだけど、これを17に減らす方法って気づいた？ 788 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:27:55 ] mt[n] = mt[m] ^ (x >> 1) ^ (((x & 1) == 1)? 0x9908b0dfUL : 0); ↓ x = rotr(x, 1); mt[n] = mt[m] ^ x ^ ((x > 0x7FFFFFFF)? (0x1908b0dfUL) : 0); ※これを使ってもチキンレースには参加できません。課題が別モノなら有用だったかも これ問題公開されてから3日くらいで考えたネタだけど、最終的に高速化の候補としては外れた方法だから敢えて紹介しておく。 あとブロック単位じゃなくてスカラ単位で取り出す場合はこっちのほうが速いかもしれない。レイテンシ的な意味で。 789 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:44:24 ] ^ x ^ ↑このへんがむかつく 790 名前：202 mailto:sage [2009/01/23(金) 13:24:28 ] >>787 evenの命令数削減は無意識だから、どうやったら even18 になるか悩んだ。 andc ともう一つ命令を使うヤツか？ もう一つの命令で予約違反してるけど、将来のSPUで動かなくなっても 構わないと判断したよ。 791 名前：202 mailto:sage [2009/01/23(金) 13:26:21 ] andcじゃなくてselでも良いのか。 792 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 13:48:27 ] >>202 なに言ってんだ？w 793 名前：202 mailto:sage [2009/01/23(金) 13:54:00 ] いっか、トップランカーには無意味な情報だからバラしちゃえ。 spu_and( matrix_a, spu_cmpeq( spu_and( x , 1 ) , 1 ) ) ↓ spu_andc( matrix_a, spu_subx( z, z, x ) ) 794 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 13:58:00 ] コンテスト参加してんのお前らだけじゃねーぞ 少しは考えろ 795 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 14:00:30 ] ってか、202 には >>788 の答えは見えてないのか？ 796 名前：202 mailto:sage [2009/01/23(金) 14:00:57 ] >>794 悪い。調子乗りすぎた。 締め切りまで黙ってる。 797 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 14:03:11 ] >>793 そ　　ん　　な　　方　　法　　も　　あ　　っ　　た　　の　　か 第一オペランド破壊する命令はうまく考えて使わないと困るんだよね。 >>788見つけたときは俺SUGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEって思った 798 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 14:06:19 ] >>797 こんなので思うな!w 799 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 21:14:51 ] 8bit×4の水平加算とかあるけど何に使うんだコレ SSEのPSADBW/MPSADBWと同じく、動画の動き検出とかに使うんだろ？ それしか思いつかない。 悲しいことに今回の課題でも役に立たない。 如何あがいても垂直加算のほうが性能出る。 これがもしもOddで処理されるならまた使い方も違ったんだけど。 800 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 21:23:56 ] absdb/avgb/sumb あたりは動画のためだぁな。 801 名前：579 mailto:sage [2009/01/23(金) 21:43:31 ] ORIGNAL: sum=26842941, 20235458 ticks MINE: sum=26842941, 296432 ticks ORIGNAL: sum=ff298dc7, 29209150 ticks MINE: sum=ff298dc7, 416484 ticks ORIGNAL: sum=e41976b4, 21287451 ticks MINE: sum=e41976b4, 359310 ticks ORIGNAL: sum=1d20a3cf, 19895914 ticks MINE: sum=1d20a3cf, 271577 ticks ORIGNAL: sum=7ab6f153, 1012083 ticks MINE: sum=7ab6f153, 80442 ticks ORIGNAL: sum=d528faae, 14662211 ticks MINE: sum=d528faae, 226395 ticks ORIGNAL: sum=f2e9b16f, 20421921 ticks MINE: sum=f2e9b16f, 285473 ticks ORIGNAL: sum=c38c3ffb, 17745083 ticks MINE: sum=c38c3ffb, 312869 ticks ORIGNAL: sum=4a476dd4, 17155127 ticks MINE: sum=4a476dd4, 268986 ticks ORIGNAL: sum=817388cd, 412802 ticks MINE: sum=817388cd, 60522 ticks 課題アナル(仮称)間違えていたよ orz ところで、いつまでも仮称だとアナルが可愛そうなので、正式名称を ハックtheアナルに決めたよ。ついでに処理系と実装も変えたけど。 802 名前：579 mailto:sage [2009/01/23(金) 21:44:09 ] $ diff mt19937ar.sep/mt19937ar.c~ mt19937ar.sep/mt19937ar.c 52c52 < #define MATRIX_A 0x9908b0dfUL /* constant vector a */ --- > #define MATRIX_A 0x9908b0cfUL /* constant vector a */ $ uname -mrsv Linux 2.6.18-6-powerpc64 #1 SMP Fri Dec 12 23:54:31 UTC 2008 ppc64 $ cat /proc/cpuinfo processor : 0 cpu : PPC970FX, altivec supported clock : 2700.000000MHz revision : 3.1 (pvr 003c 0301) processor : 1 cpu : PPC970FX, altivec supported clock : 2700.000000MHz revision : 3.1 (pvr 003c 0301) timebase : 33333333 platform : PowerMac machine : PowerMac7,3 motherboard : PowerMac7,3 MacRISC4 Power Macintosh detected as : 336 (PowerMac G5) pmac flags : 00000000 L2 cache : 512K unified pmac-generation : NewWorld ですが、何か？ 803 名前：579 mailto:sage [2009/01/23(金) 21:45:05 ] ちなみに、実装は C99 な。本当の意味でのな。altivec も使っていない。 32bit ビットスライスｗでこの程度。端数の処理はまったく最適化していない。 SIMD 化したらもっと早くなるかなぁ（棒 >>720 >突っ込みどころのデパート。詭弁の集大成。 で、 >>729 >だからTempering前の値をいくら「加算」しても無意味なんだ。 言いたいことはそれだけ？ >>579 >tempering 前の「とある値」を集計する。GF(2)の中で。 >すると、tempering (相当の操作)は一回で済む。 誰も tempering 前の値を「そのまま」加算するとは言っていないぜ？ 加算するとも言っていない。首尾一貫してるだろ？ >>730 >彼は全然役に立たないことしか言ってない。 ｵﾏｴﾓﾅｰ >>771 そんなに俺のアナル大きい？ >>781=202 俺？優勝する可能性？ないよ。出ないしｗ 804 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 21:56:21 ] >>801 おいORIGANALが本来のターゲットより一桁以上速いぞw でも、多項式取り違えてたとはいえ、すげえ伸び率だね。 805 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:05:25 ] よくできた捏造だな でもターゲットはＰｏｗｅｒPCじゃなくて「SPU」 806 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:08:25 ] よ、よく出来てるのか？ｗ 807 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:09:26 ] > 俺？優勝する可能性？ないよ。出ないしｗ これを書くのはもうちょっとあとの方が面白かったかなｗ 808 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:09:33 ] >>805 たしかに>>732より、よくできてるのは間違いないな 809 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:11:27 ] ゲハ板で発狂してるアスペル君が勝手に勘違いしただけだろそれ 810 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:12:40 ] さすがに俺もそう思う。団子はウザイけど >>732 は無罪。 811 名前：808 mailto:sage [2009/01/23(金) 22:15:00 ] そうだったのか。団子ごめん 812 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:16:23 ] PPUとSPUが同じコードシーケンスで実行できるとかアホなこと言いやがんだもん ＰＰＵに18issueの命令帯域が必要になるぞって言ったら、十分とかいいやがるし しまいには、SSEがｘ86のフォーマットとはかけ離れてるとかｗｗｗ あの命令フォーマットがｘ86でなくてなんなんだよ 813 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:37:38 ] 大丈夫だよ。あのコピペで団子は間違ってないってみんな分かってるから。 団子が間違いを認めなくてウザい事もかなりあるがな。 あと接頭辞のように付いてくる「知り合いに誰々がいる」って下りもウザい。 知り合いが有名なだけで、別にスネ夫が偉いわけじゃないだろう。 814 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:38:02 ] 「サマリだけ求めるショートサーキット禁止」 とか胴元が慌てて言い出したら爽快だな。 つか出題者があたまわるいってことになるが。 815 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 22:45:01 ] 俺もそろそろトランザム（笑）発動しちゃおうかな そろそろ勘のいい人は愚直な方法がいくらばかばかしいことに気づいてるかも知れない頃だし >>814 関数抜ける前にMTの配列に書き戻しさえすれば等価な実装でもかまわないのでは？ 816 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 22:59:23 ] ルールを根本変更されると正直悲しい。そしてキツい。 単なるチキンレースなら降りる。 817 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 23:18:26 ] 課題見直しで延期とかになったら面白い。 MTの配列を毎回舐める必要がない前提ならトランザム（笑）可能なことは気づいてた。 それをやるとアルゴリズムが根本から変わるけど コアループ抜けてからMT配列に書き戻せばちゃんと再実行も可能。 818 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 23:32:24 ] >>734の言うとおりになったな 819 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 23:39:57 ] 俺もロジックジェネレータ改造したそろそろ走らせようかな テキトーに当たり付けたパターンを再帰で全部試す馬鹿な方法使ってるから最適に近い方法見つけるのに1ヶ月くらいかかる。 俺の試算だと 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 ] そんなのは中の人が判断すること。けちつけるくらいなら精進しる 921 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:26:14 ] >>919 ちなみに俺はCell特有と言ってもいい命令を駆使して再設計してるよ。 今まで全くつかってなかった命令だ。 逆に従来のやり方だとSSEでもできることしかやってない。 922 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:29:46 ] >>921 再設計するのは勝手だが、大会終わるまで古い方法はさらすなよｗ 大丈夫だと思うけど、一応な 923 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:32:07 ] >>922に一票 924 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:35:57 ] 古い方法もブレイクスルー来たんだけどね。 今やってる方法がアリならこれもありじゃんって感じで。 晒しちゃうと手の内を一部明かすことになるのでやらない。スコアも一切出さない。 ただ一ついえるのは12とか13とかとは全く意味の無い数字になってしまった。 何もかも方法が違う。 925 名前：579 mailto:sage [2009/01/24(土) 22:40:25 ] >>924 スコア明かすことは、そのまんま pmt[] のサイズを晒すことに なっちゃうんだよねｗ 926 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 22:42:57 ] >>925 あんま団子にエサやるなって。 めちゃくちゃ釣れやすいんだから 927 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 22:49:12 ] >>925 そんなものは無いから。 おもっくそ泥っ臭い方法でやってるし。それこそSIMDのパワーにものいわせた頭の悪い方法で。 配列なんてレイアウトが変わったくらいでmt[]のサイズとほとんど変わらん 敢えて言っちゃうけど、160 qword分 928 名前：579 mailto:sage [2009/01/24(土) 22:57:54 ] >>927 レイアウト変えただけで、mt[] とは等次元空間ですな。 そのやり方ができるのであれば、(演繹的には)それに越したことは ないと思います。俺は自信なかったからチートしたけど。それとて、 fixstars に文句言われる筋合いはないけどな(帰納的には)。 脱帽です。 929 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:04:02 ] 別に数学的なんちゃら考えなくてもだんごの言うくらいには命令減らせるよ データレイアウトが思いっきり変わるから和を出すときは別として 乱数列を出す時に毎回展開とかやってられんけどな 930 名前：579 mailto:sage [2009/01/24(土) 23:09:03 ] >>929 12 とか 13cycle の 1/3 まで減らせるの？ それとも、俺また釣られているの？ もう誰もちんじれない 931 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:09:22 ] 全加算じゃなきゃ馬鹿らしすぎてやっとられんわ しかしこの配列構造は大好きです 932 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:15:04 ] というか>>929には気づかれたようだ 933 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:16:06 ] 試算だとその方法でtemperingにかかるのはQWORD当たり大体0.6サイクルを切る位 残念ながらだんごよりは2〜3割遅いけどな 俺はとりあえずもとの方法で最適化を続けるけど後はFixsters次第 934 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:17:13 ] すまん ×QWORD当たり大体0.6サイクルを切る位 ○WORD当たり大体0.6サイクルを切る位 935 名前：202 mailto:sage [2009/01/24(土) 23:18:07 ] 俺も、Fixstarsの回答しだいでは両方出すかも。。。 936 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:21:52 ] >>933 GFのほうを作り込んでるけどシャッフルによるパッキングのサイクル数を抑えられないので トータルだと似たり寄ったりな性能になりそうな予感。 しかし最後の加算は美しすぎてアドレナリン出てくるぜｗｗｗｗ 937 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:30:08 ] 579の思い置き去りの展開かよw 938 名前：デフォルトの名無しさん mailto:sage [2009/01/24(土) 23:31:34 ] 0.6は計算ミス どうやら0.5位だなぁ 殆ど同じ方法かもしれん 939 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/24(土) 23:31:42 ] 当たり前だ。1割も理解してない。 力業 is Justice. 940 名前：202 mailto:sage [2009/01/24(土) 23:57:59 ] やべぇ、俺もチートの方実装したくなってきた。 まだ12.5cycle切ってないんだが、、、 941 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 00:00:17 ] チートじゃねぇ 【邪道】だ 942 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 00:09:26 ] うーん。 3倍はﾌｶｼでした。サーセンｗｗｗｗｗ 943 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 00:40:32 ] Fixstersから返事があるまでCell Challengeやろうぜ！ 944 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:05:59 ] 枯渇でストールするのは単なるバグなので、それを考慮してアセンブラチューン するのはあまり生産的では無いね。90nm版のCellでしか発生しないんだから。 ま、90nm版以外を身近に手にする事は将来にも無いかもしれないけどね。(ｗ 945 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:11:05 ] 散々罵って結局だんごも579の方法でやってるのか？ 946 名前：202 mailto:sage [2009/01/25(日) 01:16:06 ] >>945 ちがうよ、数学できない俺でもできる方法。 947 名前：202 mailto:sage [2009/01/25(日) 01:16:55 ] ちがうか、だんごさんは2種類やってるのか。 948 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:21:16 ] 3種類だ。 949 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:26:45 ] >>984 579のやり方は机上の空論だって言ってたのは？ 950 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:38:25 ] 950 951 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:38:31 ] 俺は都度擬似乱数の生成を行ってから加算してる。そこだけは拘る。 952 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:42:17 ] 579に謝れよ団子 953 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:47:13 ] 繰り返す 【俺は都度擬似乱数の生成を行ってから加算してる】 どんな方法にせよTempering前にサマリ求めるのがアリだとは思わないからな 954 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 01:51:31 ] ありとかなしとか話題すげ替えんなよ 579はオツムがよわいとか能無しだとか言ってたろ？ 机上の空論じゃなかったんだから否を認めろよ 955 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/25(日) 01:56:23 ] やっと12clockになる方法思いついた。けど、そこから先のEvenを減らす道が 見えなくて困ってる所です。やっぱりレイアウト葬らないと壁を越えられない のかなぁ…。 >>912 数学の教養が無くても、転職してから１．５週で数十万行の構造把握して、 そこからバグ率を低く保って行く位の事なら出来てますよ。 つーか、今日になって（マイルストーン一ヶ月前なのに）コアな部分の 動作変更するとか言い出す上司がいて、バグの対処諸々考えてたら頭が 回らなくなってきました。初回からコケないことを祈るしか無いですｗ 956 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 01:57:46 ] 本物の頭の弱い子だね。 俺の意図とは無関係に本人が煽りだと思ってないわけでそれ以上は何も言うことは無いだろう。 「カード」そのものは彼が登場する前から用意してたものだよ。 957 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:00:59 ] 否を認めろよ ってくらいだからな 958 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:05:59 ] 頭が弱いのを認めとくとして >>俺の意図とは無関係に本人が煽りだと思ってない ってどう有意味だ？いやまじめに。 959 名前：デフォルトの名無しさん [2009/01/25(日) 02:16:49 ] 次 pc11.2ch.net/test/read.cgi/tech/1232817361/l50 960 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 02:23:21 ] >>958 ようするに団子は本当はできるのわかってて煽ってたってことだよ。 よく恥ずかしげもなくそんな言い訳できるわ。さすが糞団子だな！ 961 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 02:40:23 ] GF(2)の解法が全然別物ということが判明したので俺も俺で思い過ごしだったということだ 962 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 09:57:55 ] 拡大体 963 名前：579 mailto:sage [2009/01/25(日) 13:19:30 ] >>949 >>952 >>954 今回は俺の負ということで、もう、ゆるして。 >>955 冬山の知識が無くても、入隊してから１．５週で一個中隊の編成把握して、 そこから致死率を低く保って行く位の事なら出来てますよ。 つーか、今日になって（三本木までもうすぐなのに）コアな部分の 編成変更するとか言い出す少佐がいて、凍死の対処諸々考えてたら頭が 回らなくなってきました。初回からコケないことを祈るしか無いですｗ いかだ作って川を下るとか言い始めるんですね。わかります。 964 名前：579 mailto:sage [2009/01/25(日) 13:24:09 ] ×三本木 ○田代元湯 965 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:23:05 ] うーむ、もはや何の話をしてるのかすら外野の俺には分からなくなってきたｗ。 966 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:25:08 ] 八甲田山死の彷徨だろ 陸軍史くらい勉強しとけよ 967 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:32:29 ] >>966 確かに、プログラマにはデスマーチの知識も必要だな。 968 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:35:35 ] ああ、そういう意味なのか、やっと分かった。 （そういう比喩を持ち出した訳は） 969 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:36:20 ] なんか、学歴厨と学歴僻み厨の争いみたいな展開だな。 正直、どっちもどっち。 数学や哲学が分からん奴は、勉強してから発言しなきゃ不毛だしただの馬鹿野郎。 頭の中の話を主として話をしてる奴は、とりあえず現実とのスリ合わせが下手な駄目人間。 970 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 19:50:22 ] >579 MATRIX_Aの変更が重要なん？ 971 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 19:54:16 ] MATRIX_Aの変形って意味なら>>788の方法でもやってるね。 MATRIX_AとのXORはMersenne TwisterのTwisterたる所以だ。 ビット単位の行列問題に帰着すれば、なぜMATRIX_Aなのかわかるかもしれない。 972 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 20:04:30 ] 拡大体云々はRSA暗号のクラックにも有用視されてる方法だな ちょっとモチベーション低下気味なんで文献あさってるけど面白すぎる 973 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 20:30:21 ] 早くFixstarsには答えを出して欲しいところだな 俺はどっちになっても続けるけど脱落する奴もいそうだ 974 名前：デフォルトの名無しさん mailto:sage [2009/01/25(日) 22:45:03 ] >971 そうじゃなくて、579が>>801-802で書いたのはMATRIX_Aを変えたMTと、彼の方法の速度比較じゃん。 (だからsumも変わってる) オリジナルMTのsumを高速化するのは結局無理だったんじゃないの？と。 975 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/25(日) 22:55:03 ] Twist抜いたMTなんてMTじゃないですわ。 MATRIX_Aはビットストリームを改変する一種のsaltとして機能してるらすぃ 余談だが「Saltを加えたDES」（2chのトリップで使われてるcrypt(3)のそれ）は差分解読がやりにくいなんて 現役の数学者が言ってたよ。 976 名前：デフォルトの名無しさん [2009/01/26(月) 17:33:50 ] ↑こいつ何者？ 977 名前：デフォルトの名無しさん mailto:sage [2009/01/26(月) 18:24:59 ] アイちゃん 978 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/26(月) 22:32:55 ] とりあえず公式見解が出るまでコーディング作業はお休み。 >>967 デスマに巻き込まれるとゆとりが無い分行動が不安定になってくるんですね。 # ４日連続勤務時間中にFPSやってる上司とか見て発狂しそうになってますｗ 979 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/26(月) 23:19:02 ] saltをとは何かを考える、 日本語でいえば「お塩学」 ファッキンライト ﾃﾝｷｭｰ 980 名前：579 mailto:sage [2009/01/27(火) 01:09:23 ] >>970 >>974 アナルに突っ込んだ行列が間違えていただけの話。 ハックtheアナルの結果でたから、再トライした結果がこれ。 ORIGNAL: sum=3c927c56, 20051002 ticks MINE: sum=3c927c56, 480600 ticks ORIGNAL: sum=2e987a4d, 28979324 ticks MINE: sum=2e987a4d, 680855 ticks ORIGNAL: sum=ef1b6aef, 21517023 ticks MINE: sum=ef1b6aef, 573675 ticks ORIGNAL: sum=eedd2516, 19761023 ticks MINE: sum=eedd2516, 446886 ticks ORIGNAL: sum=f7e967a8, 981473 ticks MINE: sum=f7e967a8, 116481 ticks ORIGNAL: sum=1f37a7db, 14592172 ticks MINE: sum=1f37a7db, 365659 ticks ORIGNAL: sum=c7d41f36, 20085705 ticks MINE: sum=c7d41f36, 465866 ticks ORIGNAL: sum=aa9d2e9f, 17899900 ticks MINE: sum=aa9d2e9f, 495607 ticks ORIGNAL: sum=8abd398a, 17074673 ticks MINE: sum=8abd398a, 434344 ticks ORIGNAL: sum=a374bd58, 415390 ticks MINE: sum=a374bd58, 86607 ticks 981 名前：579 mailto:sage [2009/01/27(火) 01:09:50 ] >>722 >ざっくりと pmt[] の最悪値を見積もり始めた頃から勝算はあった >わけだが、解析結果を見ると想像以上に小さい。 大口たたいたものの、MATRIX_A 直したら、ごらんこのザマだ。 最後の評価なんて最低合格ラインの 10 倍満たしていない。 ぶっちゃけ、46KiB の制約に収まるかも怪しい。 SIMD 化すればまだ可能性はあるかもしれないけど、俺は燃え尽きた。 団子にはかなわないよ。悔しいけどな。 982 名前：579 mailto:sage [2009/01/27(火) 01:21:13 ] >>978 上司の気持ちもわからんでもないな。 >>202 >>227 まだ若いみたいだから教えておくけど、開発の現場で 一番必要とされているスキルは何だかわかるかい？ ウンコみたいなコードを読み取るスキルでもなく、バグの少ない良質な コードを生産するスキルでもない。 正しい日本語と、寛容な気持ちだよ。 そのうちわかる日が来るさ。頼むから、俺みたいなクサレジジィには ならないでくれ。 "Der Alte wuerfelt nicht." 983 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/27(火) 01:25:37 ] ん？シミュと実機じゃTick値の意味が違うのか？？？？？？ 984 名前：579 mailto:sage [2009/01/27(火) 01:33:35 ] 先週5日間連続＋今日1日、勤務時間中にLBPやっていた俺が言うのもなんだが。 985 名前：579 mailto:sage [2009/01/27(火) 01:35:14 ] >>983 つか、PowerPC なんで。SPU への移植性なんて考えていないよｗ tb_get(get_tbだっけ?)は /usr/include/asm/time.h からかっぱらってきた。 986 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 01:47:54 ] 結果出してから大口叩けばよかったのに 987 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/27(火) 01:49:14 ] びびらせんなｗｗｗｗｗｗ 988 名前：デフォルトの名無しさん [2009/01/27(火) 07:47:08 ] 579の欺瞞によりダンゴさん始まったな 989 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 10:41:15 ] >>988 まてまて、スカラと最適化済みベクタで差の出にくい 普通の PowerPC で >>980 だとしたら、SPU じゃさらに ４倍差開くと見ていいだろ。 >>287 >>288 の通りなんじゃねーの？ 990 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 14:50:11 ] >>989 PPC970だろ？ちょっとコードの書き方変えるだけでも差は出るよ。 ループはあまり得意ではなくて、タイトな部分があればアウトオブオーダで並列実行できるから アルゴリズムレベルでたいしたことは無くてもそれだけで性能が伸びてしまうこともある。 991 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 14:53:04 ] SIMD化で性能単純4倍と考えるのも愚かだ。 ミスアラインロードの連発で性能出ないことだってある。オリジナルMTがそうであるようにね。 テーブルも16バイトアラインしたら容量オーバーかもしれないね。 992 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 17:24:41 ] そろそろ皆さんハッタリのネタが無くなって静かになっちゃいましたねｗ 993 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 17:39:59 ] 10cycを切ることはありえない 994 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 18:58:49 ] >>993 ﾆﾔﾆﾔ 995 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 19:15:53 ] >>981 ってかさぁ、１０倍満たしてないし、どうせ参加しないんだったら コードさらしてみてよ。ハッタリじゃないんだったらさｗ 996 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 19:39:44 ] 「Hack the 579コード」のはじまりです 997 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 19:43:25 ] 推測するに>>802はミスにより既約でなくなったんジャマイカ? つか64ビット整数で処理したら速くならない? 998 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2009/01/27(火) 19:50:02 ] >>997 実は、PPC970は64bit ALU×2で、かつAltiVecの並列演算できるユニット少ないから ALUでやったほうが小回りが利いて速いことがある。 999 名前：デフォルトの名無しさん mailto:sage [2009/01/27(火) 20:03:39 ] よっしゃ!! 8.5 cycle 切った!!! 1000 名前：1000 mailto:let's transpose! sage [2009/01/27(火) 20:04:06 ] 「Hack the ハッタリ」 第２章 -> pc11.2ch.net/test/read.cgi/tech/1232817361/l50 1001 名前：１００１ [Over 1000 Thread] このスレッドは１０００を超えました。 もう書けないので、新しいスレッドを立ててくださいです。。。

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef