2024q1 Homework4 (quiz3+4)

contributed by < yan112388 >

2024q3 第 3 週測驗題

測驗一

連結

程式碼解釋

計算非負整數 N 的平方根

1. 版本一：
   使用 log2(N) 含式來計算 N 的以 2 為底的對數，並將結果轉換為整數，儲存在 msb 中，藉此得到 N 的最高非零位的位置
   版本二：
   使用　while　迴圈，將數字 N　右移（相當於將數字除以 2），直到剩下最高的非零位元，得到該位置
2. 計算 a = 1 << msb，這等同於設置 a 為 2 的 msb 次方，此值將作為初始步長
3. result 被初始化為 0，將用來儲存最終的平方根
4. 使用while 迴圈，只要 a 不為 0，迴圈就會繼續。在每次的迭代中：
   a. 它檢查 (result + a) * (result + a) 是否小於或等於 N，相當於檢查 (result + a) 的平方是否小於或等於 N
   b. 如果上述條件成立，那麼 a 被加到 result 上，因為 (result + a) 仍然是 N 的平方根的下界
   c. 無論上述條件是否成立，a 都會被右移一位，相當於將 a 除以 2，藉此將搜尋的步長做調整
5. 當 a 變為 0 時，迴圈結束，此時 result 包含了 N 的平方根的整數部分
6. 回傳 result

版本三：
以　Digit-by-digit calculation　方式，數學式的原理與細節尚未搞懂，待釐清。

測驗二

目的：計算 in 除以 10 的商和餘數，並將結果儲存在 div 和 mod 中

程式碼如下：

uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */

(in | 1) - (in >> 2) = in + 1 - (in >> 2)
                     = in + 1 - (in / 4)
                     = 0.75 * in + 1

• 欲計算 in 除以 10，10 可以表達為 1.25 * 8，所以我們可以先計算 0.75 * in，接著除以 8，就可以得到in 除以 10 的近似值

• (in | 1) 亦即 in + 1，作用為將 in 的最低位元設為 1。

  • 如果 in 是奇數， 則 (in | 1) = in
  • 如果 in 是偶數，則 (in | 1) = in + 1

  可以將此操作看成是一種數值的修正，計算 0.75 * in 時，實際上是在計算 3 * in / 4。當 in 是奇數時，此算數為精確的。但是當 in 是偶數時，由於我們進行了除法並向下取整數，結果會比實際的 0.75 * in 略小，加 1 可以補償這個誤差。

uint32_t q = (x >> 4) + x;
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;

• 每一行 q = (q >> 8) + x 都相當於將 q 除以 256，256 可以表達為 2 的 8 次方。在此有 4 行，表示將 x 除以 2 的 32 次方。

*div = (q >> 3);
*mod = in - ((q & ~0x7) + (*div << 1));

• 為了得到商數，將 q 右移 3 個位元，即提取 q 的高位元作為商。

(*div << DDDD) ≈ in / 10 * 2
               = 0.2 * in+

• 計算餘數部分，希望計算 in 除以 10 的餘數，於是我們需要從 in 中減去 *div * 10((q & ~0x7) + (*div << 1)) 亦同於 div * 8 + *div * 2

測驗三

計算以 2 為底的對數
版本二：

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= 65536) {
        result += 16;
        i >>= 16;
    }
    while (i >= 256) {
        result += 8;
        i >>= 8;
    }
    while (i >= 16) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

使用了二分搜法的想法

• 檢查輸入是否大於等於 65536（
  $2^{16}$）
  • 如果是，將結果加上 16，並將　i　右移 16 位，代表著將其範圍縮小到原來的 1/65536

重複此過程，檢查輸入是否大於等於 256（

$2^8$）、16 (

$2^4$) 及

$2$。每次檢查成功，就將結果加上相應的值（

$8、4、1$），並將　i　右移相應的位數。

版本三

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v | 1)); 
}

