衛(wèi)麗華+蘆欣

摘要：本文主要介紹可逆隨機數(shù)生成器算法的設(shè)計與實現(xiàn)。首先，給出可逆隨機數(shù)生成器介紹；其次，介紹基于存儲器的可逆生成器和均勻分布的可逆生成器算法的設(shè)計與實現(xiàn)；最后，介紹其他分布的可逆生成器算法的設(shè)計與實現(xiàn)。

關(guān)鍵詞：可逆計算； 隨機數(shù)生成器；均勻分布

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）31-0240-02

Abstract： This paper mainly introduces the design and implementation of reversible algorithm of random number generator. First， it gives the introduced of reversible random number generator， Secondly， design and realization of the algorithm based on the memory and uniform distribution of reversible generator， Finally， introduced the distribution of design and implementation of the other reversible generator.

Key words： Reversible Computing； Random Number Generator. Uniform distribution

可逆計算[1]是一門新興的交叉學(xué)科，其研究的主要目是克服計算系統(tǒng)中的能耗問題，而能耗是導(dǎo)致計算系統(tǒng)芯片發(fā)熱的主要原因。在可逆計算中，如果一個正向計算包括一個隨機數(shù)生成器，那么這個計算要可逆就必須有可逆的隨機數(shù)生成器。否則后面正向計算得到的結(jié)果就變得不確定、不可重復(fù)和不可逆轉(zhuǎn)的計算，最后計算出的結(jié)果也很難被驗證與接受[2] [3]。

概率分布被計算機代碼用來模擬物理系統(tǒng)模型，隨機數(shù)生成器被用來生成符合一定概率分布的數(shù)列。生成隨機數(shù)數(shù)列已經(jīng)被研究好多年，主要的研究內(nèi)容有：1）在一定精度范圍內(nèi)，增加隨機數(shù)的長度；2）提高生成器的速度；3）生成復(fù)雜分布數(shù)列；4）降低多個數(shù)列間的相互影響。然而，關(guān)于生成器的可逆方面很少被研究或考慮。盡管它與這些研究有很多交叉的方面，但是它還沒有受到廣泛關(guān)注。

為了能夠準(zhǔn)確的回訪隨機數(shù)生成器，傳統(tǒng)的方法是使用每個被生成的隨機數(shù)的檢測點的基值。這個方法能夠解決正確性問題，但是浪費了資源，因為這需要消耗大量的內(nèi)存空間和內(nèi)存拷貝的時間。為了避免檢測點，可逆的方法在嘗試的時候又很快遇到一個新的問題，有一些隨機數(shù)生成器是基于有損或者破壞性計算，比如取模操作。這就意味著可逆計算沒有比基于檢查點更有效的方法了。為了解決這樣的問題，就需要開發(fā)不需要任何檢查點就能回訪隨機數(shù)序列的可逆隨機數(shù)生成器。理論上，這樣的隨機數(shù)生成器確實存在，因為隨機數(shù)序列是循環(huán)序列中的數(shù)值，它應(yīng)該可以同等難度的正向與反向遍歷。

這里，我們將提出三種有效的可逆隨機數(shù)生成器方法既可以正向遍歷也可以反向遍歷。

1）基于存儲器的可逆生成器；2）均勻分布的可逆生成器；3）其他分布的可逆生成器。

1 基于存儲器的可逆生成器

對于簡單分布，隨機數(shù)生成程序 經(jīng)常是由一個封閉形式的公式指定，如指數(shù)分布。更復(fù)雜的分布要么計算機復(fù)雜或者由一封閉形式的公式指定。這兒有一個通用的方法適合所有的可逆生成器，可能簡單分布的要更容易實現(xiàn)可逆。

