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

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

看板C_and_CPP (C/C++)作者 (徵女友)時間14年前 (2012/05/12 13:00), 編輯推噓12(12推 0噓 18→)
留言30則, 5人參與, 最新討論串2/2 (看更多)
00401027: B8 1F 85 EB 51 mov eax,51EB851Fh 0040102C: F7 6C 24 08 imul dword ptr [esp+8] 00401030: C1 FA 04 sar edx,4 00401033: 8B CA mov ecx,edx 00401035: C1 E9 1F shr ecx,1Fh 00401038: 03 CA add ecx,edx 0040103A: 51 push ecx 拿p大的code來反推一下 假設,被除數x,除數o 也就是 x/o I.當x>0時 x/o = x* (2^n/o) * (1/2^n) 再設(2^n/o)為c x*c x/o = --- 2^n II.當x<0時 x*c x/o = --- + 1 ;向0取整,負數時要+1 2^n ------------------------------------------ 己知c = eax = 51EB851F, o未知 由於imul在edx時會高4個Byte,等於高了32位,再算上sar edx,4 共高了36位取得 n = 36 x/o = x*c >> n ,代入得x/o = x*51EB851F >> 36 得 x/o = x*51EB851F / 2^36 o = 2^36 / 51EB851F ~~ 50 得知這是除於50的除法優化 ---------------------------------------------- 00401033: 8B CA mov ecx,edx 00401035: C1 E9 1F shr ecx,1Fh 00401038: 03 CA add ecx,edx 這三行是取得結果的正負符號 把edx的值給ecx後,右移31位,如果是正數, 則ecx = 0,add ecx,edx等於+0 如果是負數,則ecx = 1;由於負數除法的結果要+1(這個我就不推導了) add ecx,edx等於+1 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.170.163.5
→
05/12 13:12, , 1F
你的意思是說把除法換成一些乘法和指數運算嗎?
05/12 13:12, 1F
→
05/12 13:13, , 2F
不過乘法的時脈也很多.
05/12 13:13, 2F
→
05/12 13:17, , 3F
我只是幫purpose大補充一下他要表達的內容@@
05/12 13:17, 3F
推
05/12 13:19, , 4F
除法換成 multiply shift，在 x86 下是比除法快
05/12 13:19, 4F
推
05/12 23:00, , 5F
現代的cpu乘法其實很快喔 latency大約3~4個cycle而已
05/12 23:00, 5F
→
05/12 23:02, , 6F
相較之下除法至少26個cycle起跳
05/12 23:02, 6F
推
05/12 23:36, , 7F
Intel 的 Optimization Reference Manual 附錄 C 表 C-13
05/12 23:36, 7F
→
05/12 23:37, , 8F
是寫 IMUL 的 Latency 為 15-18 耶，沒這麼快吧？？
05/12 23:37, 8F
推
05/12 23:40, , 9F
資料來源
05/12 23:40, 9F
推
05/13 00:02, , 10F
05/13 00:02, 10F
推
05/13 00:51, , 11F
那就可以將一個除法替換為少於七倍的乘法
05/13 00:51, 11F
推
05/13 03:06, , 12F
好像跟多核心有關？總之謝謝 littleshan 大解惑，感謝
05/13 03:06, 12F
推
05/13 11:25, , 13F
purpose 請不要拿 Pentium 4 這史上最爛的 CPU 做例子啦
05/13 11:25, 13F
→
05/13 11:26, , 14F
然後呢 intel 和 AMD 官方就有提供 Latency 表了
05/13 11:26, 14F
→
05/13 11:27, , 15F
而且新的 CPU 都會列出來
05/13 11:27, 15F
→
05/13 11:28, , 16F
不過我個人對於 AMD 的 FP 轉 INT 還是有疑問
05/13 11:28, 16F
→
05/13 11:28, , 17F
Latency 非常不穩定 會莫名其妙飆非常高
05/13 11:28, 17F
推
05/13 14:06, , 18F
小弟很外行，倒不是特地挑舊的 CPU 來講，只是 google 得
05/13 14:06, 18F
→
05/13 14:07, , 19F
知可以從 Intel 的那本 Optimization 手冊查到，不知道最
05/13 14:07, 19F
→
05/13 14:08, , 20F
新的資訊應該要到哪查，有人可告知嗎？謝謝 wow 大指正
05/13 14:08, 20F
→
05/13 14:09, , 21F
google 查 instruction latency site:intel.com 沒找到
05/13 14:09, 21F
→
05/13 14:10, , 22F
挑單一的 CPU 看 Datasheets, Design guides 的文件也沒有
05/13 14:10, 22F
推
05/13 20:23, , 23F
因為你查錯了 XD 而且了解 CPU 應該是從官方找資料的阿
05/13 20:23, 23F
→
05/13 20:24, , 24F
05/13 20:24, 24F
→
05/13 20:25, , 25F
噗 看來是一樣的 但是你還是得知道 CPUID 阿
05/13 20:25, 25F
→
05/13 20:26, , 26F
0F2x 是 Netburst 阿 其餘都是 06xx 正規 Pentium 2 血統
05/13 20:26, 26F
推
05/13 20:35, , 27F
真是抱歉阿 兩三年沒去看 Intel 的 PDF 都忘在長怎樣了
05/13 20:35, 27F
推
05/13 20:37, , 28F
wow 大小弟悟了，感謝
05/13 20:37, 28F
→
05/13 20:38, , 29F
之前太心急看到 Table C-16 以為就查完了，不知道往下拉
05/13 20:38, 29F
→
05/13 20:39, , 30F
三頁後又有個 Table C-16a 裡面有新版 CPU 的 IMUL 資料
05/13 20:39, 30F
‣ 更多 stupid0319 的文章
文章代碼(AID): #1FhUvwpU (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 stupid0319 的文章
文章代碼(AID): #1FhUvwpU (C_and_CPP)