可逆随机数生成器的设计

卫丽华+芦欣

摘要：本文主要介紹可逆随机数生成器算法的设计与实现。首先，给出可逆随机数生成器介绍；其次，介绍基于存储器的可逆生成器和均匀分布的可逆生成器算法的设计与实现；最后，介绍其他分布的可逆生成器算法的设计与实现。

关键词：可逆计算； 随机数生成器；均匀分布

中图分类号：TP311 文献标识码：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]是一门新兴的交叉学科，其研究的主要目是克服计算系统中的能耗问题，而能耗是导致计算系统芯片发热的主要原因。在可逆计算中，如果一个正向计算包括一个随机数生成器，那么这个计算要可逆就必须有可逆的随机数生成器。否则后面正向计算得到的结果就变得不确定、不可重复和不可逆转的计算，最后计算出的结果也很难被验证与接受[2] [3]。

概率分布被计算机代码用来模拟物理系统模型，随机数生成器被用来生成符合一定概率分布的数列。生成随机数数列已经被研究好多年，主要的研究内容有：1）在一定精度范围内，增加随机数的长度；2）提高生成器的速度；3）生成复杂分布数列；4）降低多个数列间的相互影响。然而，关于生成器的可逆方面很少被研究或考虑。尽管它与这些研究有很多交叉的方面，但是它还没有受到广泛关注。

为了能够准确的回访随机数生成器，传统的方法是使用每个被生成的随机数的检测点的基值。这个方法能够解决正确性问题，但是浪费了资源，因为这需要消耗大量的内存空间和内存拷贝的时间。为了避免检测点，可逆的方法在尝试的时候又很快遇到一个新的问题，有一些随机数生成器是基于有损或者破坏性计算，比如取模操作。这就意味着可逆计算没有比基于检查点更有效的方法了。为了解决这样的问题，就需要开发不需要任何检查点就能回访随机数序列的可逆随机数生成器。理论上，这样的随机数生成器确实存在，因为随机数序列是循环序列中的数值，它应该可以同等难度的正向与反向遍历。

这里，我们将提出三种有效的可逆随机数生成器方法既可以正向遍历也可以反向遍历。

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

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

对于简单分布，随机数生成程序 经常是由一个封闭形式的公式指定，如指数分布。更复杂的分布要么计算机复杂或者由一封闭形式的公式指定。这儿有一个通用的方法适合所有的可逆生成器，可能简单分布的要更容易实现可逆。

任何可逆的随机数生成器都可以将生成的随机数保存在计算机存储器中并使它们能逆转，因为最简单的可逆可以基于正向随机数列后进先出操作。这是一个最费空间，但最通用的方法，因为他不需要去计算生成的随机数。例如，随机数来源于大气辐射能够很容易的使用基于存储器的方法实现可逆。因为，不管是基于物理的随机数生成器还是伪随机数都很难去通过计算可逆，但可逆性可以很容易的通过将正向序列记录在存储器中去实现。存储器可能会在使用的过程中被填满，因此，存储器的容量决定了可逆随机数序列的长度。

给定一个大小为Mz位的空间，每个数的精度为B位，那么可逆随机数序列的长度为M=Mz/B。

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

算法1.1展示了正向和反向遍历一个随机数数列的方法。正向随机数数列由函数R*（）生成，而R*（）的逆函数要么不存在，或者物理不可逆，或者计算成本很高，算法使用一个大小为M的循环缓冲区B来实现可逆。这个循环缓冲区下标取值范围是从0到M-1，h为头指针，c为当前指针，t为尾指针，如图1所示。

2 均匀分布的可逆生成器

最传统的随机数生成器是生成[0，1]区间均匀分布的变量，其他复杂分布的随机数数列都能基于这种均匀分布的随机数生成。因此均匀分布的随机数生成器是其他序列的基础。因而为了是其他复杂分布数列可逆，首先必须开发均匀分布可逆生成器。

一个均匀分布的伪随机数生成器正向和逆向的执行在算法1.2被给出。公式f（）从当前种子值计算下一个种子值，而f-1（）是从当前种子值计算前面种子值。公式U（）映射种子值到区间[0，1）。注意公式U（）既被用于正向计算也被用于反向计算。

3 其他分布的可逆生成器

其他分布的可逆随机数数生成器都可以基于均匀分布的随机数生成器基础上加上洗牌算法等算法，使得生成均匀分布的数列符合其他分布。

一个其他分布的伪随机数生成器正向和逆向的执行在算法1.3被给出。公式f（）从当前种子值计算下一个种子值，而f-1（）是从当前种子值计算前面种子值。公式S（）为变换函数实现不同分布，公式U（）映射种子值到区间[0，1）。注意公式U（）既被用于正向计算也被用于反向计算。

4 结束语

本文主首先介绍可逆随机数生成器；然后分别介绍基于存储器的可逆生成器、均匀分布和介绍其他分布的可逆生成器算法的设计与实现。主要解决可逆计算中，包括一个随机数生成器实现可逆。其中，基于存储器的可逆生成器是一种基于内存的通用方法，在内存允许范围内，记录检查点，实现任意可逆，而均匀分布与其他分布，则是基于特定公式，通过计算实现可逆，这样的方法避免了记录检查点，节约了内存。

参考文献：

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