Tag: randu

Delicate tracings from a terrible PRNG

The two orbits of 16-bit RANDU, plotted as X-Y coordinates

I’d previously mentioned RANDU — IBM’s standard scientific PRNG in the 1970s that was somewhat lacking, to say the least —some time ago, but I found a new wrinkle.

For their 1130 small computer system, IBM published the Scientific Subroutine Package [PDF], which included a cut-down version of RANDU for this 16-bit machine. The code, on page 64 of the manual, doesn’t inspire confidence:

c     RANDU - from IBM Scientific Subroutine 
c     Package Programmer's Manual
c     1130-CM-02X - 5th ed, June 1970
c     http://media.ibm1130.org/1130-106-ocr.pdf

      SUBROUTINE RANDU(IX, IY, YFL)
      IY = IX * 899
      IF (IY) 5, 6, 6
 5    IY = IY + 32767 + 1
 6    YFL = IY
      YFL = YFL / 32727.
      RETURN
      END

(If you’re not hip to ye olde Fortran lingo, that bizarre-looking IF statement means IF (IY < 0) GO TO 5; IF (IY == 0) GO TO 6; IF (IY > 0) GO TO 6)

It accepts an odd number < 32768 as a seed, and always outputs an odd number. Yes, it basically multiplies by 899, and changes the sign if it rolls over. Umm …

There are two possible orbits for this PRNG, each 8192 entries long:

  1. Starting seed 1 (899, 21769, 7835, …, 18745, 9003, 1, 899)
  2. Starting seed 5 (4495, 10541, 6407, …, 28189, 12247, 5, 4495).

The plot above is the first series as X and the second as Y. I used INTEGER*2 types to simulate the 1130’s narrow integers.

“Well, that was unexpected …”: The Raspberry Pi’s Hardware Random Number Generator

Hey! This is a bit old! Things may have changed and I haven’t necessarily fixed them.

Most computers can’t create true random numbers. They use a formula which makes a very long stream of pseudo-random numbers, but real randomness comes from thermal noise in analogue components. The Raspberry Pi has such a circuit in its SoC, as it helps making the seed data for secure transactions. It was only recently that a driver for this circuit was supplied. To enable it (on Raspbian): I think the module is enabled by default now for the different versions of the SoC.

  1. Make sure your system is up to date with
    sudo apt-get update
    sudo apt -y upgrade
  2. Install the module:
    sudo modprobe bcm2708-rng
  3. To make sure it’s always loaded, add the following line to /etc/modules (editing as root):
    bcm2708-rng
  4. For some RNG-related stuff, install rng-tools:
    sudo apt-get install rng-tools

The /dev/hwrng device should now be available, but can only be read by the root user.

Nico pointed out that you also need to:

  1. Edit /etc/default/rng-tools, and remove the # at the start of the line
    HRNGDEVICE=/dev/hwrng
  2. Restart rng-tools with
    sudo service rng-tools restart

What random looks like

random20130606210642random20130606210630

Random data look pretty dull. Here are random RGB values made with:

sudo cat /dev/hwrng  | rawtoppm -rgb 256 256 | pnmtopng > random$(date +%Y%m%d%H%M%S).png

(you’ll need to install the netpbm toolkit to do this.)

What random sounds like

Two short WAV samples of, well, noise:

Yup, sounds like static. It was made with the rndsound.sh script. You’ll need to install sox to run it.

This is not random

If it sounds like static, and even if it sometimes looks like static, it may not actually be true random noise. An infamous case of a pseudo random number generator being not very random at all was RANDU, which at first glance appeared to produce nearly random results, but close study showed it to be very predictable.

I wrote (what I think to be) a C implementation of RANDU: randu.c. While it produces appropriately random-sounding audio data (randu17.wav), if you output it as an image:

randu17_rgbThose stripes are a giveaway; there should be no order in the output. (Then again, I have no idea if I’ve implemented RANDU correctly.) Testing random data is hard, then — you really need a barrage of tests, and even some of them might fail even for truly random output. Thankfully, when you installed rngtools, it included rngtest, a simple checker for random data:

sudo cat /dev/hwrng | rngtest -c 1000
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests…
rngtest: bits received from input: 20000032
rngtest: FIPS 140-2 successes: 1000
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=67.969; avg=921.967; max=1953125.000)Kibits/s
rngtest: FIPS tests speed: (min=842.881; avg=3208.336; max=6407.890)Kibits/s
rngtest: Program run time: 27658884 microseconds

We were lucky that none of the tests failed for that run; sometimes there are a few failures. RANDU, on the other hand fares very badly:

./randu 17  | rngtest -c 1000
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests…
rngtest: bits received from input: 20000032
rngtest: FIPS 140-2 successes: 0
rngtest: FIPS 140-2 failures: 1000
rngtest: FIPS 140-2(2001-10-10) Monobit: 730
rngtest: FIPS 140-2(2001-10-10) Poker: 1000
rngtest: FIPS 140-2(2001-10-10) Runs: 289
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=45.630; avg=14255.221; max=19073.486)Mibits/s
rngtest: FIPS tests speed: (min=23.694; avg=154.238; max=176.606)Mibits/s
rngtest: Program run time: 141071 microseconds

See? Lots of failures there. It’s hardly random at all. If you really want to get out testing randomness, there are the dieharder tests. They takes ages to run, though.

(Note: newish Intel machines also have a real hardware RNG in the shape of Rdrand.)

I trust you all got the obvious Strictly Ballroom reference in the title?