• 利用了 GCC 的內建函數 __builtin_clz，其功能為找到 x 最高位數前面有幾個 0 ， x 為 0 時，未定義。
• 對於一個 32 位的數字 v，31 - __builtin_clz(v) 就等於 v 的最高非零位的位置，也就是 floor(log2(v))。
• 為了處理　__builtin_clz(0) 是未定義的這種問題，使用了 v | 1 而非 v。　v | 1 的作用是將 v 的最低位設為 1，確保了進入 __builtin_clz is never的輸入永遠非０。

測驗四

EWMA 數學式展開如下：

$$\begin{array}{rl}{S}_t& =\alpha Y_t+(1-\alpha )\cdot S_{t-1}\\ & =\alpha Y_t+(1-\alpha )(\alpha Y_{t-1}+(1-\alpha )\cdot S_{t-2})\\ & =\alpha Y_t+(1-\alpha )(\alpha Y_{t-1}+(1-\alpha )(\alpha Y_{t-2}+(1-\alpha )\cdot S_{t-3}))\\ & =\alpha (Y_t+(1-\alpha )Y_{t-1}+(1-\alpha {)}^2{Y}_{t-2}+\dots +(1-\alpha {)}^k{Y}_{t-k}+\dots +Y_0)\end{array}$$

struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
    avg->internal = avg->internal
                        ? (((avg->internal << avg->weight) - avg->internal) +
                           (val << avg->factor)) >> avg->weight
                        : (val << avg->factor);
    return avg;
}

• $S_t$　表示時間
  $t$ 時的EWMA值，對應程式碼中的 avg->internal
• $Y_t$　表示時間
  $t$ 時的資料點，對應程式碼中的 val
• $\alpha$　為一係數，用來控制新樣本值的權重，即
  $(1-2^{-weight})$，

流程：

• 先判斷 internal 是否為零
  • 若為零則表示這是第一個資料點，將 val 值乘以
    $2^{factor}$，作為初始的 EWMA 值 (val << avg->factor)
  • 非零則代表已經有資料點被加入到 EWMA 公式中
    • 將 internal 值乘以
      $2^{weight}$ 再減去 internal ，得到
      $(2^{weight}-1)\cdot S_{t-1}$ ，對應於公式中的
      $(1-\alpha )\cdot S_{t-1}$
    • val << avg.factor 將新的樣本值 val 左移 avg->factor 位，相當於將其乘以
      $2^{factor}$ 進行縮放，對應於公式中的
      $\alpha Y_t$
    • 將前述兩項相加，得到
      $(2^{weight}-1)\cdot S_{t-1}+2^{factor}\cdot Y_t$，最後將結果右移 avg->weight 位，相當於除以
      $2^{weight}$

Q：為甚麼

$(2^{weight}-1)\cdot S_{t-1}$ 會對應於公式中的

$(1-\alpha )\cdot S_{t-1}$ ?

欲求

$(1-\alpha )\cdot S_{t-1}$，將之展開，得到：

$$\begin{array}{rl}(1-\alpha )\cdot S_{t-1}& =(1-(1-2^{-weight}))\cdot S_{t-1}\\ & =2^{-weight}\cdot S_{t-1}\end{array}$$
程式碼中：

$$\begin{array}{rl}(2^{weight}-1)\cdot S_{t-1}& =(2^{weight}-2^0)\cdot S_{t-1}\\ & =(2^{weight}-2^{weight}\cdot 2^{-weight})\cdot S_{t-1}\\ & =2^{weight}\cdot (1-2^{-weight})\cdot S_{t-1}\\ & =2^{weight}\cdot \alpha \cdot S_{t-1}\end{array}$$
最後，將

$(2^{weight}\cdot \alpha \cdot S_{t-1})$ 除以

$2^{weight}$：

$$\begin{array}{rl}\frac{2^{weight}\cdot \alpha \cdot S_{t-1}}{2^{weight}}& =\alpha \cdot S_{t-1}\\ & =(1-2^{-weight})\cdot S_{t-1}\end{array}$$

2024q3 第 4 週測驗題