本節書摘來自華章計算機《算法基礎》一書中的第2章，第2.1節，作者：（美）羅德·斯蒂芬斯（rod stephens）著，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視
數值算法就是對數值進行計算，這些算法執行随機取數、分解質因數、尋找最大公約數和幾何面積計算等任務。
所有的這些算法在不同情況下有各自的用途，但是它們也展示了有效的算法技巧，比如自适應算法、蒙特卡羅方法和用表格來存儲中間結果。
随機化在許多應用中起到重要作用。這種算法讓一個程式模仿随機過程，測試算法在随機輸入時的表現并尋找複雜問題的解決方案。2.5節描述的蒙特卡羅積分，即采用随機選點的辦法來估算複雜幾何面積的大小。
在任何一種随機的算法中，第一步都是建立随機數表。
2.1.1 随機數生成
盡管許多程式員談到“随機”數發生器，但隻要是用計算機來生成資料的算法，就并非真正的随機。如果知道該算法的細節和其内部狀态，就能正确地預見它生成的“随機”數。
為了獲得真正的不可預見的随機狀态，需要一個并非計算機程式的資料來源。例如，可以采用一台輻射探測儀，測量從輻射試樣中散發出來的粒子來擷取随機數值。因為沒有人能夠精确預見什麼時候粒子将出現，這是真正的随機。
其他可能是真正随機資料來源的還有擲骰子、分析電磁波中的靜電幹擾和研究布朗運動。random.org測量大氣噪音來生成随機數。
不幸的是，由于這類真随機數發生器（true random number generator，trng）相對複雜并且速度較慢，是以大多數應用場合采用一種更快的僞随機數發生器（pseudo random number generator，prng）來替代。對于多數應用場景，如果資料在某種程度上足夠随機，程式就可以利用它們并取得好的結果。
1.生成随機數
線性同餘發生器是一個簡單并且常見的僞随機數生成的方式，這種發生器用以下關系生成數：
其中a、b和m是常數。
x0的值初始化這個發生器，這樣不同的x0值就會産生不同的數組。用來初始化僞随機數發生器的值叫做種子，比如例子中的x0。
由于在一個數組中的所有數值都和m同餘，在最多m個數後，發生器會産生一個它之前産生過的數，然後這個數組從這個點開始重複。
舉一個十分簡單的例子，假設a＝7，b＝5，m＝11。如果以x0＝0開始，之前的方程式會給出以下的數組：
x0＝0
x1＝(7×0＋5) mod 11＝5
x2＝(7×5＋5) mod 11＝40 mod 11＝7
x3＝(7×7＋5) mod 11＝54 mod 11＝0
x4＝(7×10＋5) mod 11＝75 mod 11＝9
x5＝(7×9＋5) mod 11＝68 mod 11＝2
x6＝(7×2＋5) mod 11＝19 mod 11＝8
x7＝(7×8＋5) mod 11＝61 mod 11＝6
x8＝(7×6＋5) mod 11＝47 mod 11＝3
x9＝(7×3＋5) mod 11＝26 mod 11＝4
x10＝(7×4＋5) mod 11＝33 mod 11＝0
由于x10＝ x0＝ 0，這個數組開始重複。
數值0、5、7、10、9、2、8、6、3、4看起來十分随機，但是既然已經知道了這個程式用來産生這些數的方式，如果給出該程式所産生的一個确切的數，你就能夠正确地推斷出接下來的數是什麼。
一些僞随機數發生器算法使用有着多個常數的多元線性同餘發生器，然後從每一步生成的數值中選擇一些來使這些數看起來更加随機，并且增加數組的重複周期。這能夠使程式産生更多看起來随機的結果，但是那些方法仍然不是真正地随機。
注 大多數程式設計語言内置僞随機數發生方法，讀者可以直接使用這些方法而不是編寫自己的算法。這些方法普遍是相當快的，并且在發生重複前會産生一段非常長的數組，是以對大多數程式來說，可以直接使用它們而不是編寫自己的算法。
僞随機數發生器的一個特點或者說優點是：可以使用一個特定的種子來重複生成相同的“随機”數組。這也許看起來是一個缺點，因為這意味着這些數将會更容易被預測，但是重複使用相同的數可以使一些程式調試起來更加簡單。
重複使用相同的數組也可以使一些應用程式以非常緊湊的方式存儲複雜的資料。例如，假設一個程式需要使對象在地圖上進行一段漫長而複雜的僞随機運動。該程式會生成路線并且存儲該路線的所有坐标，以便它能在以後重新繪制這條路線。另外一個選擇是這個程式可以隻存儲一個種子值，然後每當它需要繪制路線時，可以用種子重新啟動一個僞随機數發生器來産生相同的路線。
在圖2-1中的随機樹程式使用種子值來代表随機樹。輸入一個種子值，然後點選“go”來生成一個随機樹。即使兩個種子有很小的差别，也會産生完全不同的結果。
随機樹程式使用你輸入的種子值來生成繪制參數，例如每一步産生的樹枝數、子樹枝相對其母樹枝彎曲的角度，以及每一條樹枝相對其母樹枝縮短的程度。讀者可以從本書網站上下載下傳程式來檢視詳細資訊。
如果輸入了同一個種子數兩次，則會産生兩個相同的随機樹。
基于密碼安全性的僞随機數發生器
任何線性同餘發生器都存在一個重複周期，是以它不能用于加密。
例如，使用僞随機數發生器，為消息中的每一個字母生成一個值，然後将這個值與字母相加，通過這種方式将一段消息加密。舉個例子，字母a加3是d，因為d是字母表中a之後的第三個字母。如果累加到了z，那麼再加1的時候就回到a。這樣，舉例來說，y加3是b。
隻要數組中的數是随機的，這種技術就會運作得十分良好，但是一個線性同餘發生器對于某個種子值隻能産生有限的數。破解密碼時需要做的就是通過嘗試所有的可能種子值來解密。對于每一個可能的解密結果，系統可以通過檢測字母頻率來檢驗這個結果是否看起來是真正的文本。如果使用了錯誤的種子，每個字母的出現頻率應當大緻相同。如果猜到了正确的種子，一些字母（例如e和t），将會比其他字母（例如j和x）出現得多很多。如果字母是十分不平均地配置設定，也許就是猜到了正确的種子值。
這也許看起來工作量很大，但是在現代計算機上這不難實作。如果種子值是一個32位整數，隻可能有大約 40億個不同種子值。一台現代計算機可以在幾秒鐘、最多幾分鐘之内，檢驗每一個可能的種子。
基于密碼安全性的僞随機數發生器（cryptographically secure pseudorandom number generator，csprng）使用更多的複雜算法來生成難以預測的數，并且生成長得多的數組而無需進入循環。它們通常使用更大值的種子。僞随機數發生器可能會使用32位長的種子，而基于密碼安全性的僞随機數發生器可能會使用1000位長的種子來初始化算法。
基于密碼安全性的僞随機數發生器是十分有趣并且“随機的”，但是它們也有一些缺點。其複雜性導緻其運算比其他更簡單的算法慢。它們也許不能手動初始化，是以可能不能簡單地生成一個可重複的數組。如果要使用相同的數組一次以上，應當使用較簡單的僞随機數發生器。所幸大部分算法不需要基于密碼安全性的僞随機數發生器，這樣可以僅用簡單些的僞随機數發生器。
2.確定公平性
通常程式需要使用一個公平的僞随機數發生器。公平僞随機數發生器按相同機率産生可能輸出結果。不均衡的僞随機數發生器是有偏斜的。例如，一個三分之二機率正面向上的硬币是有偏斜的。
許多程式設計語言有着在任何所需範圍内産生随機數的方法。但是如果需要編寫代碼将僞随機數發生器産生的數值轉換到一個特定範圍内，要注意以均衡的方式來完成。
線性同餘發生器産生一個範圍大于等于0而小于m的數，m是生成器方程中的模。
xn+1＝(a×xn＋b) mod m
通常一個程式需要一個範圍不在0到m之間的随機數。以下方程式顯然可以産生滿足最大值和最小值範圍的随機數，但并不恰當：
result＝min＋number mod (max－min＋1)
例如，為了獲得一個1到100之間的随機數，需要計算下列算式：
result＝1＋number mod (100－1+1)
這種方法的問題在于，相對于其他方法它産生的結果可能更加相似。
為說明原因，請思考這樣一個例子：m＝3，min＝0，max＝1。如果發生器以合理的方式運作，它會以大緻相同的機率産生數值0、1和2。如果将這三個值代入之前的方程式，你會得到如表2-1所示的結果。
在表2-1中，結果0出現的次數是結果1的兩倍，是以最終結果存在偏斜。
在一個真正的僞随機數發生器中，模m可能非常大，這時這個問題變得微小，但仍然存在。
較好的方法是将僞随機數發生器生成的值轉換到0和1之間，然後再與所需要範圍相乘，如下列方程式所示：
result＝min＋(number÷m)×(max－min)
另一種将一個僞随機數從一個範圍轉換到另一範圍的方法是簡單地忽略掉所需範圍之外的所有結果。在前例中，可以使用有限的僞随機數發生器來生成一個0和2之間的值。如果你得到2，它超過了所需範圍，可以忽視掉2而留下其他數。
舉一個稍微現實些的例子，假設将一塊餅幹給四位朋友中的一位，并且有一個六面骰子。這種情況下可以重複地抛骰子，直到得到一個1和4之間的值。
3.從偏斜的來源獲得公平性
即使一個僞随機數發生器是偏斜的，也可能存在一個生成公平随機數的方法。例如，假設你認為一枚硬币是偏斜的，但不知道正面向上或背面向上的機率，不過預想到可能性一定不是0.5。在這種情況下，以下算法産生一個公平的硬币抛擲結果：
來看看為何這麼做，假設偏斜的硬币正面向上的機率是p，那麼背面向上的機率就是1－p。進而第一次正面向上、第二次背面向上的幾率就是p×(1－p)。同理，第一次背面向上、第二次正面向上的幾率就是(1－p)×p。這兩個幾率相同，是以這個算法輸出正面向上或背面向上的幾率是相同的，也就是說結果是公平的。
如果偏斜的硬币兩次正面向上或者兩次背面向上，需要重複這個算法。如果很不走運，或者硬币是十分偏斜的，也許需要重複這個算法很多次才能得到一個公平的結果。例如，如果p＝0.9，該硬币兩次正面向上的可能性是81%，而兩次背面向上的可能性是1%。
注 使用偏斜的硬币來生成公平硬币抛擲在實際程式中未必有效。但是它是機率的一個不錯的應用，并且可能成為一個面試中的有趣問題，是以它值得了解。
可以使用相似的技術來擴充僞随機數發生器。例如，假設想将一塊餅幹給五位朋友中的一位，并且獲得随機數的唯一途徑是一枚公平硬币。在這種情況下，可以抛擲這枚硬币三次然後将結果看做一個二進制數，正面向上代表1，背面向上代表0。舉個例子：抛擲結果為正面、背面、正面代表二進制數101，也就是十進制中的5。如果獲得一個所需範圍之外的結果（在本例中抛擲結果為正面、正面、正面代表二進制數111或十進制數8，比朋友的數多），則放棄這個結果并且重新開始。
總之，程式設計語言附帶的僞随機數發生器工具可以适用于大部分的程式。如果需要更好的随機化，應當使用基于密碼安全性的僞随機數發生器。使用公平硬币來擷取一個1到100之間的随機數或者使用偏斜的資訊來源去生成公平數，這在作為面試問題或一些不可思議的情況下是有用的。
2.1.2 随機化數組
生成随機化數組中的項是程式中一個十分常見的任務。例如，假設一個日程安排程式需要配置設定員工輪班工作。如果程式按照他們出現在資料庫或其他固定順序中的字母順序配置設定員工工作，總是被配置設定在後半夜工作的員工會不滿意。
一些算法也可以利用随機化來防止最壞情況的發生。例如，标準的快速排序算法通常運作良好，但如果該算法需要進行排序的值最初已經被排序，這時算法會運作得較差。一種避免這種情況發生的方法是在排序前随機化這些值。
下面的算法展示了随機化數組的一種方式：
該算法通路這個數組上的每個位置一次，是以它有一個對于大多數應用程式來說足夠快的運作時間o(n)。
請注意重複這個算法并沒有使該數組“更加随機化”。當洗一摞撲克牌時，開始時相鄰的兩張撲克牌有保持相鄰的趨勢（即使可能相距稍遠些），是以需要洗很多次來得到一個相當随機的結果。該算法可以在一個過程中徹底随機化數組，是以重複運作它就是浪費時間了。
十分随機的數組
算法的另一個重要考慮因素是它是否産生一個公平的排列。換句話說，一個排列在任何給定位置結束的幾率對于排列在所有位置來說相同嗎？例如，如果在第一個位置開始的一個排列有半數幾率在第一個位置結束，那麼這種情況就是不公平的。
在介紹中說過本書不包含複雜的數學證明。是以可以跳過以下的讨論并且認為随機算法是公平的。但是如果懂得一些機率，就會發現下面的讨論是有幾分趣味的。
對于一個數組中的确定項，考慮它被放置在位置k的可能性。為了被放置在位置k，它必須不能被放置在位置1、2、3、…、k－1上，然後才能被放置在位置k上。
定義p-i為某項沒有被放置在位置i的幾率，前提是該項之前沒有被放置在位置1、2、…、i－1。同理定義pk為某項被放置在位置k的幾率，前提是該項之前沒有被放置在
位置1、2、…、k－1。然後該項被放置在k上的所有幾率是p-1×p-2×p-3×…× p-(k-1)×pk.
p1是1/n，是以p-1是1－p1＝1－1/n＝(n－1)/n。
在第一項确定後，第n－1項可以被放置在位置2上，是以p-2是1－p2＝1－1/(n－1)＝(n－2)/(n－1)。
概括地說，pi＝1/(n－(i－1))，p－i＝1－pi＝1－1/(n－(i－1))＝(n－(i－1)－1)/(n－(i－1))＝(n－i)/(n－i+1)。
将所有幾率乘在一起，p-1×p-2×p-3×…×p-(k-1)×pk，得到如下方程式：
觀察以上方程式，會發現可以約分每一項的分子和其後一項的分母。完成所有約分後，方程式被簡化為1/n。
這意味着無論k為何值，某項被放置在位置k的幾率都是1/n，是以這個排列是公平的。
一個和随機化數組生成十分相似的任務是從無重複數組中選擇某一确定數量的随機項。
例如，假設某作家正在舉行一場贈送五本著作的抽簽活動(我有時這樣做)，有100位參與者。一種找出這五位幸運兒的方法是将這100個名字編成一個數組，随機化該數組，然後向這個随機名單中的前五位贈書。每個确定姓名出現在五個獲獎位置的幾率是相同的，是以這次抽簽是公平的。
2.1.3 生成不均勻分布
一些程式需要生成不均勻分布的僞随機數。這些程式通常模仿其他形式的随機數生成過程。例如，一個程式也許會通過模仿兩個六面骰子的滾動來生成一個2和12之間的數。
這種情況下不可以簡單地取2和12之間的一個僞随機數，因為滾動兩個骰子所得到各個數的幾率是不同的。
解決方法是實際模拟一個骰子的滾動，生成兩個1和6之間的數，再将它們相加。