› 看板 C_and_CPP 關於我們 聯絡資訊
作者stupid0319 (徵女友)
看板C_and_CPP
標題Re: [問題] 不用除法，算出整數除以五的商
時間Sat May 12 13:00:39 2012
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
→ yauhh:你的意思是說把除法換成一些乘法和指數運算嗎? 05/12 13:12
→ yauhh:不過乘法的時脈也很多. 05/12 13:13
→ stupid0319:我只是幫purpose大補充一下他要表達的內容@@ 05/12 13:17
推 purpose:除法換成 multiply shift，在 x86 下是比除法快 05/12 13:19
推 littleshan:現代的cpu乘法其實很快喔 latency大約3~4個cycle而已 05/12 23:00
→ littleshan:相較之下除法至少26個cycle起跳 05/12 23:02
推 purpose:Intel 的 Optimization Reference Manual 附錄 C 表 C-13 05/12 23:36
→ purpose:是寫 IMUL 的 Latency 為 15-18 耶，沒這麼快吧？？ 05/12 23:37
推 purpose:http://i.imgur.com/sdU6Y.png 資料來源 05/12 23:40
推 littleshan: http://gmplib.org/~tege/x86-timing.pdf 05/13 00:02
推 yauhh:那就可以將一個除法替換為少於七倍的乘法 05/13 00:51
推 purpose:好像跟多核心有關？總之謝謝 littleshan 大解惑，感謝 05/13 03:06
推 wowtiger:purpose 請不要拿 Pentium 4 這史上最爛的 CPU 做例子啦 05/13 11:25
→ wowtiger:然後呢 intel 和 AMD 官方就有提供 Latency 表了 05/13 11:26
→ wowtiger:而且新的 CPU 都會列出來 05/13 11:27
→ wowtiger:不過我個人對於 AMD 的 FP 轉 INT 還是有疑問 05/13 11:28
→ wowtiger:Latency 非常不穩定 會莫名其妙飆非常高 05/13 11:28
推 purpose:小弟很外行，倒不是特地挑舊的 CPU 來講，只是 google 得 05/13 14:06
→ purpose:知可以從 Intel 的那本 Optimization 手冊查到，不知道最 05/13 14:07
→ purpose:新的資訊應該要到哪查，有人可告知嗎？謝謝 wow 大指正 05/13 14:08
→ purpose:google 查 instruction latency site:intel.com 沒找到 05/13 14:09
→ purpose:挑單一的 CPU 看 Datasheets, Design guides 的文件也沒有 05/13 14:10
推 wowtiger:因為你查錯了 XD 而且了解 CPU 應該是從官方找資料的阿 05/13 20:23
→ wowtiger:http://tinyurl.com/7ty2lsx 05/13 20:24
→ wowtiger:噗 看來是一樣的 但是你還是得知道 CPUID 阿 05/13 20:25
→ wowtiger:0F2x 是 Netburst 阿 其餘都是 06xx 正規 Pentium 2 血統 05/13 20:26
推 wowtiger:真是抱歉阿 兩三年沒去看 Intel 的 PDF 都忘在長怎樣了 05/13 20:35
推 purpose:wow 大小弟悟了，感謝 05/13 20:37
→ purpose:之前太心急看到 Table C-16 以為就查完了，不知道往下拉 05/13 20:38
→ purpose:三頁後又有個 Table C-16a 裡面有新版 CPU 的 IMUL 資料 05/13 20:39