The Two Component Random Number Generator

attiny10

[Karl] was in need of a hardware random number generator, but is needs had a few caveats: it needed to be cheap, and sufficiently random. Random number generation can get quite crazy with Geiger tubes, lava lamps, and radioactive decay, but a much smaller solution was found in an 8 pin AVR microcontroller.

The solution uses AVRentropy, a library that uses the watchdog timer’s jitter in AVR microcontrollers to provide cryptographically secure random numbers. Setting up the circuit was easy – an ATtiny45 microcontroller was connected to a cheap chinese USB to serial converter. Three wires, and the circuit is complete. The code was simple as well; it’s just a call to initialize the entropy and write the bits to the serial port.

There are a few drawbacks to this build. Because the entropy library must wait until enough entropy is gathered, it can only produce about two 32-bit numbers per second. That’s all [Karl] needed for his application, though, and with an enclosure made from a wine cork and marble, he has the prettiest and smallest random number generator around.

Pseudo-Random Flickering Jack-O-Lantern LED using ATtiny13

Pseudo_Random_Flicker_ATtiny13

It’s time to get those jack-o-lanterns twinkling for Halloween. If you don’t want to use candles or buy a jack-o-lantern light this Halloween you can do like [Johannes Bauer] and code your own pseudo-random flickering super bright LED. His wife wanted their pumpkin to be illuminated this year and he knew it would be easy to do with an Arduino, but that would be overkill for such a simple project. Plus, he doesn’t have an arduino. [Johannes] used very few components; 4 slightly depleted AA batteries, a super bright LED, 680 ohm resistor and a little custom code on an 8 pin ATtiny13. The circuit does work great for a pumpkin lantern but his video is more of a tutorial on coding linear congruential generator (LCG) for the 8 bit pseudo-random LED flickering.

The code is short and can be gleaned from the YouTube video. [Johannes] used avr-gcc to compile and has packaged his code and build scripts for download. The hex file can be flashed over to the chip using avrdude or AVR Studio. If you have any ATtiny13s lying around you should cobble this hack together just in time to emulate that real look of a pumpkin candle without the hassles and hazards of real flames.

If you want something with a lot more light that still has that candle like flicker then checkout “Flickering Pumpkin Lanterns” that used the signal from LED tea lights to power some 12 V lamps.

Follow along after the break to watch [Johannes Bauer’s] video.

[Read more...]

How the mazes were generated for classic Berzerk game

berzerk-random-maze

This is a screenshot from the Atari 5200 version of the classic game Berserk. But the write-up we’re featuring actually looks at the original coin-op version. The maze for each level was established on the fly using a seed number fed into a rudimentary algorithm . Here’s a close look at how the maze building code actually worked.

Recently we saw a talk by Pitfall creator [David Crane] as part of our Retrotechtacular series. That is a real gem of programming history, and one of our favorite take-aways was that the levels were not hardcoded, but built using a random number generator algorithm with a hardcoded seed (so that the game was the same each time you played it). This uses a similar method but with a somewhat random seed.

The maze building was reverse engineered by observing the game in a MAME emulator, and by digging through disassembled code. Each time the code is “cold started” the seed starts out at zero, but from there the room number is used as the next seed. This is fed through a very simple algorithm. It generates directions for the walls, which use s few bit-wise operations to add the pillars inside the rooms.

It’s a great thing to study if you’re writing games for your embedded projects. By generating the room programmatically you don’t use up as much program memory. Of course these days even simple hobby controllers have way more storage to work with than [Alan McNeil] had when he designed Berserk.

[via Reddit]

[Image Source]

Improved hourglass entropy

improved-hour-glass-entropy

[Wardy] built himself a high quality entropy source with parts he had lying around. It’s based on the hourglass entropy project we saw in a links post earlier this month. Just like that project, he is bouncing a laser off of the falling sand and reading the result. But he brings a few innovations to the party, and has test results to back up his work.

