algorithm

37 Articles

50-Year-Old Program Gets Speed Boost

November 7, 2023 by 19 Comments

At first glance, getting a computer program to run faster than the first electronic computers might seem trivial. After all, most of us carry enormously powerful processors in our pockets every day as if that’s normal. But [Mark] isn’t trying to beat computers like the ENIAC with a mobile ARM processor or other modern device. He’s now programming with the successor to the original Intel integrated circuit processor, the 4040, but beating the ENIAC is still little more complicated than you might think with a processor from 1974.

For this project, the goal was to best the 70-hour time set by ENIAC for computing the first 2035 digits of pi. There are a number of algorithms for performing this calculation, but using a 4-bit processor and an extremely limited memory of only 1280 bytes makes a number of these methods impossible, especially with the self-imposed time limit. The limited instruction set is a potential bottleneck as well with these early processors. [Mark] decided to use [Fabrice Bellard]’s algorithm given these limitations. He goes into great detail about the mathematics behind this method before coding it in JavaScript. Generating assembly language from a working JavaScript was found to be fairly straightforward.

[Mark] is also doing a lot of work on the 4040 to get this program running as well, including upgrades to the 40xx tool stack, the compiler and linker, and an emulator he’s using to test his program before sending it to physical hardware. The project is remarkably well-documented, including all of the optimizations needed to get these antique processors running fast enough to beat the ENIAC. We won’t spoil the results for you, but as a hint to how it worked out, he started this project using the 4040 since his original attempt using a 4004 wasn’t quite fast enough.

Guitar Distortion With Diodes In Code, Not Hardware

August 23, 2023 by 14 Comments

Guitarists will do just about anything to get just the right sound out of their setup, including purposely introducing all manner of distortion into the signal. It seems counter-intuitive, but it works, at least when it’s done right. But what exactly is going on with the signal? And is there a way to simulate it? Of course there is, and all it takes is a little math and some Arduino code.

Now, there are a lot of different techniques for modifying the signal from an electric guitar, but perhaps the simplest is the humble diode clipping circuit. It just uses an op-amp with antiparallel diodes either in series in the feedback loop or shunting the output to ground. The diodes clip the tops and bottoms off of the sine waves, turning them into something closer to a square wave, adding those extra harmonics that really fatten the sound. It’s a simple hack that’s easy to implement in hardware, enough so that distortion pedals galore are commercially available.

In the video below, [Sebastian] explains that this distortion is also pretty easy to reproduce algorithmically. He breaks down the math behind this, which is actually pretty approachable — a step function with a linear part, a quadratic section, and a hard-clipping function. He also derives a second, natural exponent step function from the Schockley diode equation that is less computationally demanding. To implement these models, [Sebastian] chose an Arduino GIGA R1 WiFi, using an ADC to digitize the guitar signal and devoting a DAC to each of the two algorithms. Each distortion effect has its own charms; we prefer the harsher step function over the exponential algorithm, but different strokes.

Kudos to [Sebastian] for this easy-to-understand treatment of what could otherwise be a difficult subject to digest. We didn’t really expect that a guitar distortion pedal would lead down the rabbit hole to diode theory and digital signal processing, but we’re glad it did.

Continue reading “Guitar Distortion With Diodes In Code, Not Hardware” →

Formation Flying Does More Than Look Good

June 26, 2023 by 14 Comments

Seeing airplanes fly in formation is an exciting experience at something like an air show, where demonstrations of a pilot’s skill and aircraft technology are on full display. But there are other reasons for aircraft to fly in formation as well. [Peter] has been exploring the idea that formation flight can also improve efficiency, and has been looking specifically at things like formation flight of UAVs or drones with this flight planning algorithm.

Aircraft flying in formation create vortices around the wing tips, which cause drag. However, another aircraft flying through those vortices will experience less drag and more efficient flight. This is the reason birds instinctively fly in formation as well. By planning paths for drones which will leave from different locations, meet up at some point to fly in a more efficient formation, and then split up close to their destinations, a significant amount of energy can potentially be saved. Continue reading “Formation Flying Does More Than Look Good” →

Martian Wheel Control Algorithms Gain Traction

February 15, 2022 by 13 Comments

Imagine the scene: You’re puttering along in your vehicle when, at least an hour from the nearest help, one of your tires starts losing air. Not to worry! You’ve got a spare tire along with the tools and knowhow to change it. And if that fails, you can call roadside assistance. But what if your car isn’t a car, has metal wheels for which no spares are available, and the nearest help is 200 million miles away? You just might be a Jet Propulsion Laboratory Engineer on the Curiosity Mars Rover mission, who in 2017 was charged with creating a new driving algorithm designed to extend the life of the wheels.