可逆隨機(jī)數(shù)生成器的設(shè)計(jì)

衛(wèi)麗華+蘆欣

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

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

中圖分類號：TP311 文獻(xiàn)標(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

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

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

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

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

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

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

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

任何可逆的隨機(jī)數(shù)生成器都可以將生成的隨機(jī)數(shù)保存在計(jì)算機(jī)存儲器中并使它們能逆轉(zhuǎn)，因?yàn)樽詈唵蔚目赡婵梢曰谡螂S機(jī)數(shù)列后進(jìn)先出操作。這是一個(gè)最費(fèi)空間，但最通用的方法，因?yàn)樗恍枰ビ?jì)算生成的隨機(jī)數(shù)。例如，隨機(jī)數(shù)來源于大氣輻射能夠很容易的使用基于存儲器的方法實(shí)現(xiàn)可逆。因?yàn)椋还苁腔谖锢淼碾S機(jī)數(shù)生成器還是偽隨機(jī)數(shù)都很難去通過計(jì)算可逆，但可逆性可以很容易的通過將正向序列記錄在存儲器中去實(shí)現(xiàn)。存儲器可能會在使用的過程中被填滿，因此，存儲器的容量決定了可逆隨機(jī)數(shù)序列的長度。

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

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

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

2 均勻分布的可逆生成器

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

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

3 其他分布的可逆生成器

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

[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.