# 2023-10-24 / 2023-10-31 問答簡記

## 2022 年下半產業狀況
* [Meta 面臨史上最大裁員潮](https://technews.tw/2022/11/13/meta-mark-zuckerberg-layoffs/): 宣布大規模裁員超過 1.1 萬人，約占總員工 13%，幾乎是 Twitter 裁員人數 3 倍
* [Amazon 史上最大規模裁員 預計資遣 1 萬人](https://news.pts.org.tw/article/609365): 資遣的人數約為 1 萬人，佔 Amazon 公司約 3%
* [晶片，寒冬靜悄悄](https://mp.weixin.qq.com/s?__biz=MzU1MzQ1NDk3MQ==&mid=2247550676&idx=1&sn=e97255bb5b38aeed60b04b95d93b48ad)
* [取代南灣的南灘](https://www.facebook.com/icjan/posts/pfbid02rU6ysBZUmb3qaAw6mtPkxQtJUgRPMQV2K9puaWyvuxavLP96eWdnH4oLr8jbBTE6l)

## 用數學賺錢
* [如何將高頻交易從股市帶進加密貨幣？](https://youtu.be/2E7F9PqPuBw)
* 美國知名財經作家 Michael Lewis 在幾年前寫過一本講華爾街高頻交易員的故事，書名是Flash Boys(中文版由早安財經出版）
* 他們利用演算法設定交易條件，鎖定研究好的股票，再來就是透過高速網路傳輸，爭取哪怕是比別人快百萬分之一秒的時間提前下單完成交易。為了網速夠快，甚至不惜花千萬到上億美金，鏟平ㄧ座會讓線路得繞過去的小山坡或建築，就為了把光纖拉直，爭取速度快幾奈秒。
* 這群 flash boys 和股票高頻交易的概念，三年前被台灣ㄧ家新創應用到加密貨幣交易上，ㄧ樣用 AI 協助演算、ㄧ樣透過累積大量交易達到機率上設定的穫利，但是不用拉光纖，而是在雲端業者的機房當中進行。這類似ㄧ種降維打擊，把股市已成熟的操作用在相比交易量小很多的加密貨幣交易上，也創造一個時間差的機會窗口。

## IC 設計市場

[Qualcomm's QCT (semiconductor) division outpowered QTL (licensing)](https://twitter.com/SKundojjala/status/1607385655000301569)
> 

雖然手機相關晶片業務仍有顯著成長，但 Qualcomm 手機業務營收出現趨緩，技術授權業務依然是 Qualcomm 目前重要營收來源。

依據 Qualcomm 在 2022 年第四季[財報](https://investor.qualcomm.com/)，總營收同比增長 22% 至 113.9 億美元，調整後每股盈餘為 3.13 美元。公司已開始停止招聘，同時也準備在必要時刻降低營運支出。

2022 年第三季全球前十大 IC 設計業者營收依序為:
1. Qualcomm
2. Broadcom
3. NVIDIA
4. AMD
5. MediaTek
6. Marvell
7. Realtek
8. Novatek
9. [Cirrus Logic](https://www.cirrus.com/)
10. Will Semiconductor
> [來源](https://www.trendforce.com.tw/presscenter/news/20221215-11499.html)

[Cirrus Logic Completes Acquisition of Wolfson Microelectronics](https://investor.cirrus.com/news-and-events/investor-news/news-details/2014/Cirrus-Logic-Completes-Acquisition-of-Wolfson-Microelectronics/default.aspx)

Will Semiconductor (韋爾半導體) 來自中國資本，對照 [OmniVision Technologies](https://en.wikipedia.org/wiki/OmniVision_Technologies)
> 2018/2019: Will Semiconductor acquired OmniVision Technologies (for $2.178 billion) and SuperPix Micro Technology, merging them to form Omnivision Group.

2023 年排名 (第一季) : [出處](https://www.trendforce.com/presscenter/news/20230620-11725.html)
1. Qualcomm 7,962 23.5%
2. Broadcom 6,908 20.4%
3. Nvidia 6,732 19.9%
4. AMD 5,353 15.8%
5. MediaTek 3,147 9.3%
6. Marvell 1,354 4%
7. Novatek 791 2.3%
8. Realtek 646 1.9%
9. WillSemi 539 1.6%
10. MPS 451 1.3%
> MPS (芯源系統有限公司)
> [第二季全球前十大 IC 設計營收季增 12.5%](https://finance.technews.tw/2023/09/21/top10-ic-design-2023q2/)

$\to$ [Integrated circuit (IC) design companies revenue worldwide from 2017 to 2023, by quarter](https://www.statista.com/statistics/946425/worldwide-fabless-integrated-circuit-design-houses/)

## [System Design Course](https://github.com/karanpratapsingh/system-design)
> System design helps us define a solution that meets the business requirements. It is one of the earliest decisions we can make when building a system. Often it is essential to think from a high level as these decisions are very difficult to correct later. It also makes it easier to reason about and manage architectural changes as the system evolves.
* [圖解電腦技術用語和概念](https://github.com/xiaolincoder/CS-Base)
* [略懂系統設計面試](https://youtu.be/Y93BGebBwEE)
* [刷題面試：資料結構、演算法之概念與準備方向](https://youtu.be/sAjkAz75jis)

## Content Delivery Network (CDN)
[the benefits of CDN](https://twitter.com/alexxubyte/status/1597635214565466112), including:
- Improving latency
- Reducing bandwidth
- Increasing content availability
- DDoS protection

## B+ Trees Implement in SQL

以下圖例以 5-way 為例(一棵樹的每個節點的度數小於等於 5)


B+ Trees 將所有資料(Data)存在 leaf node 上，leaf node 之外的 node 只會儲存 key 供索引，且每個 leaf node 會直接接到下一個 leaf node，可以利用類似 Binary Search Tree 的方式去搜尋目標值。

因為 B+ 將 leaf node 串接了，所以可以僅一次的搜尋就做到範圍查詢，以上圖為例，要搜尋 key 介於 5~16 之間的 Data，僅需搜尋下限 key = 5，並利用 leaf node 之間的 pointer 就可以將 5、6、7、9、12、16 這些目標找出。

對於硬碟來說，每個區塊大小固定，且 B+ Tree 的非葉節點只須儲存指標(Key)，當 Data 所需空間很大時並不影響非葉節點，所以可增加(相較於 B Tree)每個 node 的指標數量，以減少 I/O 次數，因此被應用在 MySQL 的 InnoDB 中。

- 深入閱讀 - [資料庫層的核心 - 索引結構演化論 B+樹](https://ithelp.ithome.com.tw/articles/10221111)

## 模擬面試檢討

* [面試心得](https://hackmd.io/@Xpz2MX78SomsO4mV3ejdqg/B11uF_bW7): 「題目跟 leetcode 的問法不太一樣，都是有一個生活化的描述，然後要你找出答案，我覺得很好的是每一題會告訴你這個題目要求的是甚麼，例如要求時間複雜度 $O(n log n)$ 且空間複雜度 $O(n)$，或是不要求時間複雜度，改為要求答案的正確性。第二點不同的是題目給的測試資料不像leetcode那麼完整，只會給兩個case，這邊就要自己去想有可能會發生甚麼情況，我覺得這是比較難的地方。」
- 直接在 codility 視窗中撰寫程式碼，才會有程式開發紀錄，不少公司不開放上網搜尋答案，網頁查詢參考 API 的部分，會被記錄下來作為綜合評量

- [ ] [史迪奇](https://hackmd.io/@sysprog/HyshnB6yT)
* [從 $\sqrt{2}$ 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt)

- [ ] [失去倪](https://hackmd.io/@sysprog/rJ8AJupka)
針對正整數在相鄰敘述進行 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';
    }
}

$\to$ 利用除法原理將 mod 10 和 div 10 合併
根據除法原理：
$f = g \times Q + r$
* $f$: 被除數
* $g$: 除數
* $Q$: 商
* $r$: 餘數

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

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

$\to$ 利用 bitwise operation 來去除除法運算
參考 [Hacker's Delight](http://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 來實作除法。

### 探討精確度
這裡採用 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$ 是除數，
$$
a.b\leq\frac{n}{x}\leq a.b9\\
\Rightarrow\frac{n}{a.b9}\leq x\leq\frac{n}{a.b}
$$
1. 可見 $x$ 的右邊是 $10$，因此一定在精確度內。
2. $x$ 的左邊：
$$
c.d\leq l\times\frac{a.b9}{n}\leq c.d9\\
\Rightarrow c.d\leq cd\times\frac{a.b9}{ab}\leq c.d9\\
$$
1. $cd\times\frac{a.b9}{ab}$ 的左邊顯然成立
2. $cd\times\frac{a.b9}{ab}$ 的右邊：
$$
c.d + \frac{0.09cd}{ab}\leq c.d + 0.09
$$
因為 $ab > cd$ 因此上述式子依然成立。

因此，前述猜想也成立，接下來只需要針對 `19` 來做討論即可。
$$
1.9\leq \frac{19}{x}\leq 1.99\\
\Rightarrow 9.55\leq x\leq10
$$
接下來只需要找到這之中可以用除法來表示的除數即可。

### 找到除數
方法如下，透過 bitwise operation 得到的算式必定是 $\frac{an}{2^N}$ 其中 $N$ 為非負整數， $a$ 正整數。因此只需要透過查看 $2^N$ 再配對適合的 $a$ 即可。
其中， $2^N=128, a=13,\frac{128}{13}\approx9.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)\times2$ 也就是 $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](http://homepage.cs.uiowa.edu/~dwjones/bcd/mod.shtml)

- [ ] [路易十四](https://hackmd.io/@sysprog/HyVs-dpJT)

- [ ] [屎地芬森](https://hackmd.io/@sysprog/HJi_5S6y6)