PTT數位生活區 / C_and_CPP (C/C++)

[問題] 不用除法，算出整數除以五的商

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