Thursday, July 2, 2009

Double spring pendulum pRNG

You can make a pretty decent random number generator through physical simulation of a double spring pendulum. Double pendulums are chaotic systems, and as such, express a high variation of state after a given time, based on small variations on the initial dataset (the so called butterfly effect).

The motion used to generate the random numbers looks like this:


What makes this a decent random number generator is the lack of a closed form solution to the motion of the pendulum, combined with five hidden degrees of freedom.

The algorithm loosely looks like this:

  1. Simulate for N timesteps (I the Euler method for integration, but it's probably a lot smarter to use a less sensitive algorithm -- or not, the errors introduced by the algorithm might make the data more random.)

  2. Let θ be the inner pendulum's angle (scaled to the range 0 ... 1)

  3. Let φ be the outer pendulum's angle relative to the inner angle (scaled to the range 0 ... 1)

  4. Let the data be ((θ * 1000016) ∧ ff16) ⊕ ((φ * 1000016) ∧ ff16)

  5. Let N be some constant (the higher the more random the data) + data * (some other constant)

  6. Yield 'data'

  7. Repeat.


Using 'ent' to analyze the data, these are typical values:

Entropy = 7.997207 bits per byte.

Optimum compression would reduce the size
of this 70346 byte file by 0 percent.

Chi square distribution for 70346 samples is 271.07, and randomly
would exceed this value 23.38 percent of the times.

Arithmetic mean value of data bytes is 127.4919 (127.5 = random).
Monte Carlo value for Pi is 3.135107472 (error 0.21 percent).
Serial correlation coefficient is 0.000481 (totally uncorrelated = 0.0).


versus /dev/urandom on Linux:
Entropy = 7.997121 bits per byte.

Optimum compression would reduce the size
of this 70346 byte file by 0 percent.

Chi square distribution for 70346 samples is 281.53, and randomly
would exceed this value 12.19 percent of the times.

Arithmetic mean value of data bytes is 127.3213 (127.5 = random).
Monte Carlo value for Pi is 3.148072330 (error 0.21 percent).
Serial correlation coefficient is -0.001095 (totally uncorrelated = 0.0).



The randomness is on par or slightly better than Linux' (pretty dubious) urandom-pRNG, depending on configuration. :-)



This whole project got started as a means of visually telling large numbers like checksums apart through setting the initial parameters of a spring coupled double pendulum according to the number, and then tracing it's motion for a couple of thousand iterations. That did do the trick satisfactory, but still needs more work before it's useful.

No comments:

Post a Comment