# 2020q1 Homework (quiz6)
contributed by < `IepIweidieng` >

## 正題 ([quiz6](<https://hackmd.io/@sysprog/linux2020-quiz6>))

原程式碼：

double divop(double orig, int slots) {
    if (slots == 1 || orig == 0)
        return orig;
    int od = slots & 1;
    double result = divop(orig / D1, od ? (slots + D2) >> 1 : slots >> 1);
    if (od)
        result += divop(result, slots);
    return result;
}

### D2

首先是 `od ? (slots + D2) >> 1 : slots >> 1`。

先思考有哪些位元運算有除法的數學意義。

`slots >> n` 的數學意義是對有號整數 `slots` 以 $2^n$ 進行 floor division 的結果，即 $\left\lfloor\dfrac{slots}{2^n}\right\rfloor$。

而使用 `(slots + ((1 << n) - 1)) >> n` 可取得對有號整數 `slots` 以 $2^n$
進行 ceil division 的結果，即 $\left\lceil\dfrac{slots}{2^n}\right\rceil$。

可以發現 `od ? (slots + D2) >> 1 : slots >> 1` 符合對 `slots` 以 $2^1$ 進行 ceil division 的模式。

因此猜測 `D2` 為 `1`。

可以發現寫為 `divop(orig / D1, (slots + 1) >> 1)` 就足夠了。

#### 除法補充

另外，改用普通的除法則會變成 $\textrm{sign}\left(\dfrac{slots}{2^n}\right) \cdot \left\lfloor\left|\dfrac{slots}{2^n}\right|\right\rfloor$ 或是 $\textrm{sign}\left(slots\right) \cdot \left\lfloor\textrm{sign}\left(slots\right) \cdot \dfrac{slots}{2^n}\right\rfloor$。

其中當 `slots` 為 32 bit 整數時，$\textrm{sign}\left(slots\right) \cdot x$ 可用 `((slots >> 31) ^ x) - (slots >>
31)` 或 `(slots >> 31) ^ (x + (slots >> 31))` 計算之。
($-x$ 可用 `~x + 1` 或 `~(x - 1)` 計算之)

因此 `slots / (1 << n)` 可用

((slots >> 31) ^ ((((slots >> 31) ^ slots) - (slots >> 31)) >> n)) - (slots >> 31)

(slots >> 31) ^ ((((slots >> 31) ^ (slots + (slots >> 31))) >> n) + (slots >> 31))

或是

const int32_t sign = slots >> 31;
// ...
(sign ^ (((sign ^ slots) - sign) >> n)) - sign
// or
sign ^ (((sign ^ (slots + sign)) >> n) + sign)

計算之。

### D1

再來，因為這個函式的功能是將浮點數除以整數的除法，可以假設這個函式正確運行時，$\textrm{divop}\left(orig,\ slots\right) = \dfrac{orig}{slots}$ 成立。

假設 `slots` 為 `2` 的乘冪，那麼 `result` 會直接是內層 `divop()` 呼叫的結果，因此需要保持 `slots` 與 `orig` 的比值。

為了保持原先的比值，既然 `slots` 變為一半，那麼 `orig` 也該變為一半。

因此猜測 `D1` 為 `2`。

### 回加

    if (od)
        result += divop(result, slots);

因為前面用了 ceil division，所以直接計算的結果會變小，要加回來。

而要加多少，可以數學方式進行驗證。

這裡將 `result` 分為剛初始化的 $result_{init}$ 與加回來後的 $result_{final}$ 兩個值以做區別，其中 $result_{final} = \textrm{divop}\left(orig,\ slots\right) = \dfrac{orig}{slots}$。

