Around here we mostly enjoy slide rules. We even have our own collections including some cylindrical and circular ones. But [Mathologer] discusses a recent Reddit post that explains a circular slide rule-like device using a wheel and a stretchable rubber band. While it probably would be difficult to build the actual device using a rubber band, it can do wonders for your understanding of logarithms which still show up in our lives when, for example, you are calculating decibels. [Dimitri] did simulate the rubber band for you in software.
The idea is that a perfect rubber band has numbers from 0 to 10 evenly marked on it. As you rotate a wheel attached at the 10 mark, the rubber band stretches more and more. So the 10 and the 9 have relatively little space between them, but the 1 and the 2 are much further apart. The wheel’s circumference is set so that the 1 will exactly overlay the 10. What this means is that each spot on the wheel can represent any number that differs only by a decimal point. So you could have 3 mean 0.03, 300, or — of course — 3. Of course, you don’t need to build the wheel with a rubber band — you could just mark the wheel like a regular circular slide rule.
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”→
[Paul Curtis] over at Segger has an interesting series of blog posts about calculating division. This used to be a hotter topic, but nowadays many computers or computer languages have support for multiplication and division built-in. But some processors lack the instructions and a library to do it might be less than ideal. Knowing how to roll your own might allow you to optimize for speed or space. The current installment covers using Newton’s algorithm to do division.
Steve Martin had a famous bit about how to be a millionaire and never pay taxes. He started out by saying, “First… get a million dollar. Then…” This method is a bit like that since you first have to know how to multiply before you can divide. The basic premise is twofold: Newton’s method let you refine an estimate of a reciprocal by successive multiplications and then multiplying a number a reciprocal is the same as dividing. In other words, if we need to divide 34 by 6, you could rewrite 34/6 to 34 * 1/6 and the answer is the same.
People tend to obsess over making computer software faster. You can, of course, just crank up the clock speed and add more processors, but often the most powerful way to make something faster is to find a better way to do it. Sometimes those methods are very different from how a human being would do the same task, but it suits the computer’s capabilities. [Nemean] has a video explaining a better multiplication algorithm known as Karatsuba’s algorithm and it is actually quite clever. You can see the video below.
To help you understand the algorithm, the video shows a simple two-digit by two-digit multiplication. You can see that the first and last digits are essentially the result of one multiplication. It is all the intermediate digits that add together. The only thing that might change the first digit is a carry.
The electronics hobby has changed a lot since the advent of the microprocessor. Before that — and with the lack of large-scale integrated circuits — projects in magazines tended to be either super simple or ultra complex. However, one popular type of project dealt with music synthesis. Fairly simple circuits could combine to make a complex synthesizer so it was sort of the best of both worlds. Nowadays, you are more likely to tackle a music synthesizer in software like [Tim] did when he created Abelton in Web Assembly and C++. Along the way, he learned a lot about the relationship between math and music.
[Tim] covers what he learned about the Nyquist theorem and how to keep synthesis data flowing in real time with buffers. However, there are some problems trying to do all this in a cross-browser context. The AudioWorklet class appears to have widespread support, though, and [Tim] managed to get that working.
Programmer [aemkei] Tweeted the formula(x ^ y) % 9alongside code for more “alien art”. But how can a formula as simple as (x ^ y) % 9 result in a complex design? The combination of Bitwise XOR (^) and Modulo (%) generate a repeating pattern that’s still complex enough to satisfy the eye, and it’s ok if that doesn’t sound like an explanation. Bitwise operations are useful when working with memory and shift registers, but also worth learning if you want to drive lines or matrices of LEDs or interpret combinations of multiple switches, or in this case a great way to throw an interesting test pattern up on a new flip-dot display or low-res LED matrix. Are you into it? We are, so let’s jump in.
XOR Truth Table
0b00
0b01
0b10
0b11
0b00
0b00
0b01
0b10
0b11
0b01
0b01
0b00
0b11
0b10
0b10
0b10
0b11
0b00
0b01
0b11
0b11
0b10
0b01
0b00
Bitwise XOR compares each binary digit of the two inputs. The XOR returns a 1 when only one of the two digits is a 1, otherwise, it returns a zero for that position. Let’s say the coordinates were 3, 2. Converted to binary we have 0b11 and 0b10. From this truth table, we can see the most-significant digits are both 1, returning a 0, while only one of the least-significant digits is a 1, so the comparison returns a 1.
Moving onto the %, which is the Modulo operator has nothing to do with percentages. This operator divides two numbers and returns the remainder if any. Take 9 % 5. When dividing 9 by 5, 5 goes in once with a remainder of 4 so 9 % 5 = 4. Now our original formula from the top will draw a black box for every ninth number except that the bitwise XOR throws a wrench into that count, varying how often a number divisible by 9 appears and supplying the complexity necessary for these awesome patterns.
What are the most interesting designs can you create in a simple formula?
It’ll be Pi Day when this article goes live, at least for approximately half the globe west of the prime meridian. We always enjoy Pi Day, not least for the excuse to enjoy pie and other disc-shaped foods. It’s also cool to ponder the mysteries of a transcendental number, which usually get a good treatment by the math YouTube community. This year was no disappointment in this regard, as we found two good pi-related videos, both by Matt Parker over at Standup Maths. The first one deals with raising pi to the pi to the pi to the pi and how that may or may not result in an integer that’s tens of trillions of digits long. The second and more entertaining video is a collaboration with Steve Mould which aims to estimate the value of pi by measuring the volume of a molecular monolayer of oleic acid floating on water. The process was really interesting and the results were surprisingly accurate; this might make a good exercise to do with kids to show them what pi is all about.
Remember basic physics and first being exposed to the formula for universal gravitation? We sure do, and we remember thinking that it should be possible to calculate the force between us and our classmates. It is, of course, but actually measuring the attractive force would be another thing entirely. But researchers have done just that, using objects substantially smaller than the average high school student: two 2-mm gold balls. The apparatus the Austrian researchers built used 90-milligram gold balls, one stationary and one on a suspended arm. The acceleration between the two moves the suspended ball, which pivots a mirror attached to the arm to deflect a laser beam. That they were able to tease a signal from the background noise of electrostatic, seismic, and hydrodynamic forces is quite a technical feat.
We noticed a lot of interest in the Antikythera mechanism this week, which was apparently caused by the announcement of the first-ever complete computational model of the ancient device’s inner workings. The team from University College London used all the available data gleaned from the 82 known fragments of the mechanism to produce a working model of the mechanism in software. This in turn was used to create some wonderful CGI animations of the mechanism at work — this video is well worth the half-hour it takes to watch. The UCL team says they’re now at work building a replica of the mechanism using modern techniques. One of the team says he has some doubts that ancient construction methods could have resulted in some of the finer pieces of the mechanism, like the concentric axles needed for some parts. We think our friend Clickspring might have something to say about that, as he seems to be doing pretty well building his replica using nothing but tools and methods that were available to the original maker. And by doing so, he managed to discern a previously unknown feature of the mechanism.
We got a tip recently that JOGL, or Just One Giant Lab, is offering microgrants for open-source science projects aimed at tackling the problems of COVID-19. The grants are for 4,000€ and require a minimal application and reporting process. The window for application is closing, though — March 21 is the deadline. If you’ve got an open-source COVID-19 project that could benefit from a cash infusion to bring to fruition, this might be your chance.
And finally, we stumbled across a video highlighting some of the darker aspects of amateur radio, particularly those who go through tremendous expense and effort just to be a pain in the ass. The story centers around the Mt. Diablo repeater, an amateur radio repeater located in California. Apparently someone took offense at the topics of conversation on the machine, and deployed what they called the “Annoy-o-Tron” to express their displeasure. The device consisted of a Baofeng transceiver, a cheap MP3 player loaded with obnoxious content, and a battery. Encased in epoxy resin and concrete inside a plastic ammo can, the jammer lugged the beast up a hill 20 miles (32 km) from the repeater, trained a simple Yagi antenna toward the site, and walked away. It lasted for three days and while the amateurs complained about the misuse of their repeater, they apparently didn’t do a thing about it. The jammer was retrieved six weeks after the fact and hasn’t been heard from since.
