2024q1 Homework4 (quiz3+4)

contributed by < shlin41 >

第三週測驗題

測驗一

運作原理

原理是將欲求平方根的

N^{2}

拆成：

\begin{array}{r} N^{2} = (a_{n} + a_{n - 1} + a_{n - 2} + . . . + a_{0})^{2}, w h e r e a_{m} = 2^{m} o r 0 \end{array}

進一步擴充:

\begin{array}{r} D e f : P_{m} ≜ a_{n} + a_{n - 1} + a_{n - 2} + . . . + a_{m} \end{array}

則可以得到:

\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} + (2 P_{m + 1} + a_{m}) a_{m} \\ = P_{m + 1}^{2} + Y_{m} \\ w i t h Y_{m} ≜ (2 P_{m + 1} + a_{m}) a_{m} \end{aligned}

我們的目的是從試出所有

a_{m}

，

a_{m} = 2^{m}

a_{m} = 0

。從

m = n

一路試到

m = 0

，而求得

a_{m}

只要試驗

P_{m}^{2} \leq N^{2}

是否成立。但是計算

N^{2} - P_{m}^{2} \geq 0

成本太高，所以在這個基礎上，希望可以找另外一種比較方法。

先定義:

\begin{array}{r} D e f : X_{m} ≜ N^{2} - P_{m}^{2} \end{array}

則可以得到:

\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} & ≜ P_{m + 1} \times 2^{m + 1} \\ d_{m} & ≜ (2^{m})^{2} \end{aligned}$
然後我們可以改寫
$Y_{m}$ :

$\begin{aligned} Y_{m} & = {\begin{cases} (2 P_{m + 1} + a_{m}) a_{m} & if a_{m} = 2^{m} \\ 0 & if a_{m} = 0 \end{cases} \\ = {\begin{cases} c_{m} + d_{m} & if a_{m} = 2^{m} \\ 0 & 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_{m} 2^{m} = {\begin{cases} c_{m} / 2 + d_{m} & if a_{m} = 2^{m} \\ c_{m} / 2 & 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^{2 n}

，可知指數項是 2n，所以程式中的 & ~1UL 是為了取偶數
int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL)

ffs / fls 取代 __builtin_clz

用 fls() 會相對容易，但是 C POSIX library 只有 ffs()。因此直接借用 linux-kernel 原始碼中的 __fls()。
查找過程中發現 __fls() 有分成硬體實做與軟體實做

硬體實做以 x86 為例:

static __always_inline unsigned long __fls(unsigned long word) {
  asm("bsr %1,%0" : "=r"(word) : "rm"(word));
  return word;
}

軟體實做如下:

#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;
}

取代部份

-- 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 = a b

(

a

是十位數

b

是個位數)，且

l = c d

(

c

是十位數，

d

是個位數)，則只要以

n

算出來的除數

t

，在

\frac{n}{t}

後能保持在精確度內，則

l

除以該除數

t

仍然會在精確度內。

我們的目標 n = UINT_MAX = 4294967295，一樣是要找出

t = \frac{a}{2^{N}}

，並滿足下式

\begin{array}{r} 429496729.5 \leq \frac{4294967295}{t} \leq 429496729.59 \Rightarrow 9.999999997904524 \leq t \leq 10 \end{array}

整段程式還看不懂:














#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: 應該就是模擬
$\frac{i n}{t} = \frac{i n \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{array}{r} S_{t} = {\begin{cases} Y_{0} & if t = 0 \\ α Y_{t} + (1 - α) S_{t - 1} & if t > 0 \end{cases} \end{array}

差別在於存 internal 時，會把

v a l \times 2^{f a c t o r}

後，再存入。讀取平均值時，會把

\frac{i n t e r n a l}{2^{f a c t o r}}

後，再讀出。

解析這一段：

avg->internal = (((avg->internal << avg->weight) - avg->internal) + (val << avg->factor)) >> avg->weight;

上式可改寫為

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

程式的最後部份

shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;

等於

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。程式碼改進如下：

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

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

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]

2024q1 Homework4 (quiz3+4)

第三週測驗題

測驗一

運作原理

ffs / fls 取代 __builtin_clz

Linux 核心原始程式碼找出對整數進行平方根運算的程式碼

嘗試撰寫更快的整數開平分根運算程式

測驗二

運作原理

比較 CPU 週期數量

% 9 (modulo 9) 和 % 5 (modulo 5) 程式碼

測驗三

ilog2() 運作原理

在 Linux 核心原始程式碼找出 log2 的相關程式碼

測驗四

運作原理

在 Linux 核心原始程式碼找出 EWMA 的相關程式碼

測驗五

運作原理

改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless

在 Linux 核心原始程式碼找出 ceil 和 log2 的組合

第四週測驗題

測驗一

運作原理

LeetCode 477

測驗二

測驗三

運作原理

指出上述程式碼可改進之處

設計效能評比程式

Read more

2024 Homework1

2024q1 Homework2 (quiz1+2)

2023 Homework3

Interview