$$
\begin{split}
& \text{Assume } \left\{ \begin{array}{c}
D_1 = 2 \\
D_2 = 1 \\
\end{array} \right. \\
& result_{init} \\
&= \textrm{divop}\left(orig / D_1,\ od\ ?\ \left(slots + D_2\right) >> 1 : slots >> 1\right) \\
&= \textrm{divop}\left(orig / 2,\ od\ ?\ \left(slots + 1\right) >> 1 : slots >> 1\right) \\
&= \textrm{divop}\left(\dfrac{orig}{2},\ \left\lceil\dfrac{slots}{2}\right\rceil\right) \\
&= \dfrac{orig}{2} \div \left\lceil\dfrac{slots}{2}\right\rceil \\
\end{split}
$$

#### 當 `slots` 可被 `2` 整除時
這時 $\left\lceil\dfrac{slots}{2}\right\rceil = \dfrac{slots}{2}$。
$$
\begin{split}
& result_{init} \\
&= \dfrac{orig}{2} \div \left\lceil\dfrac{slots}{2}\right\rceil \\
&= \dfrac{orig}{2} \div \dfrac{slots}{2} \\
&= orig \div slots \\
&= \dfrac{orig}{slots} \\
&= result_{final} \\
\end{split}
$$

無須回加，符合原程式。

#### 當 `slots` 不可被 `2` 整除時
這時 $\left\lceil\dfrac{slots}{2}\right\rceil = \dfrac{slots + 1}{2}$。
$$
\begin{split}
& result_{init} \\
&= \dfrac{orig}{2} \div \left\lceil\dfrac{slots}{2}\right\rceil \\
&= \dfrac{orig}{2} \div \dfrac{slots + 1}{2} \\
&= orig \div \left(slots + 1\right) \\
&= \dfrac{orig}{slots + 1} \\
\end{split}
$$

接著計算要加的量。

$$
\begin{split}
& result_{final} - result_{init} \\
&= \dfrac{orig}{slots} - \dfrac{orig}{slots + 1} \\
&= orig \cdot \left(\dfrac{1}{slots} - \dfrac{1}{slots + 1}\right) \\
&= orig \cdot \left(\dfrac{slots + 1}{slots \cdot \left(slots + 1\right)} - \dfrac{slots}{slots \cdot \left(slots + 1\right)}\right) \\
&= orig \cdot \left(\dfrac{1}{slots \cdot \left(slots + 1\right)}\right) \\
&= \dfrac{orig}{slots \cdot \left(slots + 1\right)} \\
&= \dfrac{orig}{slots + 1} \div slots \\
&= result_{init} \div slots \\
&= \textrm{divop}\left(result_{init},\ slots\right) \\
\end{split}
$$

符合原程式，因此猜測正確。$\Box$

## 改寫為 Tail Recursion 形式

原程式：

double divop(double orig, int slots) {
    if (slots == 1 || orig == 0)
        return orig;
    int od = slots & 1;
    double result = divop(orig / 2, od ? (slots + 1) >> 1 : slots >> 1);
    if (od)
        result += divop(result, slots);
    return result;
}

將原本的 `result` 的初始化移到 `if (od)` branches 中，然後 inline `od`。

double divop(double orig, int slots) {
    if (slots == 1 || orig == 0)
        return orig;
    if (slots & 1) {
        const double result = divop(orig / 2, (slots + 1) >> 1);
        return result + divop(result, slots);
    }
    return divop(orig / 2, slots >> 1);
}

double divop(double orig, int slots) {
    if (slots == 1 || orig == 0)
        return orig;
    if (slots & 1)
        return divop(orig / 2, (slots + 1) >> 1) + divop(divop(orig / 2, (slots + 1) >> 1), slots);
    return divop(orig / 2, slots >> 1);
}

新增參數 `owe` (欠) 以做回加。

static double divop3(double orig, int slots, double owe) {
    if (slots == 1 || orig == 0)
        return orig + owe;
    if (slots & 1)
        return divop3(orig / 2, (slots + 1) >> 1, owe + divop3(divop3(orig / 2, (slots + 1) >> 1, 0), slots, 0));
    return divop3(orig / 2, slots >> 1, owe);
}

double divop(double orig, int slots) {
    return divop3(orig, slots, 0);
}