Our Favorite Things: Binary Search

March 16, 2022 by Elliot Williams 34 Comments

You might not think that it would be possible to have a favorite optimization algorithm, but I do. And if you’re well-versed in the mathematical art of hill climbing, you might be surprised that my choice doesn’t even involve taking any derivatives. That’s not to say that I don’t love Newton’s method, because I do, but it’s just not as widely applicable as the good old binary search. And this is definitely a tool you should have in your toolbox, too.

Those of you out there who slept through calculus class probably already have drooping eyelids, so I’ll give you a real-world binary search example. Suppose you’re cropping an image for publication on Hackaday. To find the best width for the particular image, you start off with a crop that’s too thin and one that’s too wide. Start with an initial guess that’s halfway between the edges. If this first guess is too wide, you split the difference again between the current guess and the thinnest width. Updated to this new guess, you split the differences again.

But let’s make this even more concrete: an image that’s 1200 pixels wide. It can’t get wider than 1200 or thinner than 0. So our first guess is 600. That’s too thin, so we guess 900 — halfway between 600 and the upper limit of 1200. That ends up too wide, so we next guess 750, halfway between 600 and 900. A couple more iterations get us to 675, then 638, and then finally 619. In this case, we got down to the pixel level pretty darn fast, and we’re done. In general, you can stop when you’re happy, or have reached any precision goal.

[Ed note: I messed up the math when writing this, which is silly. But also brought out the point that I usually round the 50% mark when doing the math in my head, and as long as you’re close, it’s good enough.]

What’s fantastic about binary search is how little it demands of you. Unlike fancier optimization methods, you don’t need any derivatives. Heck, you don’t even really need to evaluate the function any more precisely than “too little, too much”, and that’s really helpful for the kind of Goldilocks-y photograph cropping example above, but it’s also extremely useful in the digital world as well. Comparators make exactly these kinds of decisions in the analog voltage world, and you’ve probably noticed the word “binary” in binary search. But binary search isn’t just useful inside silicon. Continue reading “Our Favorite Things: Binary Search” →

Linux Fu: Simple Pipes

March 16, 2022 by Al Williams 15 Comments

In the old days, you had a computer and it did one thing at a time. Literally. You would load your cards or punch tape or whatever and push a button. The computer would read your program, execute it, and spit out the results. Then it would go back to sleep until you fed it some more input.

The problem is computers — especially then — were expensive. And for a typical program, the computer is spending a lot of time waiting for things like the next punched card to show up or the magnetic tape to get to the right position. In those cases, the computer was figuratively tapping its foot waiting for the next event.

Someone smart realized that the computer could be working on something else while it was waiting, so you should feed more than one program in at a time. When program A is waiting for some I/O operation, program B could make some progress. Of course, if program A didn’t do any I/O then program B starved, so we invented preemptive multitasking. In that scheme, program A runs until it can’t run anymore or until a preset time limit occurs, whichever comes first. If time expires, the program is forced to sleep a bit so program B (and other programs) get their turn. This is how virtually all modern computers outside of tiny embedded systems work.

But there is a difference. Most computers now have multiple CPUs and special ways to quickly switch tasks. The desktop I’m writing this on has 12 CPUs and each one can act like two CPUs. So the computer can run up to 12 programs at one time and have 12 more that can replace any of the active 12 very quickly. Of course, the operating system can also flip programs on and off that stack of 24, so you can run a lot more than that, but the switch between the main 12 and the backup 12 is extremely fast.

So the case is stronger than ever for writing your solution using more than one program. There are a lot of benefits. For example, I once took over a program that did a lot of calculations and then spent hours printing out results. I spun off the printing to separate jobs on different printers and cut like 80% of the run time — which was nearly a day when I got started. But even outside of performance, process isolation is like the ultimate encapsulation. Things you do in program A shouldn’t be able to affect program B. Just like we isolate code in modules and objects, we can go further and isolate them in processes.

Doubled-Edged Sword

But that’s also a problem. Presumably, if you want to have two programs cooperate, they need to affect each other in some way. You could just use a file to talk between them but that’s notoriously inefficient. So operating systems like Linux provide IPC — interprocess communications. Just like you make some parts of an object public, you can expose certain things in your program to other programs.

Continue reading “Linux Fu: Simple Pipes” →

Tech In Plain Sight: Tough As Nails

March 15, 2022 by Al Williams 17 Comments

