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

2022 年下半產業狀況

Meta 面臨史上最大裁員潮: 宣布大規模裁員超過 1.1 萬人，約占總員工 13%，幾乎是 Twitter 裁員人數 3 倍
Amazon 史上最大規模裁員預計資遣 1 萬人: 資遣的人數約為 1 萬人，佔 Amazon 公司約 3%
晶片，寒冬靜悄悄
取代南灣的南灘

用數學賺錢

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

IC 設計市場

Qualcomm's QCT (semiconductor) division outpowered QTL (licensing)

Image Not Showing Possible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Learn More →

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

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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

2022 年第三季全球前十大 IC 設計業者營收依序為:

Qualcomm
Broadcom
NVIDIA
AMD
MediaTek
Marvell
Realtek
Novatek
Cirrus Logic
Will Semiconductor

來源

Cirrus Logic Completes Acquisition of Wolfson Microelectronics

Will Semiconductor (韋爾半導體) 來自中國資本，對照 OmniVision Technologies

2018/2019: Will Semiconductor acquired OmniVision Technologies (for $2.178 billion) and SuperPix Micro Technology, merging them to form Omnivision Group.

2023 年排名 (第一季) : 出處

Qualcomm 7,962 23.5%
Broadcom 6,908 20.4%
Nvidia 6,732 19.9%
AMD 5,353 15.8%
MediaTek 3,147 9.3%
Marvell 1,354 4%
Novatek 791 2.3%
Realtek 646 1.9%
WillSemi 539 1.6%
MPS 451 1.3%

MPS (芯源系統有限公司)
第二季全球前十大 IC 設計營收季增 12.5%

\to

Integrated circuit (IC) design companies revenue worldwide from 2017 to 2023, by quarter

System Design Course

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.

Content Delivery Network (CDN)

the benefits of CDN, including:

Improving latency
Reducing bandwidth
Increasing content availability
DDoS protection

B+ Trees Implement in SQL

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

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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+樹

模擬面試檢討

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

史迪奇

從
$\sqrt{2}$ 的存在談開平方根的快速運算

失去倪
針對正整數在相鄰敘述進行 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 來實作除法。

探討精確度

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

10

有包含

5

這個因數，無法完全用

2

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

n = a b

(

a

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

l = c d

(

c

是十位數，

d

是個位數)，則只要以

n

算出來的除數在

n

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

l

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

x

是除數，

a . b \leq \frac{n}{x} \leq a . b 9 \Rightarrow \frac{n}{a . b 9} \leq x \leq \frac{n}{a . b}

可見
$x$ 的右邊是
$10$ ，因此一定在精確度內。
$x$ 的左邊：

$c . d \leq l \times \frac{a . b 9}{n} \leq c . d 9 \Rightarrow c . d \leq c d \times \frac{a . b 9}{a b} \leq c . d 9$
1. $c d \times \frac{a . b 9}{a b}$ 的左邊顯然成立
2. $c d \times \frac{a . b 9}{a b}$ 的右邊：
  
  $c . d + \frac{0.09 c d}{a b} \leq c . d + 0.09$
  因為
  $a b > c d$ 因此上述式子依然成立。

因此，前述猜想也成立，接下來只需要針對 19 來做討論即可。

1.9 \leq \frac{19}{x} \leq 1.99 \Rightarrow 9.55 \leq x \leq 10

接下來只需要找到這之中可以用除法來表示的除數即可。

找到除數

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

\frac{a n}{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);

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

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

$\frac{t e m p}{8} + \frac{t e m p}{2} + t e m p$
```
(temp >> 3) + (temp >> 1) + temp
```
這時會發生一個問題，也就是在 right shift 後，會有部分 bits 被忽略，因此必須將它們另外考慮進來。
```
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
```

合併步驟 1, 2

((((temp >> 3) + (temp >> 1) + temp) << 3) + d0 + d1 + d2)

湊出

128

，也就是右移

7

bits

q = ((((temp >> 3) + (temp >> 1) + temp) << 3) + d0 + d1 + d2) >> 7;

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);