【高速化】ビット演算　0x02

1 名前：デフォルトの名無しさん [2006/09/16(土) 09:46:26 ] 前スレ ビット演算 pc8.2ch.net/test/read.cgi/tech/1123918075/ 関連スレ アセンブラ…　(゜□゜) ↑アッー！↓ pc8.2ch.net/test/read.cgi/tech/1148402614/ 関連情報 Hacker's Delight ttp://www.hackersdelight.org/ ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか ttp://www.amazon.co.jp/exec/obidos/ASIN/4434046683 ビットを数える・探すアルゴリズム ttp://www.nminoru.jp/~nminoru/programming/bitcount.html Bitboard ttp://en.wikipedia.org/wiki/Bitboard 449 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 13:50:16 ] ぼ 450 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 23:03:56 ] ぬ 451 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 23:56:29 ] る 452 名前：デフォルトの名無しさん [2007/09/20(木) 00:04:43 ] ぽ 453 名前：デフォルトの名無しさん mailto:sage [2007/09/20(木) 18:42:49 ] >>450-452 ｶﾞ 454 名前：デフォルトの名無しさん mailto:sage [2007/09/22(土) 00:43:27 ] pc11.2ch.net/test/read.cgi/tech/1142467359/555 これもっと簡単にならないかな？ 455 名前：デフォルトの名無しさん mailto:sage [2007/09/22(土) 07:06:58 ] >>454 -------------------- int my_fputwc(wint_t c, FILE *fp) { wint_t r = fputwc(c, fp); return (r == WEOF) ? EOF : r; } int wtbl[0x10000]; void dokkade_jikkou(void ) { int i; for (i = 0; i < 0x10000; i++) wtbl[i] = i; wtbl[0xffff] = EOF; } int my_fputwc(wint_t c, FILE *fp) return wtbl[fputwc(c, fp);]; } みたいなこと(WEOF(wint_tの0xffff)をEOF(intの-1)に変換) をもっとスマートに行う方法ないですかね。 ---------これで何の不満があるんだ？----------- wtbl[0xffff] = EOF; for (i = 0; i < 0xffff; i++) wtbl[i] = i; } -------------------- 456 名前：デフォルトの名無しさん [2007/09/27(木) 20:24:00 ] age 457 名前：デフォルトの名無しさん [2007/09/29(土) 23:03:31 ] int rotate_0_9(int a){a++;return(a+(((a+6)>>4)+(((a+6)>>4)<<1))<<1)&15;} or int rotate_0_9(int a){a++;return(a+((a+6)>>4)*6)&15;} 引数が0〜8の時1を加算し、引数が9の時0を返す。 458 名前：デフォルトの名無しさん mailto:sage [2007/09/29(土) 23:17:24 ] return ++a%9; 459 名前：デフォルトの名無しさん mailto:sage [2007/09/29(土) 23:39:43 ] % はビット演算じゃないだろう 460 名前：デフォルトの名無しさん mailto:sage [2007/09/29(土) 23:58:36 ] int rotate_0_9(int a){return a<9?a+1:0;} 461 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:06:34 ] DAA 462 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:15:35 ] >>457 >>458 >>460 どれが速い？ 463 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:20:18 ] 実測あるのみ 464 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:34:05 ] 試してみた！ cl /O2 rot9.c rot9 rotate_0_9_457_1 1873 msec rotate_0_9_457_2 1272 msec rotate_0_9_458 4016 msec rotate_0_9_460 641 msec >>460が圧倒的だった(俺もそう思ってた) ソースに続く 465 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:34:50 ] >>464のソース (VC6SP4) ---------------------------- #include <windows.h> #include <stdio.h> int rotate_0_9_457_1(int a){a++;return(a+(((a+6)>>4)+(((a+6)>>4)<<1))<<1)&15;} int rotate_0_9_457_2(int a){a++;return(a+((a+6)>>4)*6)&15;} int rotate_0_9_458(int a){return ++a%9;} int rotate_0_9_460(int a){return a<9?a+1:0;} //#define COUNT_TIMES 0x7fffffff #define COUNT_TIMES 0x7ffffff #define TEST(func) \ dwTime = GetTickCount(); \ for(i = 0, count = 0; count < COUNT_TIMES ; count++) { \ i=func(i); \ } \ printf( # func " %d msec\n", GetTickCount() - dwTime); main() { int i, count; DWORD dwTime; SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS); Sleep(100); TEST(rotate_0_9_457_1) Sleep(100); TEST(rotate_0_9_457_2) Sleep(100); TEST(rotate_0_9_458) Sleep(100); TEST(rotate_0_9_460) return 0; } ---------------------------- 466 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:38:34 ] printf( # func " %d msec (i:%d)\n", GetTickCount() - dwTime, i); と変更して計算結果も表示してみたら>>457の最初の式の結果がおかしい事に 気付いたんだけど。 rotate_0_9_457_1 1862 msec (i:0) rotate_0_9_457_2 1272 msec (i:7) rotate_0_9_458 3986 msec (i:7) rotate_0_9_460 671 msec (i:7) 467 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:40:00 ] int rotate_0_9_467(int a){ static int t[10]={1,2,3,4,5,6,7,8,9,0}; return t[a]; } 表引き。 これもやってみてくれ。 468 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:49:01 ] >>457 やってみるよ。 457_1のiの推移 0 2 6 14 4 10 12 0 2 6 14 4 10 12 0 2 6 14 4 10 12 0 2 6 14 無茶苦茶だった。 469 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:55:09 ] rotate_0_9_457_1 1893 msec (i:0) rotate_0_9_457_2 1272 msec (i:7) rotate_0_9_458 3996 msec (i:7) rotate_0_9_460 661 msec (i:7) rotate_0_9_467 621 msec (i:7) テーブル引きのがわずかに速いね。 >>460と>>467が微差だったんでカウンタ倍にしてみた。 #define COUNT_TIMES 0xfffffffに変更。 rotate_0_9_457_1 3535 msec (i:2) rotate_0_9_457_2 2553 msec (i:5) rotate_0_9_458 7991 msec (i:5) rotate_0_9_460 1332 msec (i:5) rotate_0_9_467 1202 msec (i:5) 計ったPCはThinkPad X31 (PenM1.6G Banias) XPSP2 470 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:57:00 ] あと>>458は0〜8の繰り返しで条件が違うんで int rotate_0_9_458(int a){return ++a%10;} に修正してる 471 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 01:13:29 ] _rotate_0_9_457_2 PROC NEAR ; 13 : int rotate_0_9_457_2(int a){a++;return(a+((a+6)>>4)*6)&15;} mov ecx, DWORD PTR _a$[esp-4] inc ecx lea eax, DWORD PTR [ecx+6] sar eax, 4 lea eax, DWORD PTR [eax+eax*2] lea eax, DWORD PTR [ecx+eax*2] and eax, 15 ret 0 _rotate_0_9_457_2 ENDP 掛け算消えるんだね _rotate_0_9_458 PROC NEAR ; 14 : int rotate_0_9_458(int a){return ++a%10;} mov eax, DWORD PTR _a$[esp-4] mov ecx, 10 inc eax cdq idiv ecx mov eax, edx ret 0 _rotate_0_9_458 ENDP 見るからに遅そうな 472 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 01:16:44 ] _rotate_0_9_460 PROC NEAR ; 15 : int rotate_0_9_460(int a){return a<9?a+1:0;} mov eax, DWORD PTR _a$[esp-4] cmp eax, 9 jge SHORT $L53312 inc eax ret 0 $L53312: xor eax, eax ret 0 _rotate_0_9_460 ENDP 普通だね _rotate_0_9_467 PROC NEAR ; COMDAT mov eax, DWORD PTR _a$[esp-4] mov eax, DWORD PTR _?t@?1??rotate_0_9_467@@9@9[eax*4] ret 0 _rotate_0_9_467 ENDP 短いね この短さがテーブル参照のオーバーヘッドを相殺してる？ けどaが10以上だったら脂肪 473 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 01:27:47 ] まあ表引きはキャッシュから外れた時にペナルティがあるから 平均的には>460がいいんだろうな。 474 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 02:05:05 ] >>473 確かに、別の環境だと逆転してたり。 #Celeron 430@2.4G XPSP2 rotate_0_9_457_1 1750 msec (i:2) rotate_0_9_457_2 1359 msec (i:5) rotate_0_9_458 2969 msec (i:5) rotate_0_9_460 719 msec (i:5) rotate_0_9_467 860 msec (i:5) #Core2Duo 4300@3.2G XPSP2 rotate_0_9_457_1 1281 msec (i:2) rotate_0_9_457_2 1000 msec (i:5) rotate_0_9_458 2172 msec (i:5) rotate_0_9_460 516 msec (i:5) rotate_0_9_467 656 msec (i:5) 475 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 04:40:29 ] ％は割り算があるから遅いってことか。0〜9ではなく0〜2^n-1の場合にかぎり使えばいいかな。 でも実際の仕事では0〜99のローテートでも％で書いたりするなあ。 476 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 08:29:40 ] 剰余は定数除算よりも更に遅い。 477 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 09:14:40 ] その剰余をビット演算でなんとか．．． 478 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 10:11:46 ] このスレの355から、剰余をビット演算でする方法が書かれているよ。 入力が必ず0〜9なら a=((a+7)&15)-6; 　// 0〜8 が 1〜9 9が-6 (aの符号拡張か　4bitの算術右シフト結果)のビット反転と and 479 名前：457 mailto:sage [2007/09/30(日) 23:43:50 ] ふぬぅ、やっぱ分岐しない上にテーブルも使わない奴は遅いな。 480 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 23:45:02 ] 逆に考えて、分岐する上にテーブルも使う奴は・・・ すまん、逆に遅くなりそうだ。 481 名前：デフォルトの名無しさん [2007/10/01(月) 16:44:48 ] modも内部的には分岐してるだろ。RISCならよくわかる。 482 名前：デフォルトの名無しさん mailto:sage [2007/10/01(月) 17:41:59 ] え〜(*o*) それは２のｎ乗の場合とそうでないので分けてるとか？ 483 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/10/04(木) 02:56:19 ] 剰余　＝　披除数 − (除数 ＊ 商) 一般的には商と剰余は同時に求めることが可能 484 名前：デフォルトの名無しさん [2007/10/21(日) 17:07:33 ] age 485 名前：デフォルトの名無しさん mailto:sage [2007/10/21(日) 18:36:55 ] 剰余のビット演算への変換ならこのページにあるよ。 www.tensyo.com/urame/date/dayTips.htm#MOD 縛りを入れるともっと高速化出来そう… 486 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 00:23:05 ] ある変数の値が 2018か2019 4049か4050 であるか判別する方法は4回比較するしか ないかな？ 487 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 00:49:07 ] 愚直な方法だけど比較２回には減らしてみた。 bool check(int value) { const int mask = ~1; if( (value & mask) == 2018 || ((value + 1) & mask) == 4050 ) return true; return false; } 488 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 01:56:04 ] テストしてないけど。 bool check(int value) { const int mask = ~1; if (((abs(value - 3034) + 1) & mask) == 1016) return true; return false; } 489 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 09:11:06 ] AND も加算も比較＝減算も、演算量は同じ、ってこと考えたら、どっちも減ってない。 比較４回に比べてリーダビリティは下がってる。 490 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 09:53:31 ] switch (value) { case 2018: case 2019: case 4049: case 4050: 　　doit(); } 491 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 11:06:26 ] if (v == 2018 || v == 2019 || v == 4049 || v == 4050) return 1; return 0; 0m48.123s 0m2.250s const int mask = ~1; if ((v & mask) == 2018 || ((v + 1) & mask) == 4050) return 1; return 0; 0m53.281s 0m2.278s const int mask = ~1; if (((abs (v - 3034) + 1) & mask) == 1016) return 1; return 0; 0m52.661s 0m2.167s switch (v) { case 2018: case 2019: case 4049: case 4050: return 1; } return 0; 0m46.065s 0m2.087s if (v < 2018 || (v > 2019 && (unsigned int) (v - 4049) > 1)) return 0; return 1; 0m45.938s 0m2.086s いろいろ測ってみた コンパイラやマシンによって違うと思うけど 492 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 11:25:06 ] ４回比較より下の２つのが短いのが不思議ですね。 入力が多数回で、４つの値が均等にバラつくという条件にしたら、最後まで演算しない４回比較 がイイかと思えますが。 493 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 11:26:33 ] >>489 可読性も考慮するの？このスレで？ 494 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 11:29:15 ] ちなみに最後の一個はswitchバージョンのアセンブル出力をCに直したもの 495 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 12:45:37 ] iccで試してみた。 # icc -xP -O3 -ip # icc 10.0 上から、0.3, 0.23, 0.33, 0.3, 0.22[sec/(10000 * 10000call)]だった。 どうやらswitchで書いても一番上と同じような出力になるようだ。 gccでも試してみた。 # gcc -O3 -funroll-loops # gcc 3.4.6 こちらは、0.16, 0.22, 0.27, 0.17, 0.22[sec/(10000 * 10000call)]だった。 なんでこんなに速いんだ?w 496 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 21:35:27 ] >>495 アセンブリコードで比較してみると分かるんじゃね？ 497 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 23:12:05 ] 俺には>>486が if(v==2018||v==2019){ }else if(v==4049||v==4050){ }else{ } って条件に読めるんだが 498 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 23:17:57 ] 俺も俺も 499 名前：デフォルトの名無しさん mailto:sage [2007/10/24(水) 00:23:34 ] >>486 日本語でおｋ やっと言う側に回れたか 500 名前：デフォルトの名無しさん mailto:sage [2007/10/24(水) 01:05:28 ] >>497 いや、今日きちんとみかか村に出撃して 糞仕様について問い詰めてきたけど case 2018: case 2019: case 4049: case 4050: で正しい どうもみんなありがとう 501 名前：デフォルトの名無しさん mailto:sage [2007/11/02(金) 19:56:43 ] >491 >if (((abs (v - 3034) + 1) & mask) == 1016) return 1; ここら辺の数値の導き方教えてください どいった関係で3034とか出すの？ど素人ですんません 502 名前：デフォルトの名無しさん mailto:sage [2007/11/02(金) 20:15:08 ] >>501 2018+4050=2019+4049=3034+3034 v = [2018 or 2019 or 4049 or 4050] の時 abs(v - 3034) = [1015 or 1016] abs (v - 3034) + 1 = [1016 or 1017] mask=0xfffffffeより奇数はそれを超えない偶数に変換される。 (abs (v - 3034) + 1) & mask = 1016 503 名前：デフォルトの名無しさん mailto:sage [2007/11/02(金) 21:44:43 ] >502 ものっそい感動しました 久しぶりに成長した気がする この括り方すげー 504 名前：デフォルトの名無しさん mailto:sage [2007/11/03(土) 20:48:03 ] もはや逆方向にソースから動作仕様を求めることはほぼ不可能だな 505 名前：デフォルトの名無しさん mailto:sage [2007/11/04(日) 06:35:34 ] かっこいい BIN→BCD は？ 506 名前：デフォルトの名無しさん mailto:sage [2007/11/04(日) 08:47:47 ] 速さなら、00h,01h,02h・・・を表に持ち、binで表引き。 <99のチェックは必要。 サイズなら、((bin/16)<<4) | (bin%16) ・・・バイト版。　<99のチェックは必要。 ワードは、／100の商と余りに分けて、上のを呼び、合成。 自分で書いたのはこんな当たり前の奴だなあ・・・ 507 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 16:03:38 ] しばらく前はメモリアクセスがからむテーブル参照の方が重いって話だったけど、 また状況変った？ 508 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 16:47:46 ] キャッシュの容量 メモリアクセス速度とキャッシュアクセス速度の比率 によって変わるからなあ 細かくいいだすとキャッシュ方式も絡むし 結局「場合による」んじゃねえの 509 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 17:28:19 ] 一般論としては、キャッシュに載っている(=頻繁に呼ばれる)ならテーブルの方が速いんじゃないかね。 ただ、この場合の「一般」というのは、分岐が含まれる(=分岐ミスの可能性がある)という前提。 例えば上の((bin/16)<<4) | (bin%16) の場合だと 依存関係が2箇所あって、その部分は同時実行は出来ないけど キャッシュアクセスに要する数クロック程度の時間と比べてどちらが速いかはわからんね。 テーブルジャンプ(ほぼ同じ値が続く場合以外)は糞だけど。 510 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 17:37:19 ] 掛けたり割ったりすることにものすごい抵抗感がある 511 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 18:06:01 ] いや、この場合に限れば、まず間違いなく最適化でシフトやアンドになるよ。 512 名前：506 mailto:sage [2007/11/11(日) 02:32:03 ] 今のチップで乗除算持ってないほうが珍しいよね。俺が書いたのは3MHzの8085だったから、 キャッシュ云々の話はなし。／100だけは除算ルーチン使わないとだめだった。 513 名前：デフォルトの名無しさん mailto:sage [2007/11/11(日) 13:44:02 ] ARMは現役のチップだけど除算命令なかったような 514 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 11:40:49 ] x/100　は　掛け算があるなら 655*( x + x/2048 + x/16384)/ 65536 515 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 14:14:26 ] その掛け算とｼﾌﾄの計算量なら、100=64hだから、分母の<<2と<<5と<<6を引いたほうが・・・ 516 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 15:57:51 ] y = (655*x)>>16 で概算して while ( x-y*100>=100 ) y++; ならせいぜいループ１回だろ 517 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 18:05:59 ] 最低でもx<6557202(≒(1<<32)/655)が言えなければ。 518 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 18:34:29 ] >>512 (42949672*x+65536)>>32 519 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 07:36:11 ] シフト演算子がアンカーになってしまう（ｗ >>514-516 は、たぶん数学的には同等なような気がする。 >>518 それ、どういう原理なの？ 32シフトしたら全部なくなっちゃうような気が・・・ 520 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 08:53:19 ] 32bitレジスタ持ってるような16bit以上のCPUを想定してるんだろ x386なら32x32bit掛け算の結果が２つのレジスタに判られるから 32bitシフトは上位のレジスタを採用するだけになる。 521 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 11:57:03 ] &gt;&gt;32 >>32 522 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:18:01 ] >>512 >>‍32 523 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:22:04 ] >>521 >>522 何が言いたいのか意味不明だ。 524 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:29:42 ] >>523 525 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:42:20 ] これでどうだ x >> 32 526 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:44:23 ] 俺他人だけど　>>‍523 色が違うだろって言いたいんじゃないのかな？ 527 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 13:11:18 ] >>523 こうすればいいのよ（たぶん） 528 名前：527 mailto:sage [2007/11/15(木) 13:12:44 ] >>‍527 吊ってくるorz 529 名前：518 mailto:sage [2007/11/15(木) 16:36:17 ] >>520 あたり。 あと、>>518のxは0〜65535の範囲である必要がある。 530 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 16:54:12 ] 多少ステップ数がかかるように見えても、まだハードウエア除算は普通の命令２０個分以上に重いからな 1/100 は1/10のルーチンを２度呼んでたな。 1/10は1/2/5 だから１ビットシフトしてから５で割る 65536/5=13107.2 だから13107を係数に使うと誤差は16bitの範囲で１ だけど１ビットシフトしてるから、15bitの範囲になってるから 最大誤差は0.5なんでOK という事で、最大誤差の0.5を足して x = x / 2 x = (13107*x+ 6553) / 2^16 を２度繰り返す 531 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 01:35:07 ] >>518 や、>>530 は余りも一緒に求まるの？ 532 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 08:46:49 ] この話は掛け算が高速ならという話だから 余りは後から　y=x/N を求めた後 x-N*y で求めればいい 余りだけが必要なら355付近から話題が出てる 533 名前：デフォルトの名無しさん [2007/11/16(金) 09:53:08 ] 実測で、ハードウェアまたはCの除算を上回るルーチン作れるの？うｐして 動かしてみる辛さ 534 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 10:26:25 ] どっかのスレでやってたでしょ。 パソコンの除算命令はレイテンシが大きいから連続して実行させるととても重くなる。 ただ整数ユニットでは実行されないから、その間に他の命令を入れられるならＯＫ あ、このスレか、>>367-379 535 名前：デフォルトの名無しさん [2007/11/16(金) 10:59:28 ] int型の除算で標準のものより速いものは作れるのか作れないのか？ 536 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 11:03:08 ] 分母が固定なら可能。　変数なら無理。　 537 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 11:04:47 ] まてよ。分子が固定な場合、ニュートン法である程度いけるかな・・・・まあ無理か 538 名前：デフォルトの名無しさん [2007/11/16(金) 11:23:21 ] 分母が固定ならif文などで分岐すれば、総合的には速度が上げられるのか? 作ってくれ 539 名前：デフォルトの名無しさん [2007/11/16(金) 11:26:26 ] 経験上、演算や比較文より代入に時間がかかる気がする たぶんレジスタ動作　+　演算より、メモリ動作は遅いんだろう 540 名前：518 mailto:sage [2007/11/16(金) 11:39:24 ] >>535 ループの中で定数(変数でも変わらなければＯＫ)で除算するのは、 置き換えた方が高速化できるし、それを実際に使っている。 ピクセル操作のような回数の多いループでは劇的な効果がある。 >>539 それは毎回キャッシュから外れた場合の話。 オンキャッシュなら少しでもＣＰＵを止めない方がいい。 541 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 11:45:08 ] >>538 で、分母はいくらなの？　100の場合はいろいろ出てるよね。 542 名前：デフォルトの名無しさん [2007/11/16(金) 11:46:27 ] 汎用の除算は出来ないか? 例えば2〜500まで定数だけ作って分岐させて使う そのとき高速になるのか? 543 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 11:48:53 ] その分岐の為に時間を使ってしまうから無理だろうね たとえば関数テーブルで分岐したとしても、キャッシュミスを起こすだろう。 544 名前：518 mailto:sage [2007/11/16(金) 11:50:14 ] >>542 できる。 それぐらいなら除数の逆数のテーブルを使って可能。分岐はさせないほうがいい。 ただ、16bit全域とかになると、テーブルの方が不利になるCPUが多い。 545 名前：デフォルトの名無しさん [2007/11/16(金) 11:54:52 ] 逆数で気づいたけど、浮動小数点の掛け算で計算すると鈍いの？ 546 名前：デフォルトの名無しさん [2007/11/16(金) 11:57:24 ] 逆数の2進展開を持っていたらビット演算できそうだけど・・・どうだろ　速いのか？ 547 名前：デフォルトの名無しさん [2007/11/16(金) 12:00:46 ] たびたび連投すまんが、計算でループを使うなら、はじめに分岐させてもコストは同じようなものだな 2〜1024までなら10回の分岐で決定する　10回程度のループを使うなら分岐させた方が良い 548 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 12:01:09 ] >>544 (A*x+B)のＡ，Ｂをテーブルにするの？ でも、たとえば　65535÷３はどうするの？A=21845にしたら、これでは無理だよね 549 名前：デフォルトの名無しさん [2007/11/16(金) 12:10:41 ] x / n = (Ax + B ) >> C ってどうやって求めるの？

---

---

[ 続きを読む ] / [ 携帯版 ]

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