生成排序的隨機數而不涉及指數？

Question

我正在尋找一個數學方程或算法，它可以在[0,1]範圍內以升序生成均勻的隨機數，而無需除法運算符的幫助。我熱衷於跳過除法操作，因爲我正在用硬件實現它。謝謝。

Answer 1

按照升序（或降序）順序生成數字意味着依次生成它們，但具有正確的分佈。這反過來又意味着我們需要知道一組大小爲N的最小值的分佈，然後在每個階段我們需要根據我們已經看到的情況使用條件來確定下一個值。在數學上，除了避免分裂的問題外，這些都很簡單。

您可以使用算法min = 1 - U**(1/N)從單個統一的（0,1）隨機數U生成N個均勻（0,1）的最小值，其中**表示指數運算。換句話說，統一體的根的補碼與[0,1]範圍內的最少N個統一體具有相同的分佈，然後可以將它們縮放到任意其他的區間長度。

調節方面基本上說，已經生成的k值已經吃掉了原始間隔的一部分，而我們現在想要的是N-k值的最小值，縮放到剩餘的範圍。

結合這兩部分產生以下邏輯。生成N個制服中最小的一個，按照剩餘間隔長度（第一次爲1）進行縮放，並將結果作爲我們生成的最後一個值。然後生成最小的N-1個制服，按照剩餘時間間隔長度進行縮放，並將其添加到最後一個，以便爲您提供下一個值。泡沫，沖洗，重複，直到你完成了它們。下面的Ruby實現提供了分佈式地正確的結果，假設你已經在此之前，讀取或指定N：

last_u = 0.0 
N.downto(1) do |i| 
    p last_u += (1.0 - last_u) * (1.0 - (rand ** (1.0/i))) 
end 

但我們有那個討厭我^個根它使用部門。但是，如果我們提前知道N，我們可以預先計算從1到N的整數的倒數並將它們表格化。

last_u = 0.0 
N.downto(1) do |i| 
    p last_u += (1.0 - last_u) * (1.0 - (rand ** inverse[i])) 
end 

我不知道有什麼方法順序得到正確的分配行爲，而不使用指數運算。如果這是一個展示瓶塞，你將不得不放棄該過程的順序特性或統一性要求。

Answer 2

您可以嘗試所謂的「分層採樣」，這意味着您將範圍分爲多個分箱，然後從分箱中隨機採樣。這樣生成的樣本比從整個區間生成的樣本更均勻（更少聚集）。出於這個原因，分層抽樣降低了蒙特卡羅估計的方差（我不認爲這對你很重要，但這就是爲什麼該方法是發明的，作爲方差的減少方法）。

按順序生成數字是一個有趣的問題，但我的猜測是要在整個時間間隔內獲得均勻分佈，您將不得不應用一些需要更多計算的公式。如果你想盡量減少計算時間，我懷疑你不可能比生成一個樣本然後對它進行分類更好。