# 亂數

以現況來說，在 [E-game 打寇島](https://www.egame.kh.edu.tw/) 眾多積木中，能夠萌生隨機效果只有一個：「隨機顏色」。


其對應程式碼如下：

function colour_random() {
  var num = Math.floor(Math.random() * Math.pow(2, 24));
  return '#' + ('00000' + num.toString(16)).substr(-6);
}

colour_random();

由程式碼可得知：

* 該函數回傳一個長度為 7 的字串，||其正規表達式為 `^#([0-9a-f]{6})$`||，例如 `#000000` 或 `#ffffff`。
* 亂數結果有 $2^{24}$ 種可能（$2^{24}=16777216$），且每一種情況的發生機率皆相同。

## 顏色的大小

在 JavaScript 中，字串的大小由 **字典序（Lexicographic order）** 決定，也就是由左往右比。


這是兩個字串比大小。它們對應的程式碼如下：

'#990000' > '#66ffff';

以字典序比大小時，會先找到兩字串的首個不相等的位置，此範例為 `#` 號後的 `9` 與 `6`。
顯然 `'9' > '6'`，因此這個表達式成立。

## 機率的計算方式

觀察顏色的大小比較規則，可以發現若先把顏色字串轉成 16 進制整數，再進行比大小，仍會保持其結果。這使得我們可以輕易地計算出下列表達式成立的機率。


這些積木對應的程式碼如下：

colour_random() <= '#990000';

* 以 16 進制整數來看，`colour_random()` 的範圍是 `0x000000` 到 `0xffffff`。
（`0xffffff` + `1` = `16777216` 種）。
* 若表達式成立，則 `colour_random()` 的範圍是 `0x000000` 到 `0x990000`。
（`0x990000` + `1` = `10027009` 種）。

其中 `colour_random()` 的機率是均勻分布，表達式成立的機率為：

$$
P = \frac{10027009}{16777216} \approx 0.5976563096
$$

即表達式成立的機率約為 59.8%。

## 實現 50% 機率

從機率的計算方式可看出，若想要得到 50% 機率成立的表達式，可以使用顏色 `#799999`。
但可選的 70 種顏色裡，最接近 50% 的顏色為 `#66ffff`（40.2%） 及 `#990000`（59.8%）。

所以更好的方式應為：


它成立的機率約為 $0.4999999702$，是非常理想的實現方式。

:::spoiler 補充：計算方式
假設 $c_1, c_2$ 為兩個獨立且均勻地從顏色空間選取的隨機顏色變數，即 $c_1, c_2 \in \{0, 1, \dots, 2^{24} - 1\}$。由於 $c_1, c_2$ 是獨立且均勻分布的，我們可以得到：

$$
P(c_1 = c_2) = \frac{1}{2^{24}}
$$

且

$$
P(c_1 \neq c_2) = 1 - P(c_1 = c_2) = 1 - \frac{1}{2^{24}}
$$

考慮到 $c_1 > c_2$ 和 $c_1 < c_2$ 的對稱性，我們可以推斷兩者機率相同。因此，我們可以將 $c_1 \neq c_2$ 的機率平分給 $c_1 > c_2$ 和 $c_1 < c_2$。

所以：

$$
P(c_1 < c_2) = \frac{P(c_1 \neq c_2)}{2} = \frac{1 - P(c_1 = c_2)}{2} = \frac{1 - \frac{1}{2^{24}}}{2} = \frac{2^{24} - 1}{2^{25}}
$$

將數字代入計算：

$$
P(c_1 < c_2) = \frac{2^{24} - 1}{2^{25}} = \frac{16,777,216 - 1}{33,554,432} = \frac{16,777,215}{33,554,432} \approx 0.4999999701976776
$$

最終結果為：

$$
P(c_1 < c_2) = \frac{2^{24} - 1}{2^{25}} \approx 0.4999999701976776
$$
:::

### 達到 50% 理論值

若在兩顏色大小相等時，重新亂數一次，即可達到 50% 理論值。


:::warning
這種方式使用了較多的積木與較長的執行時間，一般無特殊需求時不會採用。
:::

## 實現亂數 - rand(min, max)


### 功能

回傳一個介於 `min` 到 `max` 之間的小數。

### 原理

變數 `x` 的每一個 bit 都有 50% 的機率是 `0` 或 `1`，因此 $0 \le x \le 2^{53}-1$ 且均勻分布。
其中 `9007199254740991` 是 JavaScript 中的 `Number.MAX_SAFE_INTEGER`，在此不多做解釋。

## 實現亂數 - randint(min, max)


### 功能

回傳一個介於 `min` 到 `max` 之間的整數。`min` 及 `max` 須為整數。

### 原理

輸出結果有 `max - min + 1` 種，將 `x` 對其取餘數後，再加上 `min` 即可。

## 實現指定機率

`rand(0, 1) < p` 成立的機率為 $p$。


## 積木

### random_half

<block type="procedures_defreturn" id="|r_|_Wffx+/a|d#)WZek" collapsed="true"><field name="NAME">random_half</field><statement name="STACK"><block type="variables_set" id="[DLwIlf{%/NR8S)wEukI"><field name="VAR">c1</field><value name="VALUE"><block type="colour_random" id="*Ww#:7L=%f|M5^nDMCHq"></block></value><next><block type="variables_set" id="`S!Kl2#L@]#]/5`qfqb_"><field name="VAR">c2</field><value name="VALUE"><block type="colour_random" id="g+ek{`xP(Pl%PVQw;bDi"></block></value><next><block type="procedures_ifreturn" id="G{ZudIJn_mKloMk_HE7C"><mutation value="1"></mutation><value name="CONDITION"><block type="logic_compare" id="~?R[IIwL:rQ^~|NE#I.k"><field name="OP">NEQ</field><value name="A"><block type="variables_get" id="MDDGm)-4~OP%D}vQPy;5"><field name="VAR">c1</field></block></value><value name="B"><block type="variables_get" id="B^8N`}%%I},0EiZAm)s_"><field name="VAR">c2</field></block></value></block></value><value name="VALUE"><block type="logic_compare" id="RiTC%%[mT=]mTW4~W,%{"><field name="OP">LT</field><value name="A"><block type="variables_get" id=":1j}l,J)^~f,]s7q8v!-"><field name="VAR">c1</field></block></value><value name="B"><block type="variables_get" id="A6^kUZhS?ry#tM:7PQY["><field name="VAR">c2</field></block></value></block></value></block></next></block></next></block></statement><value name="RETURN"><block type="procedures_callreturn" id="KK]l3uht/yqVPo3yw3xm"><mutation name="random_half"></mutation></block></value></block>

### rand

<block type="procedures_defreturn" id="9hgAR(Hh3G;V7Q8jjPRp" collapsed="true"><mutation><arg name="min"></arg><arg name="max"></arg><arg name="_x"></arg></mutation><field name="NAME">rand</field><comment pinned="false" h="80" w="160">描述此函數...</comment><statement name="STACK"><block type="variables_set" id="fUl1J?SRzhP]wE:{jZ`6"><field name="VAR">_x</field><next><block type="controls_repeat_ext" id="*%W4mkom@+`rQ@_F%q?["><value name="TIMES"><block type="math_number" id="ER)OGxZh=hx(R=7Kd1w1"><field name="NUM">53</field></block></value><statement name="DO"><block type="variables_set" id="s*[=eUX)cew!l?GZ@).`"><field name="VAR">_x</field><value name="VALUE"><block type="math_arithmetic" id="wsN5bO+#DmWC%Y)KMWuu"><field name="OP">MULTIPLY</field><value name="A"><block type="variables_get" id="4DL/tRfw/*Ta.5`Y0xP|"><field name="VAR">_x</field></block></value><value name="B"><block type="math_number" id="3Q,Rx4VYdkL@Sx;W?Q7,"><field name="NUM">2</field></block></value></block></value><next><block type="controls_if" id="8K)P,Jy.9hW3qNRU@nD0"><value name="IF0"><block type="logic_compare" id="2@D4?XQ+Q^ymCrW}eLpv"><field name="OP">GTE</field><value name="A"><block type="colour_random" id="y(W0J6w1h[vRKvdCjqyr"></block></value><value name="B"><block type="colour_random" id="2D*^:Ee;wI12VR(MMOuR"></block></value></block></value><statement name="DO0"><block type="variables_set" id="d:U^?a|rXk@7%.:3wqOV"><field name="VAR">_x</field><value name="VALUE"><block type="math_arithmetic" id="ZN5xD75iTlMU9`^4l3m."><field name="OP">ADD</field><value name="A"><block type="variables_get" id="FBHmL|v~pj~la1GL~bOs"><field name="VAR">_x</field></block></value><value name="B"><block type="math_number" id="Ft9*s2V8mxX,Dnhvtf+2"><field name="NUM">1</field></block></value></block></value></block></statement></block></next></block></statement></block></next></block></statement><value name="RETURN"><block type="math_arithmetic" id="Jqc`8Sn#]U60mcQ0{:1g"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="je@/wto2?Qh4lKgNV7=J"><field name="VAR">min</field></block></value><value name="B"><block type="math_arithmetic" id="{y-h,mu7q#bUv)5c?htY"><field name="OP">MULTIPLY</field><value name="A"><block type="math_arithmetic" id="M}fk+N1z+Q((C%.b-/bN"><field name="OP">DIVIDE</field><value name="A"><block type="variables_get" id="q[5y.SHGz1)|Lo}Zq3;e"><field name="VAR">_x</field></block></value><value name="B"><block type="math_number" id="BmrbBbUPV[44(wYBDnR@"><field name="NUM">9007199254740991</field></block></value></block></value><value name="B"><block type="math_arithmetic" id="m|J3[LHjT`}(p8@-yUl["><field name="OP">MINUS</field><value name="A"><block type="variables_get" id="`dSJ9M[G1yiW35%oHj1e"><field name="VAR">max</field></block></value><value name="B"><block type="variables_get" id="x8oL[E.Z;Ff7A^C|v5rh"><field name="VAR">min</field></block></value></block></value></block></value></block></value></block>

### randint

<block type="procedures_defreturn" id="hKg|,e}`C8S+1c~X:vyG" collapsed="true"><mutation><arg name="min"></arg><arg name="max"></arg><arg name="_x"></arg></mutation><field name="NAME">randint</field><comment pinned="false" h="80" w="160">描述此函數...</comment><statement name="STACK"><block type="variables_set" id="0%cHAxPT6yY=reY@w+pk"><field name="VAR">_x</field><next><block type="controls_repeat_ext" id="S=JB0{{?fNp2e];-q1rp"><value name="TIMES"><block type="math_number" id="24HI^OY5^9B!(VQnGDO_"><field name="NUM">53</field></block></value><statement name="DO"><block type="variables_set" id="UC`/(Bd*%U_9uT+oeu,1"><field name="VAR">_x</field><value name="VALUE"><block type="math_arithmetic" id="}Rf~[g414^+2O%~`AR1b"><field name="OP">MULTIPLY</field><value name="A"><block type="variables_get" id="HY1wr@wT.!N(IFu`8{T)"><field name="VAR">_x</field></block></value><value name="B"><block type="math_number" id="i#Ypn~tpSGq,nvRLJJ99"><field name="NUM">2</field></block></value></block></value><next><block type="controls_if" id="_#YgvNQ.5)N*5UU{Sl38"><value name="IF0"><block type="logic_compare" id="uqmdnnRjl883pApi}0=a"><field name="OP">GTE</field><value name="A"><block type="colour_random" id="zd}Y{CV#*A(yEovLyMu8"></block></value><value name="B"><block type="colour_random" id="f|0hda|j:p+P[+%FHCX*"></block></value></block></value><statement name="DO0"><block type="variables_set" id="SQu%K(.K1@/phX#4emsM"><field name="VAR">_x</field><value name="VALUE"><block type="math_arithmetic" id="zhl3xRtvw+FV9a8./)s*"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="ZZmWqYzDMF^7KIPN-EEJ"><field name="VAR">_x</field></block></value><value name="B"><block type="math_number" id="~`I[zyZnsHtkkKGP7Mh3"><field name="NUM">1</field></block></value></block></value></block></statement></block></next></block></statement></block></next></block></statement><value name="RETURN"><block type="math_arithmetic" id=".+pBHJ=wtk8#d+Z*e-Md"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="@WMGSuTMCyg@EoNn{Ck3"><field name="VAR">min</field></block></value><value name="B"><block type="math_modulo" id="lBl`aVzWS.JHq,vfM,-1"><value name="DIVIDEND"><block type="variables_get" id="aQUA_9mL6Uq9KJ*ez*=?"><field name="VAR">_x</field></block></value><value name="DIVISOR"><block type="math_arithmetic" id="`-(Yg=f]sK2e:l0UnYpz"><field name="OP">ADD</field><value name="A"><block type="math_arithmetic" id="C]n;!TfL8b|DB=[pMRZ7"><field name="OP">MINUS</field><value name="A"><block type="variables_get" id="O7nmJ_V8CSr.yN,Vb]01"><field name="VAR">max</field></block></value><value name="B"><block type="variables_get" id="3#ce.wV-#KPpMOv-BjT4"><field name="VAR">min</field></block></value></block></value><value name="B"><block type="math_number" id="`%P!5b;X~Hx~0[0k}8-/"><field name="NUM">1</field></block></value></block></value></block></value></block></value></block>