When you think of machines you see around you every day, you probably think about your car, computer, or household appliances. However, the world is full of simple machines. One simple machine in particular, the inclined plane, shows up a lot. For example, think of the humble nail. If you are a woodworker or even a homeowner you probably have bags of them. They certainly are all around you if you are indoors and maybe even if you are outdoors right now. Nails have been the fastener of choice for a very long time and they are a form of a wedge which is a type of inclined plane.

What else can you say about nails? Turns out, there is a lot to know. Like other fasteners, there are nails for very specific purposes. There are even nails with two heads and — no kidding — nails with two points. Exactly what kind of nail you need depends on what you are doing and what’s important to you.

Continue reading “Tech In Plain Sight: Tough As Nails” →

Illustrated Kristina with an IBM Model M keyboard floating between her hands.

Keebin’ With Kristina: The One With The Really Tall Keycaps

March 14, 2022 by Kristina Panos 5 Comments

About a month ago, [Unexpected Maker] finished their TinyS3, an ESP32-S3 development board. Since the chip supports both true USB and Bluetooth, [deʃhipu] wondered how well it would work in a keyboard.

Thus, the Vegemite Sandwich was made, perhaps while [deʃhipu] was dreaming of traveling in a fried-out Kombi. But really, it was named so because [Unexpected Maker] hails from Australia.

This is [deʃhipu]’s first time using switch sockets, which is (as far as we know) the only choice when it comes to hot-swappable Kailh chocs. We’ll be watching this one with hungry eyes.

Continue reading “Keebin’ With Kristina: The One With The Really Tall Keycaps” →

Open Source ASICs Hack Chat With Matt Venn

March 14, 2022 by Dan Maloney No comments

Join us on Wednesday, March 16 at noon Pacific for the Open Source ASICs Hack Chat with Matt Venn!

When it comes to electronic designs, most of us are content to make (sometimes) useful circuits using chips that were designed by someone else. That’s the beauty of this game, really — a lot of the hard work has already been done for you in the form of microcontrollers, gates, memory, amps, and timers that are all well-characterized, cheap, and readily available. Well, maybe not that last one right now…

Supply chain issues notwithstanding, though, there’s plenty to be said for designing your own silicon. It’s not for everyone, of course, but if you need something custom, something that nobody else has ever dreamed up, then you really might want to consider rolling your own. Trouble is, most of us don’t really have the tools to design something as exquisitely complicated as a silicon chip, and we don’t exactly have access to a multi-billion dollar fab plant to spin up a couple when the whim strikes.

Or do we? As it turns out, we all do have access to the tools and technologies needed to turn our designs into silicon. We just need a little guidance, like that offered by Matt Venn and his “Zero to ASIC” course. You’ll no doubt recall that Matt made appearances at both the 2020 and the 2021 Remoticons to talk about his efforts, and his recent partial success with his application-specific integrated circuit (ASIC). Now’s your chance to ask Matt questions about the process, what the course is all about, and how you can make your silicon dreams come true.

Our Hack Chats are live community events in the Hackaday.io Hack Chat group messaging. This week we’ll be sitting down on Wednesday, March 16 at 12:00 PM Pacific time. If time zones have you tied up, we have a handy time zone converter. Reminder: this is the first Hack Chat this year after the time change in North America, so check carefully.

Continue reading “Open Source ASICs Hack Chat With Matt Venn” →

Hackaday Links: March 13, 2022

March 13, 2022 by Dan Maloney 13 Comments

As Russia’s war on Ukraine drags on, its knock-on effects are being felt far beyond the eastern Europe theater. And perhaps nowhere is this more acutely felt than in the space launch industry, seeing that at least until recently, Russia was pretty much everyone’s go-to ride to orbit. All that has changed now, at least temporarily, and has expanded to include halting sales of rocket engines used in other nations’ launch vehicles. Specifically, Roscosmos has put an end to exports of the RD-180 engine used in the US Atlas V launch vehicle, along with the RD-181 thrusters found in the Antares rocket. The loss of these engines may be more symbolic than practical, at least for the RD-180 — United Launch Alliance stopped selling launches on Atlas V back last year, and had secured the engines it needed for the 29 flights it has booked by that April. Still, there’s some irony that the Atlas V, which started life as an ICBM aimed at the USSR in the 1950s, has lost its Russian-made engines.

Bad news for Jan Mrázek’s popular open-source parametric search utility which made JLCPCB’s component library easier to use. We wrote about it back in 2020, and things seemed to be going fine up until this week, when Jan got a take-down request for his service. When we first heard about this, we checked the application’s web page, which bore a big red banner that included what were apparently unpleasant accusations Jan had received, including the words “reptile” and “parasitic.” The banner is still there, but the text has changed to a more hopeful tone, noting that LCSC, the component supplier for JLC’s assembly service, objected to the way Jan was pulling component data, and that they are now working together on something that everyone can be happy with. Here’s hoping that the service is back in action again soon.

