# 2024q1 Homework4 (quiz3+4)
contributed by < `shlin41` >
---
## 第三週測驗題
---
### 測驗一
#### 運作原理
原理是將欲求平方根的 $N^2$ 拆成：
\begin{aligned}
N^2 = (a_n + a_{n-1} + a_{n-2} + ... + a_0)^2,\ where\ a_m = 2^m\ or\ 0
\end{aligned}
進一步擴充:
\begin{aligned}
Def: P_m \triangleq a_n + a_{n-1} + a_{n-2} + ... + a_m
\end{aligned}
則可以得到:
\begin{aligned}
P_m^2 &= (a_n + a_{n-1} + a_{n-2} + ... + a_{m+1} + a_m)^2\\
&= (P_{m+1} + a_m)^2\\
&= P_{m+1}^2 + 2 \times P_{m+1} \times a_m + a_m^2\\
&= P_{m+1}^2 + (2P_{m+1} + a_m)a_m\\
&= P_{m+1}^2 + Y_m\\
\\
&with\ Y_m \triangleq (2P_{m+1} + a_m)a_m
\end{aligned}
我們的目的是從試出所有 $a_m$， $a_m=2^m$or $a_m=0$。從 $m=n$ 一路試到 $m=0$，而求得 $a_m$ 只要試驗 $P_m^2 \leq N^2$ 是否成立。但是計算 $N^2 - P_m^2 \geq 0$ 成本太高，所以在這個基礎上，希望可以找另外一種比較方法。
先定義:
\begin{aligned}
Def: X_m \triangleq N^2 - P_m^2
\end{aligned}
則可以得到:
\begin{aligned}
X_m &= N^2 - P_m^2\\
&= N^2 - (P_{m+1}^2 + Y_m)\\
&= N^2 - P_{m+1}^2 - Y_m\\
&= X_{m+1} - Y_m
\end{aligned}
再對 $Y_m$ 進行處理:
* 定義:
\begin{aligned}
c_m &\triangleq P_{m+1} \times 2^{m+1}\\
d_m &\triangleq (2^m)^2
\end{aligned}
* 然後我們可以改寫 $Y_m$:
\begin{aligned}
Y_m &= \begin{cases}
(2P_{m+1} + a_m)a_m &\text{ if } a_m=2^m \\
0 &\text{ if } a_m=0 \\
\end{cases}\\
&= \begin{cases}
c_m + d_m &\text{ if } a_m=2^m \\
0 &\text{ if } a_m=0 \\
\end{cases}
\end{aligned}
* 再改寫 $c_m$ 和 $d_m$ 成遞迴式:
\begin{aligned}
&c_{m-1} = P_m \times 2^m
= (P_{m+1} + a_m) \times 2^m
= P_{m+1}2^m + a_m2^m
= \begin{cases}
c_m/2 + d_m &\text{ if } a_m=2^m\\
c_m/2 &\text{ if } a_m=0
\end{cases}\\
&d_{m-1} = d_m/4
\end{aligned}
結合上述方法撰寫演算法來尋求 $a_n + a_{n-1}+...+a_0$，假設從 $a_n$ 開始往下試。
因為是從 $a_n$ 開始，所以：
* $X_{n+1} = N$
* $n$ 是最大的位數，使得 $a_n^2 = (2^n)^2 = d_n^2 = 4^n \leq N^2$，所以用 $d_n$ 迴圈逼近
* $c_n = 0$
`int m` 對應上述理論中的 $d_m$，由於首項 $d_n = (2^n)^2 = 2^{2n}$，可知指數項是 2n，所以程式中的 `& ~1UL` 是為了取偶數
`int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL)`
#### ffs / fls 取代 __builtin_clz
用 `fls()` 會相對容易，但是 C POSIX library 只有 `ffs()`。因此直接借用 linux-kernel 原始碼中的 `__fls()`。
查找過程中發現 `__fls()` 有分成硬體實做與軟體實做
* 硬體實做以 x86 為例:
```cpp
static __always_inline unsigned long __fls(unsigned long word) {
asm("bsr %1,%0" : "=r"(word) : "rm"(word));
return word;
}
```
* 軟體實做如下:
```cpp
#define BITS_PER_LONG 64
static __always_inline unsigned long __fls(unsigned long word) {
int num = BITS_PER_LONG - 1;
#if BITS_PER_LONG == 64
if (!(word & (~0ul << 32))) {
num -= 32;
word <<= 32;
}
#endif
if (!(word & (~0ul << (BITS_PER_LONG - 16)))) {
num -= 16;
word <<= 16;
}
if (!(word & (~0ul << (BITS_PER_LONG - 8)))) {
num -= 8;
word <<= 8;
}
if (!(word & (~0ul << (BITS_PER_LONG - 4)))) {
num -= 4;
word <<= 4;
}
if (!(word & (~0ul << (BITS_PER_LONG - 2)))) {
num -= 2;
word <<= 2;
}
if (!(word & (~0ul << (BITS_PER_LONG - 1))))
num -= 1;
return num;
}
```
取代部份
```diff
-- for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
++ for (int m = 1UL << (__fls(x) & ~1UL); m; m >>= 2) {
```
#### Linux 核心原始程式碼找出對整數進行平方根運算的程式碼
[TODO]
#### 嘗試撰寫更快的整數開平分根運算程式
[TODO]
---
### 測驗二
#### 運作原理
題目已經證明：假設我目標的最大數是 $n$ ， $l$ 則是比 $n$ 還要小的非負整數。假設 $n = ab$ ($a$ 是十位數 $b$ 是個位數)，且 $l = cd$ ($c$ 是十位數，$d$ 是個位數)，則只要以 $n$ 算出來的除數 $t$，在 $\dfrac{n}{t}$ 後能保持在精確度內，則 $l$ 除以該除數 $t$ 仍然會在精確度內。
我們的目標 `n = UINT_MAX = 4294967295`，一樣是要找出 $t = \dfrac{a}{2^N}$，並滿足下式
\begin{aligned}
429496729.5 \leq \dfrac{4294967295}{t} \leq 429496729.59
\Rightarrow 9.999999997904524 \leq t \leq 10
\end{aligned}
整段程式還看不懂:
```cpp=
#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
uint32_t q = (x >> 4) + x;
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
*div = (q >> 3);
*mod = in - ((q & ~0x7) + (*div << 1));
}
```
* line 4 ~ 12: 應該就是模擬 $\dfrac{in}{t} = \dfrac{in \times a}{2^N}$
* 具體怎麼做還看不出來
* 小實驗: `(in | 1)` 改成 `(in)` 的話，答案會在 20 的倍數的 `in` 出錯
* line13: `*mod = in - *dev * 10`
* 其中 `q & ~0x7 = *div << 3 = *div * 8`
#### 比較 CPU 週期數量
[TODO]
#### % 9 (modulo 9) 和 % 5 (modulo 5) 程式碼
[TODO]
---
### 測驗三
#### ilog2() 運作原理
答案的部份
* AAAA = $2^{16} = 32768$
* BBBB = $2^8 = 64$
* CCCC = $2^4 = 16$
* 程式少一個 while (i >= 4)
* DDDD = v | 1
整個程式的目標是找出最開頭的 `bit = 1` 的位置。作法是使用二分搜尋法。
解釋第一個 while:
輸入是一個 32 個位元的無號整數 `i`，分成前 16 位元和後 16 位元。如果 $i \geq 2^{16}$，則表示前 16 位元有 `bit = 1` 存在。所以 result += 16，並且把原數字 `i >> 16`，繼續看前 16 位元。反之，如果 $i < 2^{16}$，則表示前 16 位元都是 0。所以 result 保持不變，繼續看後 16 位元。
其他 while 比照處理。
#### 在 Linux 核心原始程式碼找出 log2 的相關程式碼
[TODO]
---
### 測驗四
#### 運作原理
概念上還是
\begin{aligned}
S_t = \begin{cases}
Y_0 &\text{ if } t = 0\\
\alpha Y_t + (1-\alpha) S_{t-1}&\text{ if } t > 0
\end{cases}\\
\end{aligned}
差別在於存 internal 時，會把 $val \times 2^{factor}$ 後，再存入。讀取平均值時，會把 $\frac{internal}{2^{factor}}$ 後，再讀出。
解析這一段：
```cpp
avg->internal = (((avg->internal << avg->weight) - avg->internal) + (val << avg->factor)) >> avg->weight;
```
上式可改寫為
```cpp
unsigned long S = avg->internal;
unsigned long loga = avg->weight;
unsigned long logf = avg->factor;
S = ((S << loga) - S) >> loga + (val << logf) >> loga;
= (S - S >> loga) + (val << logf) >> loga;
= S * (1 - 1 >> loga) + (val << logf) >> loga;
/* Note: "1 >> loga" is alpha */
```
至於為什麼要引入 factor，我尚未了解其目的。
#### 在 Linux 核心原始程式碼找出 EWMA 的相關程式碼
[TODO]
---
### 測驗五
#### 運作原理
答案的部份: GGGG = 1
程式的最後部份
```cpp
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;
```
等於
```cpp
shift = (x > 0x3) << 1;
x >>= shift;
r |= shift;
shift = (x > 0x1) << 0;
x >>= shift;
r |= shift;
return r + 1;
```
只是把 $2^0$ 的 shift 部份補上。程式的概念上和測驗三是一樣的。
#### 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
原程式在 `ceil_ilog2(1) = 1` 且 `ceil_ilog2(0) = 32` 為錯誤值。正確的`ceil_ilog2(1) = 0` 且 `ceil_ilog2(0)` 應該是沒有定義。因此在 `x == 0` 自行定義回傳值為 0。程式碼改進如下：
```diff
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
+ uint32_t mask = ((x > 1) << 5) | ((x > 1) << 4) | ((x > 1) << 3) |
+ ((x > 1) << 2) | ((x > 1) << 1) | (x > 1);
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
- return (r | shift | x > 1) + 1;
+ return ((r | shift | x > 1) + 1) & mask;
}
```
使用一個 `mask`，在 `x <= 1` 時， `mask = 0x00000000`，函式回傳 0。`x > 1` 時，`mask = 0x0000003f`，函式回傳舊有的值。
`mask = 0x0000003f` 是因為函式回傳值最大為 $2^5 = 32$。
#### 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合
[TODO]
---
## 第四週測驗題
---
### 測驗一
#### 運作原理
答案的部份: AAAA = 1
運作原理已在題目講解清楚說明。
#### LeetCode 477
```cpp
int totalHammingDistance(int* nums, int numsSize) {
int ans = 0;
for(int i = 0; i < 32; i++) {
int zeros = 0;
int ones = 0;
unsigned int mask = 1U << i;
for(int j = 0; j < numsSize; j++)
(nums[j] & mask) ? ones++ : zeros++;
ans += ones * zeros;
}
return ans;
}
```
Time Complexity: O(n)
Space Complexity: O(1)
---
### 測驗二
---
### 測驗三
#### 運作原理
參考之前的作業 [reference](https://hackmd.io/@shlin41/linux2023-summer-quiz)
**1. 找 subtree 中的 max/minminmin**
```
xt_first(root) --> 找出 root 這個 subtree 中的最小 node
xt_last(root) --> 找出root 這個 subtree 種的最大 node
```
**2. Rotation：調整樹高的基本操作**
```
xt_rotate_left(node) --> 把 Lchild 轉到 node 位置上
(演算法書的 rotate_right)
xt_rotate_right(node) --> 把 Rchild 轉到 node 位置上
(演算法書的 rotate_left)
```
**3. 計算樹高與平衡性：用來決定要不要調整的依據**
```
xt_balance(node) --> L_hint - R_hint
(左樹高 - 右樹高)
xt_max_hint(node) --> 算 hint（回傳樹高）
```
**4. 決定是否調整樹的架構：這個 function 可以快速 implement 成 AVL-Tree**
```
xt_update(**root, *node) --> 調整樹的架構
```
> AVL-Tree Implementation:
> *~~if (n->hint == 0 || n->hint != prev_hint)~~
> xt_update(root, p);*
> 把條件式刪除讓 root 到 node 間的所有 xt_node 都 xt_update() 一遍，就變成 AVL-Tree。但是這樣會增加 st_update() 的時間。
**5. 把 nodeA 用 nodeB 取代：屬於一種 node 刪除法**
(a) 概念上等於 swap(nodeA, nodeB) 再砍掉 nodeA
(b) nodeB 原本的位置屬於好刪除的，所以先把 nodeA 換過去
```
xt_replace_left(*node, *left) --> 拿 left 取代 node，left 的位置在 node 左子樹
xt_replace_right(*node, *right) --> 拿 right 取代 node，right 的位置在 node 右子樹
```
**6. Insert node 和 Remove node 到 XTree 中**
```
__xt_insert(**root, *p, *n, L/R) --> 在 p 的 L/R 加入 child node n
xt_insert(*tree, *key) --> 在 tree 加入一個 node(key)
__xt_remove(**root, *del) --> 在 tree 刪除 node del
xt_remove(*tree, *key) --> 先找到 node(key)，再刪除
```
#### 指出上述程式碼可改進之處
[TODO]
#### 設計效能評比程式
[TODO]
Sign in with Wallet
Connect another wallet