第 7 週課堂問答簡記

yanjiew1

Timsort 研究與對 Linux 核心貢獻嘗試

DokiDokiPB

quiz4

留意 LLRB 和典型 rbtree 的落差，見關於紅黑樹

qwe661234

fibdrv

zeddyuu

fibdrv
quiz4

fennecJ

l_offt 在 linux 中的定義是什麼 type?
在 fibdrv.c 使用到 l_offt 作為參數型態，可能發生什麼潛在的問題

src: linux v6.2.8
l_offt:
defined in
include/linux/types.h L46

#if defined(__GNUC__)
typedef __kernel_loff_t		loff_t;
#endif

__kernel_loff_t:
defined in
include/uapi/asm-generic/posix_types.h L88

typedef long long	__kernel_loff_t;

long long 的 range 為
-9223372036854775808 ~ 9223372036854775807 ，loff_t 單位為 byte ，

$\approx \pm 8388608$ TiB

kernel module 計算完 big num 之後是怎麼把資料傳到 user space 的 ？

用 __copy_to_user 這個 kernel API 。

那這個 API 最後面參數的 size 範圍有多大。

最後一個參數的型別為 unsigned long ，在 LP64 的機器上是 64bit 的寬度。

對，linux 在處理這個議題的時候是尊重使用者電腦的架構決定寬度，若在 32 位元的機器上 unsigned long 的寬度則會是 32 位元。

chun61205

針對正整數在相鄰敘述進行 mod 10 和 div 10 操作，如何減少運算成本？

static void string_number_add(char *b, char *a, char *res, size_t size)
{
    int carry = 0;

    for (int i = 0; i < size; i++) {
        int temp = (b[i] - '0') + (a[i] - '0') + carry;
        carry = temp / 10;
        temp = temp % 10;
        res[i] = temp + '0';
    }
}

利用除法原理將 mod 10 和 div 10 合併

根據除法原理：

$f=g\times Q+r$

• $f$: 被除數
• $g$: 除數
• $Q$: 商
• $r$: 餘數

可以將 mod 10 和 div 10 合併，以此來減少除法的數量。

carry = temp / 10;
temp = temp - carry * 10;

利用 bitwise operation 來去除除法運算

這裡參考了 Hacker's Delight 來實作除法。

探討精確度

這裡採用 bitwise operation 來實作除法，因為

$10$ 有包含

$5$ 這個因數，無法完全用

$2$ 的次方項來表示，因此結果會是不準確的。然而，觀察上面的程式碼後可以發現， temp 不可能會大於 19 ，因此只需要考慮 19~0 的情況即可。
我們的目標是，得到 temp / 10 且直到小數點後第一位都是精準的。
這時，我們可以提出一個猜想，假設我們我們目標的最大數是 n ， l 則是比 n 還要小的非負整數。那麼假設

$n=ab$ (

$a$ 是十位數 b 是個位數)，且

$l=cd$ (

$c$ 是十位數，

$d$ 是個位數)，則只要以

$n$ 算出來的除數在

$n$ 除以該除數後在經確度內，則

$l$ 除與該除數仍然會在經確度內。證明如下：
假設

$x$ 是除數，

$$\begin{gathered} a.b\le \frac{n}{x}\le a.b9 \\ \Rightarrow \frac{n}{a.b9}\le x\le \frac{n}{a.b} \end{gathered}$$

1. 這裡可以很明顯的看出
   $x$ 的右邊是
   $10$ ，因此一定在精確度內。
2. $x$ 的左邊：
   
   $$\begin{gathered} c.d\le l\times \frac{a.b9}{n}\le c.d9 \\ \Rightarrow c.d\le cd\times \frac{a.b9}{ab}\le c.d9 \end{gathered}$$
   1. $cd\times \frac{a.b9}{ab}$ 的左邊顯然成立
   2. $cd\times \frac{a.b9}{ab}$ 的右邊：
      
      $$c.d+\frac{0.09cd}{ab}\le c.d+0.09$$
      因為
      $ab>cd$ 因此上述式子依然成立。

因此，當初我的猜想也成立，接下來只需要針對 19 來做討論即可。

$$\begin{gathered} 1.9\le \frac{19}{x}\le 1.99 \\ \Rightarrow 9.55\le x\le 10 \end{gathered}$$
接下來只需要找到這之中可以用除法來表示的除數即可。

找到除數

方法如下，透過 bitwise operation 得到的算式必定是

$\frac{an}{2^N}$ 其中

$N$ 為非負整數，

$a$ 正整數。因此只需要透過查看

$2^N$ 再配對適合的

$a$ 即可。
其中，

$2^N=128,a=13,\frac{128}{13}\approx 9.84$ 便是一個可以使用的解。

實作除法

接著，嘗試透過 bitwise operation 來配對數字。

unsigned d2, d1, d0, q, r;

d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((temp >> 3) + (temp >> 1) + temp) << 3) + d0 + d1 + d2) >> 7;
r = temp - (((q << 2) + q) << 1);

關於這段程式碼，我的思路如下：

1. 先湊出
   $13$：
   觀察
   $13$ 後可以發現，
   $13=8+4+1=2^3+2^2+2^0$ ，因此，首先要做的便是，使用 bitwise operation 得到
   $\frac{13temp}{8}$
   
   $\frac{temp}{8}+\frac{temp}{2}+temp$
   ​​​​(temp >> 3) + (temp >> 1) + temp
   

2. 這時會發生一個問題，也就是在 right shift 後，會有部分 bits 被忽略，因此必須將它們另外考慮進來。
   ​​​​d0 = q & 0b1;
   ​​​​d1 = q & 0b11;
   ​​​​d2 = q & 0b111;
   

3. 合併步驟 1, 2
   ​​​​((((temp >> 3) + (temp >> 1) + temp) << 3) + d0 + d1 + d2)
   

4. 湊出
   $128$ ，也就是右移
   $7$ bits
   ​​​​q = ((((temp >> 3) + (temp >> 1) + temp) << 3) + d0 + d1 + d2) >> 7;
   

5. mod 10 就是 temp 減去 div 10 的結果乘與
   $10$
   ​​​​r = temp - (((q << 2) + q) << 1);
   

   其中 (((q << 2) + q) << 1) 就是 (
   $q\times 4+q)\times 2$ 也就是
   $10\times q$

測試結果如下：

#include <stdint.h>
#include <stdio.h>

int main()
{
    for(int n = 0; n <= 19; n++){
        unsigned d2, d1, d0, q, r;
        d0 = q & 0b1;
        d1 = q & 0b11;
        d2 = q & 0b111;
        q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
        r = n - (((q << 2) + q) << 1);
        printf("q: %d r: %d\n",  q, r);
    }
    
    return 0;
}

q: 0 r: 0
q: 0 r: 1
q: 0 r: 2
q: 0 r: 3
q: 0 r: 4
q: 0 r: 5
q: 0 r: 6
q: 0 r: 7
q: 0 r: 8
q: 0 r: 9
q: 1 r: 0
q: 1 r: 1
q: 1 r: 2
q: 1 r: 3
q: 1 r: 4
q: 1 r: 5
q: 1 r: 6
q: 1 r: 7
q: 1 r: 8
q: 1 r: 9

結果正確。

可包裝為以下函式:

#include <stdint.h>
void divmod10(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));   
}

使用案例:

    unsigned div, mod;
    divmod10(193, &div, &mod);

延伸閱讀:

• Modulus without Division, a tutorial