› 看板 C_and_CPP 關於我們 聯絡資訊
作者WeBurn (燒)
看板C_and_CPP
標題[問題] 快速求出整數除以五十的商?
時間Sat May 12 05:34:54 2012
請問有什麼特別的密技或算法嗎? q = x/50 這除法的動作，會消耗很多時脈啊 (x86上耗4x個) 想成 ((x/5)/5)/2 那問題又回到除以五上面了 那請問有什麼方法可以快速求出x/5的商呢? 也就是不用除法指令，算出除以五的商 XD 有神人嘗試過的嗎 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 182.235.78.55
→ EdisonX:q,x 均為整數 ? 05/12 05:54
推 purpose:http://ideone.com/C9l8y esp+8 是你的x，ecx 就是你的q 05/12 08:43
→ purpose:原始碼直接寫 x / 50 用 VC 最佳化後的指令 05/12 08:44
→ stupid0319:x/50 = x*(2^50)*(1/2^50) 05/12 09:14
→ stupid0319:其中2^50跟1/(2^50),編譯器可算出來 05/12 09:16
→ stupid0319:好像錯了,x/50 = x * (2^n)/50 * (1/2^n) 05/12 09:18
→ stupid0319:由編譯器取n值最佳化除法 05/12 09:20
→ BombCat:st大可以給一下哪裡有資料說明這樣作的原理嗎? 05/12 09:23
→ stupid0319:取n值後(2^n)/50是固定數z,x/50=x*z/2^n 05/12 09:31
→ stupid0319:這樣做shr的話,時脈會比較快 05/12 09:33
→ stupid0319:purpose大有一行shr ecx,1Fh ,這個就是1/2^31 05/12 09:37
→ stupid0319:會看組語的可以對照purpose大貼的code 05/12 09:38
→ stupid0319:mov eax,51EB851Fh;這個應該是(2^n)/50,為定值,n=31 05/12 09:39
→ BombCat:感謝說明 05/12 09:54
推 purpose:Ceil(2^36 / 50) = Ceil(68,719,476,736/50) = 51EB851Fh 05/12 10:28
推 EdisonX:我覺得這篇講得不錯 #1Dznotk7 05/12 10:45
→ stupid0319:我又錯了QQ,我上面寫的參考就好= =,最佳化很複雜的XD 05/12 10:52
→ proach:現在 CPU 就是 /50 最快，不要浪費時間了。 05/12 12:46
推 PRAM:你用組合語言嵌入到c中最快, linus torvalds 都這樣幹 05/12 17:23
→ PRAM:反過來說如果你這樣做還比直接/50更慢的話, 就轉行吧@@ 05/12 17:24
推 purpose:不用轉行，轉個彎不要寫組合語言就好了 05/12 18:02
→ leiyan:除法指令都直接用除法器跑 應該不能再快了 05/12 20:48
→ suhorng:編譯器會優化, 除法畢竟比乘法慢....即使是硬體.... 05/12 21:31
→ suhorng:乘法也是用硬體呀.... 05/12 21:31
推 littleshan:嵌入組合語言不但沒比較快 還造成維護與移植的困難 05/12 22:57
→ proach:現在很多CPU都內建整數用 one cycle 除法器與乘法器 05/12 23:46
→ purincess:說實在的加上out-of-order execution來利用ILP 這根本就 05/13 01:20
→ purincess:是小事...你把資料從main memory搬到cpu都好幾百個cycle 05/13 01:20
→ purincess:了 (雖然也有non-blocking cache就是了(聳肩 05/13 01:21
推 holymars:這...這種事讓compiler最佳化不就好了= =　自己寫幹嘛 05/14 01:59
推 stupid0319:程式花錢給別人寫不就好了= = 自己寫幹嘛 05/14 09:44
→ calqlus:孩子給別人生不就好了 反正上新聞還可以直接切斷關係 05/14 16:57