Good news, everyone: Epson is getting into the 3D printer business. Eager to add a dimension to the planar printing world they’ve mostly worked in, they’ve announced that they’ll be launching a direct-extrusion printer sometime soon. Aimed at the industrial market, the printer will use a “flat screw extruder,” which is supposed to be similar to what the company uses on its injection molding machines. We sure didn’t know Epson was in the injection molding market, so it’ll be interesting to see if expertise there results in innovation in 3D printing, especially if it trickles down to the consumer printing market. Just as long as they don’t try to DRM the pellets, of course.

You can’t judge a book by its cover, but it turns out that there’s a lot you can tell about a person’s genetics just by looking at their face. At least that’s according to an AI startup called FDNA, which makes an app called “Face2Gene” that the company claims can identify 300 genetic disorders by analyzing photos of someone’s face. Some genetic disorders, like Down Syndrome, leave easily recognizable facial features, but some changes are far more subtle and hard to recognize. We had heard of cases where photos of toddlers posted on social media were used to diagnose retinoblastoma, a rare cancer of the retina. But this is on another level entirely.

And finally, working in an Amazon warehouse has got to be a tough gig, and if some of the stories are to be believed, it borders on being a horror show. But one Amazonian recently shared a video that showed what it’s like to get trapped by his robotic coworkers. The warehouse employee somehow managed to get stuck in a maze created by Amazon’s pods, which are stacks of shelves that hold merchandise and are moved around the warehouse floor by what amounts to robotic pallet jacks. Apparently, the robots know enough to not collide with their meat-based colleagues, but not enough to not box them in. To be fair, the human eventually found a way out, but it was a long search and it seems like another pod could have moved into position to block the exit at any time. You could see it as a scary example of human-robot interaction gone awry, but we prefer to look at it as the robots giving their friend a little unscheduled break away from the prying eyes of his supervisor.

Retrotechtacular: Measuring TV Audiences With The “Poll-O-Meter”

March 12, 2022 by Dan Maloney 21 Comments

It may come as a shock to some, but TV used to be a big deal — a very big deal. Sitting down in front of the glowing tube for an evening’s entertainment was pretty much all one had to do after work, and while taking in this content was perhaps not that great for us, it was a goldmine for anyone with the ability to monetize it. And monetize it they did, “they” being the advertisers and marketers who saw the potential of the new medium as it ramped up in early 1950s America.

They faced a bit of a problem, though: proving to their customers exactly how many people they were reaching with their ads. The 1956 film below shows one attempt to answer that question with technology, rather than guesswork. The film features the “Poll-O-Meter System,” a mobile electronic tuning recorder built by the Calbest Electronics Company. Not a lot of technical detail is offered in the film, which appears aimed more at the advertising types, but from a shot of the Poll-O-Meter front panel (at 4:12) and a look at its comically outsized rooftop antenna (12:27), it seems safe to assume that it worked by receiving emissions from the TV set’s local oscillator, which would leak a signal from the TV antenna — perhaps similar to the approach used by the UK’s TV locator vans.

The Poll-O-Meter seems to have supported seven channels; even though there were twelve channels back in the day, licenses were rarely granted for stations on adjacent channels in a given market, so getting a hit on the “2-3” channel would have to be considered in the context of the local market. The Poll-O-Meter had a charming, homebrew look to it, right down to the hand-painted logos and panel lettering. Each channel had an electromechanical totalizing counter, plus a patch panel that looks like it could be used to connect different counters to different channels. There even appears to be a way to subtract counts from a channel, although why that would be necessary is unclear. The whole thing lived in the back of a 1954 VW van, and was driven around neighborhoods turning heads and gathering data about what channels were being watched “without enlisting aid or cooperation of … users.” Or, you know, their consent.

It was a different time, though, which is abundantly clear from watching this film, as well as the bonus ad for Westinghouse TVs at the end. The Poll-O-Meter seems a little silly now, but don’t judge 1956 too hard — after all, our world is regularly prowled by equally intrusive and consent-free Google Street View cars. Still, it’s an interesting glimpse into how one outfit tried to hang a price tag on the eyeballs that were silently taking in the “Vast Wasteland.”

Continue reading “Retrotechtacular: Measuring TV Audiences With The “Poll-O-Meter”” →