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

[問題] 開根號

看板C_and_CPP (C/C++)作者 (剛好而已)時間13年前 (2011/08/26 12:05), 編輯推噓9(9推 0噓 92→)
留言101則, 12人參與, 最新討論串1/1
要做一個開根號的function，速度要跟之前的get_day_of_month(註1)一樣快，至少接近 參數的有效範圍0~4000 已給的程式碼: inline float sqrt(int num) { . . . . } int main(void) { flaot ans; ans= sqrt(58); cout<<ans<<endl; } 輸出結果 7.61..... 題目要求 main 中不做任何修改或增加程式碼 不要呼叫c lib的sqrt(); (一定慢) 不要花費數小時時間鍵入4000個array table (註1) get_day_of_month(int start_ month , int end_month); 是一個傳入 起迄月份得總日數的function 速度方面我當時是用 gobal value 設累加日數array，減少每次函數配置array時間 再用#define 巨集來取代get_day_of_month 比使用一個函數並在其中設array 快了30倍 ========================================================================== 不使用lib sqrt的寫法我寫過，google也很多 但是都要用到很多迴圈，這樣一來速度一定不可能快 (是吧?) 題目又有特別提說不要用array[4000](雖然我也不會這麼做) 又程式有特別給了參數範圍，並非一般的開根號程式，加上有要求速度 請問各位對於這題的看法是? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.0.34.42
→
08/26 12:20, , 1F
把值先算好
08/26 12:20, 1F
→
08/26 12:20, , 2F
不清楚所謂的"快"是多快, 這好主觀 (你這智妍控!
08/26 12:20, 2F
推
08/26 12:29, , 3F
你用C lib的sqrt搞不好是最快的 科科
08/26 12:29, 3F
→
08/26 12:30, , 4F
現在的compiler都可以直接把sqrt改成SSE2的sqrtsd指令
08/26 12:30, 4F
→
08/26 12:39, , 5F
array[4000]就是把值算好但是不合要求
08/26 12:39, 5F
→
08/26 12:40, , 6F
為啥不合要求？連定義都不能定義？
08/26 12:40, 6F
→
08/26 12:42, , 7F
用inline也可以跟macro一樣快呀~
08/26 12:42, 7F
→
08/26 12:42, , 8F
題目有說不要花時間鍵入4000個array table
08/26 12:42, 8F
→
08/26 12:44, , 9F
如果真得打完array[4000] 少說也要幾個小時
08/26 12:44, 9F
→
08/26 12:44, , 10F
那才不到一秒...用mpl輸出到另一個原始碼檔, 你就有
08/26 12:44, 10F
→
08/26 12:44, , 11F
那就別用鍵的，程式一開始就自己先算好 XD
08/26 12:44, 11F
→
08/26 12:44, , 12F
現成的全域陣列可用
08/26 12:44, 12F
→
08/26 12:59, , 13F
http://codepad.org/oAnR0ru0 把main.cpp拿來編就好
08/26 12:59, 13F
→
08/26 13:03, , 14F
"main.cpp" 改成 __FILE__ 也可
08/26 13:03, 14F
→
08/26 13:04, , 15F
板主那段程式碼只要跑0.032秒，完全不花時間 XDDD
08/26 13:04, 15F
→
08/26 13:10, , 16F
是針對函數來測速的 詳細可以參考我的上2篇文章
08/26 13:10, 16F
→
08/26 13:11, , 17F
執行時間更不用說啦，有什麼可以比查表法更快？
08/26 13:11, 17F
→
08/26 13:12, , 18F
total = get_day_of_month(1,6) 執行一千萬次
08/26 13:12, 18F
→
08/26 13:16, , 19F
只要0.0X秒
08/26 13:16, 19F
→
08/26 13:17, , 20F
那是當然 但是查表還有分方法 用gobal就比在函數裡快
08/26 13:17, 20F
→
08/26 13:17, , 21F
用巨集或inline又會比一般函數快
08/26 13:17, 21F
→
08/26 13:18, , 22F
我剛剛跑板主的程式，改成一千萬次，不cout，0.016秒
08/26 13:18, 22F
→
08/26 13:19, , 23F
裡面空空如 什麼也沒做 不快也難
08/26 13:19, 23F
→
08/26 13:20, , 24F
@_@ 不曉得原po點在哪
08/26 13:20, 24F
→
08/26 13:22, , 25F
推文參與討論得我都很感激 但是題目就是要求這樣啊
08/26 13:22, 25F
→
08/26 13:22, , 26F
總覺得好像有什麼誤會...
08/26 13:22, 26F
→
08/26 13:23, , 27F
就要求說不要做array 不要改main 但都推這類答案
08/26 13:23, 27F
→
08/26 13:23, , 28F
如果題目是「不要花費數小時時間鍵入4000個array table」
08/26 13:23, 28F
→
08/26 13:24, , 29F
我想板主並沒有違反這個要求啊...XD
08/26 13:24, 29F
→
08/26 13:24, , 30F
又沒說不可以建array，只叫你不要用打的
08/26 13:24, 30F
→
08/26 13:25, , 31F
可是我認為題目是只要我完成那個sqrt而以...
08/26 13:25, 31F
→
08/26 13:26, , 32F
我好奇這題目從哪來的？
08/26 13:26, 32F
→
08/26 13:26, , 33F
要快、不能調用 sqrt、不能建 table，似乎只剩一方法,
08/26 13:26, 33F
→
08/26 13:26, , 34F
但會有缺點。
08/26 13:26, 34F
→
08/26 13:26, , 35F
我能想到的是公式解、查表解跟硬體解 XDD
08/26 13:26, 35F
→
08/26 13:27, , 36F
我這些題目是一個朋友叔叔韌體工程師出的
08/26 13:27, 36F
→
08/26 13:29, , 37F
韌體工程師說不定真的是要寫硬體解
08/26 13:29, 37F
→
08/26 13:30, , 38F
因為是韌體 所以我覺得不會是用道太多C++技巧的解法
08/26 13:30, 38F
→
08/26 13:31, , 39F
依照前面題目 都是幾行程式碼就可以達到
08/26 13:31, 39F
還有 22 則推文
→
08/26 15:23, , 62F
恕我忠懇的建議,別和compiler硬拼math.h，有時查表都查
08/26 15:23, 62F
→
08/26 15:23, , 63F
不過內建的函式,像是三角函式之類的...
08/26 15:23, 63F
→
08/26 15:26, , 64F
但是韌體好像沒有math,所以pow和sqrt都要自己寫
08/26 15:26, 64F
→
08/26 15:34, , 65F
若如果,似乎不該拿有math.h之compiler 做比較.
08/26 15:34, 65F
推
08/26 15:44, , 66F
看不懂原po為什麼如此堅持4000
08/26 15:44, 66F
→
08/26 15:45, , 67F
4000可能讓你有某些很妙的方法，也可能完全沒意義
08/26 15:45, 67F
推
08/26 15:49, , 68F
除非你想把這問題當作益智問答
08/26 15:49, 68F
推
08/26 16:02, , 69F
550 個質數... 接受 array[550]; 嗎? XD
08/26 16:02, 69F
→
08/26 16:17, , 70F
= =說實話,原先po的那個code就ok了,速度跟sqrt差不多
08/26 16:17, 70F
→
08/26 16:18, , 71F
再來數值其實不算錯,那是誤差.我用迴圈測1~4000000
08/26 16:18, 71F
→
08/26 16:19, , 72F
也沒太大差異.原po把測試數據放上來看看吧
08/26 16:19, 72F
→
08/26 16:44, , 73F
只是0要特別處理,如果是用vc的話,原po其實要測試realse
08/26 16:44, 73F
推
08/26 16:55, , 74F
又沒講精準度要到哪一位...
08/26 16:55, 74F
推
08/26 16:57, , 75F
total = get_day_of_month(1,6) 執行一千萬次
08/26 16:57, 75F
→
08/26 16:57, , 76F
↑ 你確定電腦有照實跑 一千萬次?
08/26 16:57, 76F
→
08/26 17:03, , 77F
1億次時間大約是10倍 應該是有
08/26 17:03, 77F
推
08/26 17:08, , 78F
你的回答與證實方法就是這樣?
08/26 17:08, 78F
→
08/26 17:46, , 79F
他的驗證不是不好,而是沒把環境、參數註明清楚，大忌。
08/26 17:46, 79F
→
08/26 17:47, , 80F
據上次回答的經驗,應是用 VS compiler,會差到十倍,是因
08/26 17:47, 80F
→
08/26 17:47, , 81F
他在 Debug mode 下跑.開 Release O2 後結果都一樣.
08/26 17:47, 81F
→
08/26 17:47, , 82F
http://codepad.org/WH6f3Ezn get_day_of_month...
08/26 17:47, 82F
→
08/26 17:48, , 83F
=..=T大好嚴格
08/26 17:48, 83F
→
08/26 17:49, , 84F
看 asm code 會發現那些都被 opt. 掉.
08/26 17:49, 84F
→
08/26 17:54, , 85F
再討論下去應該又回歸到,要不要信任 Opt. 能力之類的..
08/26 17:54, 85F
→
08/26 18:03, , 86F
追求極限就要有相對應的嚴謹度, 要不然一堆空包彈怎行?
08/26 18:03, 86F
→
08/26 18:12, , 87F
@Littlesahn 如果題目只是要求速度何必給一個範圍?
08/26 18:12, 87F
→
08/26 18:13, , 88F
直接讓你輸入任意數就可以了，所以我想4000是有用意的
08/26 18:13, 88F
→
08/26 18:17, , 89F
我以為4000的意義在於建表,不能建表4000就沒意義 。
08/26 18:17, 89F
→
08/26 18:27, , 90F
我也以為是建表，想說4000筆的表格實在不算什麼
08/26 18:27, 90F
→
08/26 19:17, , 91F
但是建表除了 自己輸入 一樣要用sqrt算好再放進去吧
08/26 19:17, 91F
→
08/26 19:21, , 92F
F1賽車比賽時, 大家會等你沒裝滿油而多的秒數嗎?
08/26 19:21, 92F
→
08/26 19:33, , 93F
其實我也是覺得一定和查表(之類)有關 不然不可能
08/26 19:33, 93F
→
08/26 19:35, , 94F
但是表的建立方法 除了手動鍵入之外 讓程式自己跑表出
08/26 19:35, 94F
→
08/26 19:37, , 95F
好像也是要用math.h 或是 自己寫的sqrt
08/26 19:37, 95F
→
08/26 19:38, , 96F
然後才在題目中的sqrt函數中 取值出來 好像有點怪
08/26 19:38, 96F
→
08/27 10:39, , 97F
如果是韌體，有限空間下有時不會把4000全建表
08/27 10:39, 97F
→
08/27 10:40, , 98F
而是見個大概然後用演算法算出來，但一定不準！
08/27 10:40, 98F
→
08/27 10:40, , 99F
(ASM不到幾百行要多精準)
08/27 10:40, 99F
→
08/27 10:47, , 100F
4000才12bit，以16bit來計算，PIC16F約110cycles以下
08/27 10:47, 100F
→
08/27 10:48, , 101F
基於http://goo.gl/Gkqx8 發展
08/27 10:48, 101F
‣ 更多 scott90213 的文章
文章代碼(AID): #1ELnk3SC (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 scott90213 的文章
文章代碼(AID): #1ELnk3SC (C_and_CPP)