A Detailed Tutorial On Speeding Up AVR Division

July 15, 2012 by Brian Benchoff 32 Comments

[Alan Burlison] is working on an Arduino project with an accelerometer and a few LEDs. Having the LEDs light up as his board is tilted to one side or another is an easy enough project a computer cowboy could whip out in an hour, but [Alan] – ever the perfectionist – decided to optimize his code so his accelerometer-controlled LEDs don’t jitter. The result is a spectacular blog post chronicling the pitfalls of floating point math and division on an AVR.

To remove the jitter from his LEDs, [Alan] used a smoothing algorithm known as an exponential moving average. This algorithm uses multiplication and is usually implemented using floating point arithmetic. Unfortunately, AVRs don’t have floating point arithmetic so [Alan] used fixed point arithmetic – a system similar to balancing your checkbook in cents rather than dollars.

With a clever use of bit shifting to calculate the average with scaling, [Alan] was able to make the fixed point version nearly six times faster than the floating point algorithm implementation. After digging into the assembly of his fixed point algorithm, he was able to speed it up to 10 times faster than floating point arithmetic.

The takeaway from [Alan]’s adventures in arithmetic is that division on an AVR is slow. Not very surprising after you realize the AVR doesn’t have a division instruction. Of course, sometimes you can’t get around having to divide so multiplying by the reciprocal and using fixed point arithmetic is the way to go if speed is an issue.

Sure, squeezing every last cycle out of an 8 bit microcontroller is a bit excessive if you’re just using an Arduino as a switch. If you’re doing something with graphics or need very fast response times, [Alan] gives a lot of really useful tips.

Teaching A Computer To Learn

July 11, 2012 by Brian Benchoff 23 Comments

[Łukasz Kaiser] programmed a computer to play Tic-tac-toe. That doesn’t sound very remarkable until you realize he never told his computer the rules of Tic-tac-toe. The computer learned the rules by itself after watching a video of two people playing the game (link to actual paper – PDF warning).

[Łukasz] wrote a small program in C++ to recognize the placement of objects on a Tic-tac-toe, Connect 4, and Breakthough board. This program sifts through winning and losing games along with illegal moves to generate a Lambda calculus-like rule set for the relevant game. Even though [Łukasz] has only programmed a computer to learn simple games such as Tic-tac-toe, Connect 4, and Breakthrough, he plans to move up to more complex games such as Chess.

The fact that [Łukasz] programmed a computer to actually learn the rules of a game gives us pause; in one of the fabulous lectures [Richard Feynman] gave to freshman physics students in 1964, the subject of Chess came up. [Feynman] drew parallels between learning Chess and performing research. Every move is hypothesis testing, and when a very strange move occurs – castling, en passant, and the promotion of a pawn, for instance – the theory of the rules of the game must be reworked. Likewise, when extremely strange stuff happens in physics – particle/wave duality, and the existence of black holes – scientific theory is advanced.

Yes, teaching a computer to learn the rules of Tic-tac-toe may seem irrelevant, but given the same learning process can be applied to other fields such as medicine, economics, and just about every science, it’s not hard to see how cool [Łukasz]’ work is.

via extremetech

Video-based Radar For Your Car

July 9, 2012 by Brian Benchoff 28 Comments

[Gustaf] has been playing around with machine vision for a while and sent in his latest project in on our tip line. It’s a video based car radar system that can detect cars in a camera’s field of vision while cruising down the highway.

Like [Gustaf]’s previous experiments with machine vision where he got a computer to recognize and count yellow cylinders and green rectangles, the radar build uses ADABoost and the AForge AI/Machine Vision C# framework. [Gustef] used an evolutionary algorithm to detect the presence of a car in a video frame, first by selecting 150 images of cars from a pre-recorded video, and the another 1,850 images were selected by a computer and confirmed as a car by a human eye.

With 2000 images of cars in its database, [Gustaf]’s machine vision algorithm is able to detect a car in real-time as he drove down a beautiful Swedish highway. In addition to overlaying a rectangle underneath each car in a video frame and an awesome Terminator-style HUD in the upper right corner, [Gustaf] also a distance display above the hood of his car.

It’s an awesome build that makes us wonder if [Gustef] is building an autonomous car. Even if he’s not, it really makes us want to install a video HUD in our whip, just to see this in action.

On Not Designing Circuits With Evolutionary Algorithms

July 9, 2012 by Brian Benchoff 24 Comments

[Henrik] has been working on a program to design electronic circuits using evolutionary algorithms. It’s still very much a work in progress, but he’s gotten to the point of generating a decent BJT inverter after 78 generations (9 minutes of compute time), as shown in the .gif above.

