algorithm

35 Articles

Fitting A Spell Checker Into 64 KB

March 26, 2025 by 16 Comments

By some estimates, the English language contains over a million unique words. This is perhaps overly generous, but even conservative estimates generally put the number at over a hundred thousand. Regardless of where the exact number falls between those two extremes, it’s certainly many more words than could fit in the 64 kB of memory allocated to the spell checking program on some of the first Unix machines. This article by [Abhinav Upadhyay] takes a deep dive on how the early Unix engineers accomplished the feat despite the extreme limitations of the computers they were working with.

Perhaps the most obvious way to build a spell checker is by simply looking up each word in a dictionary. With modern hardware this wouldn’t be too hard, but disks in the ’70s were extremely slow and expensive. To move the dictionary into memory it was first whittled down to around 25,000 words by various methods, including using an algorithm to remove all affixes, and then using a Bloom filter to perform the lookups. The team found that this wasn’t a big enough dictionary size, and had to change strategies to expand the number of words the spell checker could check. Hash compression was used at first, followed by hash differences and then a special compression method which achieved an almost theoretically perfect compression.

Although most computers that run spell checkers today have much more memory as well as disks which are orders of magnitude larger and faster, a lot of the innovation made by this early Unix team is still relevant for showing how various compression algorithms can be used on data in general. Large language models, for one example, are proving to be the new frontier for text-based data compression.

Math On A Checkerboard

January 3, 2025 by 6 Comments

The word “algorithm” can sometimes seem like a word designed to scare people away from math classes, much like the words “calculus”, “Fourier transform”, or “engineering exam”. But in reality it’s just a method for solving a specific problem, and we use them all the time whether or not we realize it. Taking a deep dive into some of the ways we solve problems, especially math problems, often leads to some surprising consequences as well like this set of algorithms for performing various calculations using nothing but a checkerboard.

This is actually a demonstration of a method called location arithmetic first described by [John Napier] in 1617. It breaks numbers into their binary equivalent and then uses those representations to perform multiplication, division, or to take the square root. Each operation is performed by sliding markers around the board to form certain shapes as required by the algorithms; with the shapes created the result can be viewed directly. This method solves a number of problems with other methods of performing math by hand, eliminating other methods like trial-and-error. The video’s creator [Wrath of Math] demonstrates all of these capabilities and the proper method of performing the algorithms in the video linked below as well.

While not a “hack” in the traditional sense, it’s important to be aware of algorithms like this as they can inform a lot of the way the world works on a fundamental level. Taking that knowledge into another arena like computer programming can often yield some interesting results. One famous example is the magic number found in the code for the video game Quake, but we’ve also seen algorithms like this used to create art as well.

Continue reading “Math On A Checkerboard” →

Custom Drone Software Searches, Rescues

October 24, 2024 by 17 Comments

When a new technology first arrives in people’s hands, it often takes a bit of time before the full capabilities of that technology are realized. In much the same way that many early Internet users simply used it to replace snail mail, or early smartphones were used as more convenient methods for messaging and calling than their flip-phone cousins, autonomous drones also took a little bit of time before their capabilities became fully realized. While some initially used them as a drop-in replacement for things like aerial photography, a group of mountain rescue volunteers in the United Kingdom realized that they could be put to work in more efficient ways suited to their unique abilities and have been behind a bit of a revolution in the search-and-rescue community.

The first search-and-rescue groups using drones to help in their efforts generally used them to search in the same way a helicopter would have been used in the past, only with less expense. But the effort involved is still the same; a human still needed to do the searching themselves. The group in the UK devised an improved system to take the human effort out of the equation by sending a drone to fly autonomously over piece of mountainous terrain and take images of the ground in such a way that any one thing would be present in many individual images. From there, the drone would fly back to its base station where an operator could download the images and run them through a computer program which would analyse the images and look for outliers in the colors of the individual pixels. Generally, humans tend to stand out against their backgrounds in ways that computers are good at spotting while humans themselves might not notice at all, and in the group’s first efforts to locate a missing person they were able to locate them almost immediately using this technology.

Although the system is built on a mapping system somewhat unique to the UK, the group has not attempted to commercialize the system. MR Maps, the software underpinning this new feature, has been free to use for anyone who wants to use it. And for those just starting out in this field, it’s also worth pointing out that location services offered by modern technologies in rugged terrain like this can often be misleading, and won’t be as straightforward of a solution to the problem as one might think.

Supercon 2023: Teaching Robots How To Learn

September 3, 2024 by 2 Comments

Once upon a time, machine learning was an arcane field, the preserve of a precious few researchers holed up in grand academic institutions. Progress was slow, and hard won. Today, however, just about anyone with a computer can dive into these topics and develop their own machine learning systems.

Shawn Hymel has been doing just that, in his work in developer relations and as a broader electronics educator. His current interest is reinforcement learning on a tiny scale. He came down to the 2023 Hackaday Supercon to tell us all about his work.

Continue reading “Supercon 2023: Teaching Robots How To Learn” →

Robots Collaborate To Localize Themselves Precisely

August 26, 2024 by 3 Comments

Here’s the thing about robots. It’s hard for them to figure out where to go or what they should be doing if they don’t know where they are. Giving them some method of localization is key to their usefulness in almost any task you can imagine. To that end, [Guy Elmakis], [Matan Coronel] and [David Zarrouk] have been working on methods for pairs of robots to help each other in this regard.

As per the research paper, the idea is to perform real-time 3D localization between two robots in a given location. The basic idea is that the robots take turns moving. While one robot moves, the other effectively acts as a landmark. The robots are equipped with inertial measurement units and cameras in a turret, which they use to track each other and their own movements. Each robot is equipped with a Raspberry Pi 4 for processing image data and computing positions, and the two robots communicate via Bluetooth to coordinate their efforts.

It’s an interesting technique that could have some real applications in swarm robotics, and in operations in areas where satellite navigation and other typical localization techniques are not practical. If you’re looking for more information, you can find the paper here. We’ve seen some other neat localization techniques for small robots before, too. Video after the break.

Continue reading “Robots Collaborate To Localize Themselves Precisely” →

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” →