The first change is an obvious one; motorize the hourglass so that you don’t need to flip it by hand. We thought this might mess with the laser alignment but the clip after the break proved us wrong. He changed up the sensor, using an LED connected to the base of an NPN transistor. The next change was to mount the light sensor at an angle to the laser rather than straight on. This picks up reflections of the laser and not the direct beam itself, resulting in a wider range of readings.

He used an Ethernet shield to get the system on the network. It’s pushing 420k random numbers per second and was tested with the DieHarder suite. It didn’t get a very high score, but it did pass the test.

[Read more...]

Is entropy slowing down your Android device?

071210_1705_AndroidDev11.jpg

[Lambgx02] got tired of his Android device getting bogged down and decided to dig down to the cause of the issue. His investigation led him to believe that entropy is causing the slowdown. He believes that his workaround reduces 90% of the lag on the average Android device.

So how is it possible that entropy is causing the problem? It seems there is a bottleneck when an app requests a random number from the Linux kernel running at the lowest level of the device. Android is set up to use /dev/random for all random number requests, but [Lambgx02] says that location has a very shallow pool of numbers available. When they run out the kernel has to reload with a new seed and this is blocking the app that requested the data from continuing.

His solution was to write his own app that seeds /dev/random once every second using a number from /dev/urandom. He mentions that this might cause a security vulnerability as seeding the random data in this way is not quite as random. There may also be issues with battery life, so make sure to monitor performance if you give it a try.

[via Reddit]

Using a 555 timer and ADC as a random seed

Most toolchains for embedded system include support for random number generation. But if you’ve read the manual you’ll know that this is really just pseudo random number generation (PRNG). When calling this function the same numbers will always return in the same order unless a different random number seed is supplied in advance. [Gardner] put together a simple and cheap solution for deriving better random number seeds. He reads a voltage from a 555 timer using the ADC on the microcontroller. At first glance it may not seem like a great source of randomness, but he performed some testing and the results look quite promising.

The project is aimed at Arduino-based circuits, but any chip with an ADC will work. The 555 timer is used as a free running oscillator. We know that this not be very stable when compared to even the worst of crystal oscillators, but that’s what makes it work so well as a random seed source. Add to this the low parts count and small size of the additional circuitry and you’ve got a winning combination. So keep this in mind when you need a random number but don’t necessarily need rock solid entropy.

[via Reddit and Freetronics]

Generating random numbers from white noise

Even though rand() may be a good enough random number generator for making a video game, the patterns of random bits it spits out may not be sufficient for applications requiring truly random data. [Giorgio] built his own random number generator, and after many statistical tests it ended up being random enough for a few very complex calculations.

Previously, we saw [Giorgio] generate random numbers with a Chua circuit, but for all the complexity of building an electronic strange attractor there’s actually a much simpler source of random data: a white noise generator.

[Giorgio]‘s random number generator for this project is just a pair of resistors, with an op-amp buffer, amplifier, and current switch to turn analog data into a digital output of random 1s and 0s. [Giorgio] sampled this data by plugging the digital out into one of the GPIO pins of a Raspberry Pi and recording the data with s small script.

To verify his sequence of bits was actually random, [Giorgio] performed a few tests on the data, some more reliable in determining randomness than others.

Because every project needs a few awesome visualizations, [Giorgio] plotted each sequence of bits as either a black or white pixel in a bitmap. The resulting image certainly looks like television static, so there are no obvious problems with the data.

[Giorgio] also performed an interesting Monte Carlo simulation with his megabytes of random data: By plotting points on a plane (with a range from 0,0 to 1,1), [Giorgio] can approximate the value of π by testing if a point is inside a circle with a radius of 1. The best approximation of pi using 10,000 points of random data came out to be 3.1436

Of course [Giorgio] put his random data through a few proper statistical tests such as rngtest and dieharder, passing all the tests of randomness with flying colors. An interesting build that shows a small glimpse of how hard generating really random numbers actually is.