🚀 go-pugleaf

/ hpisof0:comp.arch / dupuy@amsterdam.columbia.edu (Alexander Dupuy) / 10:33 am  Nov 24, 1986 /
henry@utzoo.UUCP (Henry Spencer) replies to an earlier post:
>
> > How about taking the exclusive-or of several such random bit generators?
> > This converges exponentially toward probability 1/2 as the number of
> > bits xor'ed increases.
>
>Only if the generators drift independently, which in general they won't:
>things like temperature and aging effects will be similar for all.

Actually, the xor scheme works best if the generators all drift in the same
direction.  Taking four generators which have drifted to 75% ones and 25%
zeros, and hooking them up in a two-level xor tree gives you the following
probability table:

f(a,b,c,d) = (a^b)^(c^d)

a  b  c  d	(a^b)^(c^d)	Prob (256ths)
----------	-----------	-------------
1  1  1  1	0		81
1  1  1  0	1			27
1  1  0  1	1			27
1  1  0  0	0		9
1  0  1  1	1			27
1  0  1  0	0		9
1  0  0  1	0		9
1  0  0  0	1			3
0  1  1  1	1			27
0  1  1  0	0		9
0  1  0  1	0		9
0  1  0  0	1			3
0  0  1  1	0		9
0  0  1  0	1			3
0  0  0  1	1			3
0  0  0  0	0		1
				-----------
				136	120
				53%	47%

    3% drift is not bad considering the generators are each 25% off.
This works well for odd as well as even numbers of generators.  This
setup is vulnerable to drift if generator pairs drift in _opposite_
directions, but with careful design, the factors you mention will tend
to prevent this.

@alex
----
arpa: dupuy@columbia.edu
uucp: ...!seismo!columbia!dupuy
----------