On random numbers…

While hacking a small program today, I encountered something that I hadn’t seen in a while, so I thought I’d blog it:

My random number generator failed me!

I was implementing a little test program to generate some random terrain. The idea was pretty simple: initialize a square array to be all zero height. Set your position to be the middle of the array, then iterate by dropping a block in the current square, then moving to a randomly chosen neighbor. Keep doing this until you place as many blocks asu like (if you wander off the edge, I wrapped around to the other side), and you are mostly done (well, you can do some post processing/erosion/filtering).

When I ran my program, it generated some nice looking islands, but as I kept iterating more and more, it kept making the existing peaks higher and higher, but never wandered away from where it began, leaving many gaps with no blocks at all. This isn’t supposed to happen in random walks: in the limit, the random walk should visit each square on the infinite grid (!) infinitely often (at least for grids of dimension two or less).

A moment’s clear thought suggeseted what the problem was. I was picking one of the four directions to go in the least complicated way imaginable:

dir = lrand48() & 3 ;

In other words, I extracted just the lowest bits of the lrand48() call, and used them as an index into the four directions. But it dawned on me that the low order bits of the lrand48() all aren’t really all that random. It’s not really hard to see why in retrospect: lrand48() and the like use a linear congruential generator, and they have notoriously bad performance in their low bits. Had I used the higher bits, I probably would never have noticed, but instead I just shifted to using the Mersenne Twister code that I had lying around. And, it works much better, the blocks nicely stack up over the entire 5122 array, into pleasing piles.

Here’s one of my new test scenes:

Much better.

Nano-Satellite Launch Challenge

Apparently NASA is sponsoring the development of nanosatellite launch capabilities by sponsoring a two million dollar prize purse for the first team to launch a standard 1U Cubesat into orbit (payloads must complete at least one orbit) twice in a week.

NASA – Nano-Satellite Launch Challenge.

I found out about this by reading the Team Phoenicia blog, which announced an upcoming seminar on the Nanosatellite Launcher Challenge in cooperation with the Menlo Park Techshop. I’d love to attend, but sadly I’ve got another cool event booked for that weekend.

Draft Agenda for the Team Phoenicia/Techshop Nanosatellite Launcher Seminar

Another nifty balloon project…

Luke Gesissbuhler did a balloon launch, lofting an HD video camera and an Apple iPhone to lofty heights before recovering them. Very nice. The footage right after burst was kind of cool: I was wondering whether the fragments of the balloon or parachute tangled with the camera: perhaps dangling the camera on a longer tether could reduce the possibility of them tangling. Still, it all worked out in the end (and rather brilliantly!).

Inspirational.

Homemade Spacecraft from Luke Geissbuhler on Vimeo.