To evolve these circuits, [Henrik] told a SPICE simulation to generate an inverter with a 5V power supply, 2N3904 and 2N3906 transistors, and whatever resistors were needed. The first dozen or so generations didn’t actually do anything, but after 2000 generations the algorithm produced a circuit nearly identical to the description of a CMOS inverter you’d find in a circuit textbook.

Using evolution to guide electronic design is nothing new; an evolutionary algorithm and a a few bits of Verilog can turn an FPGA into a chip that can tell the difference between a 1kHz and 10kHz tone with extremely minimal hardware requirements. There’s also some very, very strange stuff that happened in this experiment; the evolutionary algorithm utilized things that are impossible for a human to program and relies on magnetic flux and quantum weirdness inside the FPGA.

[Henrik] says his algorithm didn’t test for how much current goes through the transistors, so implementing this circuit outside of a simulation will destroy the transistors and emit a puff of blue smoke. If you’d like design your own circuits using evolution, [Henrik] put all the code in a git for your perusal. It’s damn cool as it stands now, and once [Henrik] includes checking current and voltage in each component his project may actually be useful.

Bootable Emulator For The DCPU

July 9, 2012 by Brian Benchoff 16 Comments

[Notch], the guy behind Minecraft, is currently working on a new game called 0x10c. This game includes an in-game 16-bit computer called the DCPU that hearkens back to the 1980s microcomputers with really weird hardware architecture. [Benedek] thought it would be a great idea to turn his ThinkPad into a DCPU, so he wrote a bootable x86 emulator for the DCPU that is fully compliant with the current DCPU spec.

This bootable DCPU emulator comes from the fruitful workshop of [Benedek], the brains behind drawing fractals on the DCPU, emulating bit-flipping radiation, and even putting the Portal end credits inside [notch]’s 0x10c computer.

[Benedek] wrote this new in x86 assembly, allowing it to be booted without an OS from a USB flash drive on any old laptop. This allows for direct hardware communication for everything implemented for the DCPU so far.

If you’d like to run your bare-metal DCPU, [Benedek] made all the files avaiable. Since the entire emulator is only 1800 lines of x86 assembly, it’s possible to load this off a floppy disk; an ancient tech we’ll be seeing in [notch]’s new game.

Oh. One more thing. When we were introduced to 0x10c, we said we’ll be holding a contest for the best hardware implementation of the DCPU. We’re still waiting on some of the hardware specs to be released (hard drives and the MIDI-based serial interface), so we’ll probably be holding that when there is a playable alpha release. [Benedek]’s bootable emulator is a great start, though.

The Effect Of Code On Power Consumption

June 14, 2012 by Brian Benchoff 36 Comments

Of course putting a microcontroller into sleep mode or changing the clock rate has an effect on the power consumption of the chip, but what about different bits of code? Is multiplying two numbers more efficient than adding them, and does ORing two values consume more power than NOPping? [jcw] wanted to compare the power draw of a microcontroller running different loops, so he threw some code on a JeeNode and hooked it up to an oscilloscope.

For his test, [jcw] tested two instructions: multiply and shift left. These loops run 50,000 and 5,000 times, respectively (bit shifting is really slow on ATMegas, apparently) and looked at the oscilloscope as the JeeNode was doing its work.

Surprisingly, there is a difference in power consumption between the multiply and shift loops. The shift loop draws 8.4 mA, while the multiply loop draws 8.8 mA. Not much, but clearly visible and measurable. While you’re probably not going to optimize the power draw of a project by only using low-power instructions, it’s still very interesting to watch a microcontroller do its thing.

Scraping Blogs For Fun And Profit

June 13, 2012 by Brian Benchoff 23 Comments

Sometimes when you’re working on a problem, a solution is thrown right at your face. We found ourselves in this exact situation a few days ago while putting together Hackaday’s new retro edition; a way to select a random Hackaday article was needed and [Alexander van Teijlingen] of codepanel.net just handed us the solution.

To grab every Hackaday URL ever, [Alex] wrote a small Python script using the Beautiful Soup screen scraping library. The program starts on Hackaday’s main page and grabs every link to a Hackaday post before going to the next page. It’s not a terribly complex build, but we’re gobsmacked a solution to a problem we’re working on would magically show up in our inbox.

Thanks to [Alex], writing a cron job to automatically update our new retro edition just got a whole lot easier. If you’d like to check out a list of every Hackaday post ever (or at least through two days ago), you can grab 10,693 line text file here.