转自:http://www.chncla.com/yk/201006/p_7.html
最近浏览“程序员论坛”时发现不少好帖,增长了不少知识,现拿其中一则为例与大家共同分享心得。
某人提出一个问题:怎样才能生成一亿个不重复的随机数?
问题表述起来很简单,似乎只要弄明白什么叫随机数以及怎样用电脑生成随机数,就能解决问题。
随机数,个人理解为一定范围内出现的毫无规律的数,比如扔一个骰子,落在桌面上时朝上的一面所表示的数就是随机数,这个数只能在1到6的范围内,但具体是什么数,谁也不能肯定,因为它没有规律。一组不重复的随机数,对扔骰子来说就是扔出六个不一样的数来,再比如洗一次扑克牌,洗完后就是54张不重复的随机数。
第二个问题,怎么样用电脑生成随机数?只要调用某个语言的某个函数即可。其实电脑是没办法生成真正的随机数,因为电脑是高度有规律的机器,让它生成一个没规律的数,根本办不到。平时程序员用某个函数生成的随机数,只是利用某个算法弄出来的伪随机数,看起来像,其实不是,能解决问题就行。
回到这个帖子所描述的问题上来。生成一亿个不重复的随机数,最直接的算法就是每用函数生成一个数,就把它放在一个筐里,第一个数直接放到筐里,以后生成的数在放到筐里之前和筐里的每一个数比较一番,一旦发现筐里有和新生成的数一样的数时,丢掉这个新生成的数,再接着生成数。
毫无疑问,这种算法的效率非常低,看看其中的比较次数就知道了,最差的次数趋于无穷次。也就是说到后来,几乎生成不了和以往不同的数。
当然还可以将这个算法升级为效率高得多的算法,每生成一个数,把这个数从随机数生成器取的范围中去掉,比如要生成10个随机数,第一次生成一个3,我把3从随机数的范围中去掉,第二次只从1到9这个范围内找。3对应4,4对应5……9对应10。这样就不存在比较的环节,然而又多出一个对应的环节,每生成一个数之后就要把剩下的数重新对应一遍,效率也不容乐观。
目前以我为代表的普通程序员的想象力也就到此为止,想不出什么高级解决办法,就当扔一块砖头出来,下面就把真正的碧玉——数学家级程序员的算法隆重介绍请出来。
我们先用另一种眼光来看不重复的随机数:加密。把一个能看懂的英文字符串打乱字母的顺序,变成不可读,这就是加密。但必须得有规律地打乱,字母a对应另外一个固定的字母Ax,字母b对应另外一个固定的字母Bx,以此类推,而且必须一一对应的。那么字符串“ab…z”这26个字母对应的26个加密字母“AxBx和Zx”就可以看成是对应范围a到z的不重复的伪随机数,这就是数学家的算法的来源。
看看回帖者的原文:
“可以采用32bit RSA算法 设A从2~(N-1) C=(A EXP D) mod N 满足如下条件: D是素数,N是两个素数(P,Q)之积, (D * E) mod ((P-1) * (Q-1))=1 因为:若 C=(A EXP D)mod N 有: A=(C EXP E) mod N 所以,C与A 一一对应。 所以,对于A=2~(N-1),有不重复,无遗漏的伪随机码C。”
凡是稍微扯上一点数学,尤其是高等数学的问题,我等泛泛之辈看起来就有点费劲,这里虽然文字不长,但是还得慢慢来看。
这里面RSA算法是密码学三大算法之一(RSA、MD5、DES),是一种不对称密码算法。说如果满足条件:D是素数,N是两个素数(P,Q)之积,(D * E) mod ((P-1) * (Q-1))=1,那么存在C与A(范围从2到N-1)一一对应,且C=(A EXP D)mod N。A是一个有顺序的数,C就是一个看似无规律的伪随机数。Mod运算表示求模,例如7Mod3=1。意思是7除以3余1。类似地8Mod3=2,9Mod3=0。EXP表示前面数的后面数次方,AEXPD表示A的D次方。这两个运算清楚了,其它的也就没什么困难的了,*是乘法的意思,大多数理科生都清楚。
搜了一下网络,还得加上一些条件,1,P和Q不能一样。2,e<(P-1)(Q-1)且e与(P-1)(Q-1)的最大公因数为1。
下面用一个例子来试验一下,看看这个算法有多神奇。
设N=15,P=5,Q=3,则A为2到14的数。现在要产生2到14的伪随机数。取D为3,E为3,
C2=(2EXP3)mod15 = 8,
C3=(3EXP3)mod 15 = 12,
C4 = (4EXP3)mod 15= 4,
C5 = (5EXP3)mod 15= 5,
C6 = (6EXP3)mod 15= 6,
C7 = (7EXP3)mod 15= 13,
C8 = (8EXP3)mod 15= 2,
C9 = (9EXP3)mod 15= 9,
C10 = (10EXP3)mod 15= 10,
C11 = (11EXP3)mod 15= 11,
C12 = (12EXP3)mod 15= 3,
C13 = (13EXP3)mod 15= 7,
C14 = (14EXP3)mod 15= 14。
比较完美,如果数再大一点,可能看起来更随机一些。
由这个算法产生的1亿的伪随机数,效率那可是相当的高,只不过运算时要用到大数运算库。在一些讲求效率的场合应用的话,再做一些对应上的处理,升级一下算法,那定是相当的完美。
由此可以看出,算法的优化,如果仅仅停留在大脑能够想象到的小学数学的阶段,那是远远达不到要求。一个优秀的程序员,还需要加深对离散数学的理解,虽然,这次提到的算法已经深入到了数论的层次上了,但是RSA算法已经是应用非常广泛的算法,对其稍加变通,便可以发挥出更加不可思议的作用。程序员还是需要多学习算法,多学习数学,才能发挥出超出一般程序员的不可思议的能力。
package com.testcases; import java.math.BigInteger; import java.util.ArrayList; /** * Created by shiyanghuang on 16/6/29. */ public class randomNumber { private static ArrayListsu = new ArrayList(); public static void main(String[] args) { int maxNum = 1050000; getSu(maxNum); long P = su.get(su.size() - 1); long Q = su.get(su.size() - 2); long R = (P - 1) * (Q - 1) + 1; int T = 0; System.out.println("R : " + R); System.out.println("P : " + P); System.out.println("Q : " + Q); for (int i = 0; i < su.size(); i++) { if (R % su.get(i) == 0) { T = su.get(i); break; } } System.out.println("Su: " + T); long i = 2; while (i < R) { if (i % 1000000000 == 0) System.out.println(i + " : " + fn(i, T, P, Q)); i++; } } private static BigInteger fn(long a, int T, long P, long Q) { BigInteger ba = new BigInteger(a + ""); for (int i = 1; i < T; i++) { ba = ba.multiply(new BigInteger(a + "")); } System.out.println(ba.toString() + " "); BigInteger baa = ba.mod(new BigInteger(P + "").multiply(new BigInteger(Q + ""))); return baa; } private static void getSu(int max) { su.add(2); for (int i = 3; i < max; i++) { for (int j = 0; j < su.size(); j++) { if (i % su.get(j) == 0) { break; } else if (j == su.size() - 1) { su.add(i); } } } } }