# 2016q3 Homework1 (clz) contributed by <`ChenYi`> ### 先驗證一下結果是不是正確的 在FB課程討論區裡有看到，老師給的程式碼有問題，先驗證一下各個版本 #### Iteration , Binary-search , Byte-shift ``` ./a.out 16 27 27 27 ``` 正確不需要更改 #### Recursive 這部份是有問題的 修正一下(參考[黃鏡清的筆記](/s/Byyd3nua)裡的方法) ``` uint32_t count = 16; uint32_t mask = 0xFFFFFFFF; int clz(uint32_t x) { int result; // shift upper half down, rest is filled up with 0s uint16_t upper = (x >> count); // mask upper half away mask >>= count; uint16_t lower = (x & mask); // stopping condition if(count == 1) { return !(x >> 1); } // shifting count and go into recursive count >>= 1; result = upper ? clz(upper) : (count << 1) + clz(lower); count <<= 1; return result; } ``` 想一想，能不能更快呢？ 試著用tail recursion去挑戰 ``` int clz_tail_recursive(uint32_t x , int final_result) { if(!x) return final_result; return clz_tail_recursive( (x >> 1) , final_result-1 ); } int main(...) { ... result = clz_tail_recursive(input , 32); ... } ``` :::info Tail recursion 與一般的 recursive function不同的地方是，tail recursion可以減少stack的使用，增進效率 ::: 節錄自 [Tail call (tail-recursive) ](angelonotes.blogspot.tw/2011/03/tail-call-tail-recursive.html) :::warning 該頁面的程式碼有使用inline，但我認為那是沒意義的，如果激進一點放入force inline的話執行時應該會出錯，理由是compiler根本不知道你要執行幾次，那請問要怎麼展開呢？所以應該還是會有branch去某區塊的行為存在。 ::: 測試 ``` ./clz_test 268435456 3 3 3 3 3 ``` 全正確！！接下來就是效能問題了 ### 效能測試 這邊使用 clock_gettime() 來作為時間的測量 CLOCK_ID flag使用 CLOCK_MONOTONIC_RAW　（不受NTP影響的單調遞增） :::info CLOCK_MONOTONIC_RAW (since Linux 2.6.28; Linux-specific) ____Similar to CLOCK_MONOTONIC, but provides access to a raw ____hardware-based time that is not subject to NTP adjustments or ____the incremental adjustments performed by adjtime(3). ::: from http://man7.org/linux/man-pages/man2/clock_gettime.2.html 也可以利用在terminal輸入以下指令來找到我們要的文件 ``` man clock_gettime ``` 恩ˊ~ˋ makefile有陷阱R 一次跑太多會炸裂RRR 還在找原因 先畫圖 ``` run: for i in `seq 0 1 4294967295`; do \ ./clz_test $$i; \ done ``` 想了一下... 應該是硬碟吃不下輸出就炸裂了 假設一次輸出100byte的話 * 4294967296次 ==> 214GB左右 ==> 我的SSD只有240GB-自己的資料 ==>恩....XD 換成取個10w就好QQ ![](https://i.imgur.com/hgyI8fe.png) 我寫的Tail recursion完全不行阿 * 我想原因是還要長stack巴，這個算法跟單純的iteration基本上是一樣的 * 但由於recursive會一直call function所以多了個function call的instructions * 這樣的結果會導致，同樣的運算次數下，recursion的速度會低於iteration * 所以可以看到最快的兩個都是iteration的，recursive是在比慢的 * 而黃鏡清同學的recursion又是採用binary search的作法 * 可以看到他的recursion版本是比我的來的快不少 * 另外一點值得注意的事，未做演算法最佳化的recursion點的分佈幾乎都是在iteration的上面 * 也就是說，真的就是多了那些function call的instruction而導致的 #### Recursion少數的好處大概是 * 好讀 * code size小 ### clz的用途 - 區分significant digits - 科學計算中，常常有許多的不同大小的數字 - 而 clz 可以幫忙減少不必要的計算 - * 用在資料壓縮上 * 若已知，資料 bits 數很多，只有幾個奇異點時，可以利用 clz 來幫助壓縮 真要列的話真的很多... 倒不如直接google書籍看看有什麼用途吧:[連結](https://www.google.com.tw/search?client=ubuntu&channel=fs&biw=1920&bih=956&tbm=bks&q=use+of++leading+zero+count&oq=use+of++leading+zero+count&gs_l=serp.3...3781.471536.0.471742.4.4.0.0.0.0.113.273.3j1.4.0....0...1c.1.64.serp..0.0.0.5C6YS13eFig) ### Reference * [作業網站](https://hackmd.io/s/B1LHefQ6) * [FB課程社團](https://www.facebook.com/groups/system.software2016/) * [黃鏡清的筆記](https://hackmd.io/s/Byyd3nua) * [Recursion vs Iteration](http://stackoverflow.com/questions/15688019/recursion-versus-iteration) * [what is the benefit of using or creating recursive functions in java?](http://stackoverflow.com/questions/8573116/what-is-the-benefit-of-using-or-creating-recursive-functions-in-java)