為什麼這篇開根號用途鄉民發文收入到精華區：因為在開根號用途這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者scott90213 (剛好而已)看板C_and_CPP標題[問題] 開根號時間Fri Aug ...
要做一個開根號的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
→ dendrobium:把值先算好 08/26 12:20
→ loveme00835:不清楚所謂的"快"是多快, 這好主觀 (你這智妍控! 08/26 12:20
推 littleshan:你用C lib的sqrt搞不好是最快的 科科 08/26 12:29
→ littleshan:現在的compiler都可以直接把sqrt改成SSE2的sqrtsd指令 08/26 12:30
→ scott90213:array[4000]就是把值算好但是不合要求 08/26 12:39
→ loveme00835:為啥不合要求？連定義都不能定義？ 08/26 12:40
→ firejox:用inline也可以跟macro一樣快呀~ 08/26 12:42
→ scott90213:題目有說不要花時間鍵入4000個array table 08/26 12:42
→ scott90213:如果真得打完array[4000] 少說也要幾個小時 08/26 12:44
→ loveme00835:那才不到一秒...用mpl輸出到另一個原始碼檔, 你就有 08/26 12:44
→ james732:那就別用鍵的，程式一開始就自己先算好 XD 08/26 12:44
→ loveme00835:現成的全域陣列可用 08/26 12:44
→ loveme00835:"main.cpp" 改成 __FILE__ 也可 08/26 13:03
→ james732:板主那段程式碼只要跑0.032秒，完全不花時間 XDDD 08/26 13:04
→ scott90213:是針對函數來測速的 詳細可以參考我的上2篇文章 08/26 13:10
→ james732:執行時間更不用說啦，有什麼可以比查表法更快？ 08/26 13:11
→ scott90213:total = get_day_of_month(1,6) 執行一千萬次 08/26 13:12
→ scott90213:只要0.0X秒 08/26 13:16
→ scott90213:那是當然 但是查表還有分方法 用gobal就比在函數裡快 08/26 13:17
→ scott90213:用巨集或inline又會比一般函數快 08/26 13:17
→ james732:我剛剛跑板主的程式，改成一千萬次，不cout，0.016秒 08/26 13:18
→ scott90213:裡面空空如 什麼也沒做 不快也難 08/26 13:19
→ loveme00835:@_@ 不曉得原po點在哪 08/26 13:20
→ scott90213:推文參與討論得我都很感激 但是題目就是要求這樣啊 08/26 13:22
→ james732:總覺得好像有什麼誤會... 08/26 13:22
→ scott90213:就要求說不要做array 不要改main 但都推這類答案 08/26 13:23
→ james732:如果題目是「不要花費數小時時間鍵入4000個array table」 08/26 13:23
→ james732:我想板主並沒有違反這個要求啊...XD 08/26 13:24
→ james732:又沒說不可以建array，只叫你不要用打的 08/26 13:24
→ scott90213:可是我認為題目是只要我完成那個sqrt而以... 08/26 13:25
→ tropical72:我好奇這題目從哪來的？ 08/26 13:26
→ tropical72:要快、不能調用 sqrt、不能建 table，似乎只剩一方法, 08/26 13:26
→ tropical72:但會有缺點。 08/26 13:26
→ james732:我能想到的是公式解、查表解跟硬體解 XDD 08/26 13:26
→ scott90213:我這些題目是一個朋友叔叔韌體工程師出的 08/26 13:27
→ james732:韌體工程師說不定真的是要寫硬體解 08/26 13:29
→ scott90213:因為是韌體 所以我覺得不會是用道太多C++技巧的解法 08/26 13:30
→ scott90213:依照前面題目 都是幾行程式碼就可以達到 08/26 13:31
推 suhorng:如果是用在遊戲中,又要快,精度又不需要非常高,可能問這個: 08/26 13:33
→ tropical72:樓上那篇,現在已比 VC 開 O2 還慢了. 08/26 13:34
→ tropical72:但我也認為答案會是這個... XD 08/26 13:35
→ tropical72:似乎不像你說的,全都大量用了 loop.. 08/26 13:37
→ scott90213:我試看看 08/26 13:43
→ scott90213:不過他特別給0~4000 用意到底是? 08/26 13:55
→ tropical72:你可以參考 InvSqrt 那篇 magic number 怎麼來的,事實 08/26 13:58
→ tropical72:上最後是用暴力破才找到最好的值,我想給範圍應是 08/26 13:58
→ tropical72:縮短暴力破解所費時間,當然只是我一些推測,建議直接找 08/26 13:59
→ tropical72:你朋友的叔叔問比較快. 08/26 13:59
→ scott90213:樓上的我跑出來好像是錯的答案 08/26 14:48
→ angleevil:我有給參考網址,你試試看最後一個方法,如果ok,回覆一下 08/26 14:54
→ scott90213:OK但是 速度慢了10倍 而且給4000應該有用途 我再想想 08/26 15:17
→ angleevil:= =等等...你把你要測試的code給我,我測測看. 08/26 15:18
→ angleevil:其實t大有給類似東西 08/26 15:19
推 tropical72:嗯,我連實測結果都放了.. 08/26 15:22
→ tropical72:恕我忠懇的建議,別和compiler硬拼math.h，有時查表都查 08/26 15:23
→ tropical72:不過內建的函式,像是三角函式之類的... 08/26 15:23
→ angleevil:但是韌體好像沒有math,所以pow和sqrt都要自己寫 08/26 15:26
→ tropical72:若如果,似乎不該拿有math.h之compiler 做比較. 08/26 15:34
推 littleshan:看不懂原po為什麼如此堅持4000 08/26 15:44
→ littleshan:4000可能讓你有某些很妙的方法，也可能完全沒意義 08/26 15:45
推 littleshan:除非你想把這問題當作益智問答 08/26 15:49
推 ledia:550 個質數... 接受 array[550]; 嗎? XD 08/26 16:02
→ angleevil:= =說實話,原先po的那個code就ok了,速度跟sqrt差不多 08/26 16:17
→ angleevil:再來數值其實不算錯,那是誤差.我用迴圈測1~4000000 08/26 16:18
→ angleevil:也沒太大差異.原po把測試數據放上來看看吧 08/26 16:19
→ angleevil:只是0要特別處理,如果是用vc的話,原po其實要測試realse 08/26 16:44
推 ericinttu:又沒講精準度要到哪一位... 08/26 16:55
推 ericinttu:total = get_day_of_month(1,6) 執行一千萬次 08/26 16:57
→ ericinttu: ↑ 你確定電腦有照實跑 一千萬次? 08/26 16:57
→ scott90213:1億次時間大約是10倍 應該是有 08/26 17:03
推 ericinttu:你的回答與證實方法就是這樣? 08/26 17:08
→ tropical72:他的驗證不是不好,而是沒把環境、參數註明清楚，大忌。 08/26 17:46
→ tropical72:據上次回答的經驗,應是用 VS compiler,會差到十倍,是因 08/26 17:47
→ tropical72:他在 Debug mode 下跑.開 Release O2 後結果都一樣. 08/26 17:47
→ angleevil:=..=T大好嚴格 08/26 17:48
→ tropical72:看 asm code 會發現那些都被 opt. 掉. 08/26 17:49
→ tropical72:再討論下去應該又回歸到,要不要信任 Opt. 能力之類的.. 08/26 17:54
→ ericinttu:追求極限就要有相對應的嚴謹度, 要不然一堆空包彈怎行? 08/26 18:03
→ scott90213:@Littlesahn 如果題目只是要求速度何必給一個範圍? 08/26 18:12
→ scott90213:直接讓你輸入任意數就可以了，所以我想4000是有用意的 08/26 18:13
→ tropical72:我以為4000的意義在於建表,不能建表4000就沒意義 。 08/26 18:17
→ james732:我也以為是建表，想說4000筆的表格實在不算什麼 08/26 18:27
→ scott90213:但是建表除了 自己輸入 一樣要用sqrt算好再放進去吧 08/26 19:17
→ ericinttu:F1賽車比賽時, 大家會等你沒裝滿油而多的秒數嗎? 08/26 19:21
→ scott90213:其實我也是覺得一定和查表(之類)有關 不然不可能 08/26 19:33
→ scott90213:但是表的建立方法 除了手動鍵入之外 讓程式自己跑表出 08/26 19:35
→ scott90213:好像也是要用math.h 或是 自己寫的sqrt 08/26 19:37
→ scott90213:然後才在題目中的sqrt函數中 取值出來 好像有點怪 08/26 19:38
→ kikiqqp:如果是韌體，有限空間下有時不會把4000全建表 08/27 10:39
→ kikiqqp:而是見個大概然後用演算法算出來，但一定不準！ 08/27 10:40
→ kikiqqp:(ASM不到幾百行要多精準) 08/27 10:40
→ kikiqqp:4000才12bit，以16bit來計算，PIC16F約110cycles以下 08/27 10:47