任何可逆的隨機數(shù)生成器都可以將生成的隨機數(shù)保存在計算機存儲器中并使它們能逆轉(zhuǎn)，因為最簡單的可逆可以基于正向隨機數(shù)列后進先出操作。這是一個最費空間，但最通用的方法，因為他不需要去計算生成的隨機數(shù)。例如，隨機數(shù)來源于大氣輻射能夠很容易的使用基于存儲器的方法實現(xiàn)可逆。因為，不管是基于物理的隨機數(shù)生成器還是偽隨機數(shù)都很難去通過計算可逆，但可逆性可以很容易的通過將正向序列記錄在存儲器中去實現(xiàn)。存儲器可能會在使用的過程中被填滿，因此，存儲器的容量決定了可逆隨機數(shù)序列的長度。

給定一個大小為Mz位的空間，每個數(shù)的精度為B位，那么可逆隨機數(shù)序列的長度為M=Mz/B。

算法1.1 基于存儲器的可逆生成器

算法1.1展示了正向和反向遍歷一個隨機數(shù)數(shù)列的方法。正向隨機數(shù)數(shù)列由函數(shù)R*（）生成，而R*（）的逆函數(shù)要么不存在，或者物理不可逆，或者計算成本很高，算法使用一個大小為M的循環(huán)緩沖區(qū)B來實現(xiàn)可逆。這個循環(huán)緩沖區(qū)下標(biāo)取值范圍是從0到M-1，h為頭指針，c為當(dāng)前指針，t為尾指針，如圖1所示。

2 均勻分布的可逆生成器

最傳統(tǒng)的隨機數(shù)生成器是生成[0，1]區(qū)間均勻分布的變量，其他復(fù)雜分布的隨機數(shù)數(shù)列都能基于這種均勻分布的隨機數(shù)生成。因此均勻分布的隨機數(shù)生成器是其他序列的基礎(chǔ)。因而為了是其他復(fù)雜分布數(shù)列可逆，首先必須開發(fā)均勻分布可逆生成器。

一個均勻分布的偽隨機數(shù)生成器正向和逆向的執(zhí)行在算法1.2被給出。公式f（）從當(dāng)前種子值計算下一個種子值，而f-1（）是從當(dāng)前種子值計算前面種子值。公式U（）映射種子值到區(qū)間[0，1）。注意公式U（）既被用于正向計算也被用于反向計算。

3 其他分布的可逆生成器

其他分布的可逆隨機數(shù)數(shù)生成器都可以基于均勻分布的隨機數(shù)生成器基礎(chǔ)上加上洗牌算法等算法，使得生成均勻分布的數(shù)列符合其他分布。

一個其他分布的偽隨機數(shù)生成器正向和逆向的執(zhí)行在算法1.3被給出。公式f（）從當(dāng)前種子值計算下一個種子值，而f-1（）是從當(dāng)前種子值計算前面種子值。公式S（）為變換函數(shù)實現(xiàn)不同分布，公式U（）映射種子值到區(qū)間[0，1）。注意公式U（）既被用于正向計算也被用于反向計算。

4 結(jié)束語

本文主首先介紹可逆隨機數(shù)生成器；然后分別介紹基于存儲器的可逆生成器、均勻分布和介紹其他分布的可逆生成器算法的設(shè)計與實現(xiàn)。主要解決可逆計算中，包括一個隨機數(shù)生成器實現(xiàn)可逆。其中，基于存儲器的可逆生成器是一種基于內(nèi)存的通用方法，在內(nèi)存允許范圍內(nèi)，記錄檢查點，實現(xiàn)任意可逆，而均勻分布與其他分布，則是基于特定公式，通過計算實現(xiàn)可逆，這樣的方法避免了記錄檢查點，節(jié)約了內(nèi)存。

參考文獻：

[1] Landauer R. Irreversibility and heat generation in the computing process[J]. IBM Journal of Research and Development， 1961， 5（3）：183–191.

[2] Alfred V. Aho. Compilers： Principles， Techniques， and Tools. 2nd Edition[M]. USA： Addison Wesley，2011.

[3] Charles. Crafting a Compiler with C[M]. USA： Addison Wesley， 2005.