# 2016q3 Homework1 (clz)
contributed by <`CheHsuan`>
## 目標
閱讀 重新理解數值 裡頭關於 count leading zero (clz) 的描述，設計實驗，比較 32-bit 數值對以下實做的效能差異：
* recursive version
* iteration version
* binary search technique
* byte-shift version
* Harley’s algorithm
## 程式碼分析
```c
uint8_t clz(uint32_t x)
{
/* shift upper half down, rest is filled up with 0s */
uint16_t upper = (x >> 16);
// mask upper half away
uint16_t lower = (x & 0xFFFF);
return upper ? clz(upper) : 16 + clz(lower);
}
```
老師給的版本有一個問題，就是沒有中止條件使程式跳出recursive call,所以必須改寫一下
```c
uint8_t clz_binary_recursive(uint32_t x, int shift)
{
if (x == 0)
return 32;
if (shift == 0)
return 0;
if (x <= (0xFFFFFFFF >> shift))
return shift + clz_binary_recursive(x << shift, shift / 2);
return clz_binary_recursive(x, shift / 2);
}
```
這個寫法是類似binary search的方式，理論上時間複雜度為O(logN)
## Recursive Version
```c
uint8_t clz_recursive(uint32_t x)
{
return x ? clz_recursive(x>>1) - 1 : 32;
}
```
但這個版本的時間複雜度是O(N)，而且比iteration版本的clz多出了function call的成本
## Iteration Version
```c
uint8_t clz_iteration(uint32_t x)
{
int count = 0;
while(x != 0) {
x = x >> 1;
count++;
}
return 32 - count;
}
```
時間複雜度為O(N)
## Binary Search Technique
此版本我是參考老師[重新理解數值](https://hackmd.io/s/SkKZBXZT#count-leading-zero)裡面的作法，從這個算法來看，時間複雜度為O(logN)
## Byte-shift Version
一樣參考[重新理解數值](https://hackmd.io/s/SkKZBXZT#count-leading-zero)，這版本的算法的時間複雜度和binary search technique一樣為時間複雜度為O(logN)，只少了一次if比較，不過應該不會相差太多
## Harley's Algorithm
```c
static uint8_t Table[64] = {
32, 31, 0, 16, 0, 30, 3, 0, 15, 0, 0, 0, 29, 10, 2, 0,
0, 0, 12, 14, 21, 0, 19, 0, 0, 28, 0, 25, 0, 9, 1, 0,
17, 0, 4, 0, 0, 0, 11, 0, 13, 22, 20, 0, 26, 0, 0, 18,
5, 0, 0, 23, 0, 27, 0, 6, 0, 24, 7, 0, 8, 0, 0, 0};
```
修改table內數字,OK成功
## 時間量測方法
參考compute-pi作法，使用`clock_gettime()`函式
man一下
`int clock_gettime(clockid_t clk_id, struct timespec *tp);`
:::info
The clk_id argument is the identifier of the particular clock on which to act. A clock may be system-wide and hence visible for all processes, or per-process if it measures time only within a single process.
:::
### CLOCK_REALTIME
在manual裡面指出，clock_gettime可以指定量測system-wide time,也就是wall clock time，因此會因機器假如同時運行其他程式的話，會影響到時間量測的準確度，所以我們不考量使用這方法
### CLOCK_MONOTONIC和CLOCK_MONOTONIC_RAW
利用系統的jiffies來計算時間，當發生time interrupt時，便把紀錄+1
### CLOCK_PROCESS_CPUTIME_ID
計算整個process在kernel space和user space所花費的時間，假如是多執行緒，會將每個thread所花的時間加起來
### CLOCK_THREAD_CPUTIME_ID
計算單個thread在kernel space和user space所花費的時間
### timespec結構
```c
struct timespec {
time_t tv_sec; /* seconds */
long tv_nsec; /* nanoseconds */
};
```
## 實驗數據
這次的實驗環境是計算0X0~0XFFFF的clz，每個方法都跑100次，數據如下
從圖中可以看出兩件事情
1. 執行時間會有振盪的現象
2. iteration和recursive雖然都是O(N)，但iteration因為少了call function的overhead，所以執行時間平均來說較recursive少
再把跑的次數拉大一點來看，一樣是0X0~0XFFFF各跑5000次
針對32 bits unsigned integer的極值(0~4294967296)各跑1次
演算法的重要性！recursive的版本花到487.10秒，也就是八分鐘，夠吃完一碗泡麵了 :smile:
||recursive|binary recursive|iteration|byte-shift|binary search technique
| :------ | ------: | ------: |------: | ------: | :------: |
|0| 486.492851| 110.374512|264.005961| 22.064742| 21.832292
|1| 485.631612| 110.86067| 263.157863| 22.039492| 21.640222
OK，把recursive的版本用O(N)和O(logN)的方法來比較一下，執行時間相差了約4倍(486：110)
而同樣都是O(logN)的算法，recusive function call和one function call with multiple if-else的方法來比較，時間也差了大概5倍(110：22)
加入Harley
最後總測試
## 應用實例
[WIP]
Sign in with Wallet
Connect another wallet