I recently discovered Temu — a site selling miscellanea at often hard-to-believe low prices. A lot of what they sell is standard Dollar Store fare (plastic kitchen implements and small metal tea infusers and such), but they also have some interesting STEM items for sale.
One gizmo that caught my eye was a “three-phase power generator” demonstrator. It’s a set of nine coils grouped into three phases around a stator, with an outrunner magnet rotor. Spin the rotor and the coils generate three-phase power, suitable to light some LEDs or perhaps (with some power conditioning) charge a phone or other USB device.
A small three-phase generator. They even include a LED to show that it works.
The generator comes apart easily, to show the coil configuration.
To show the sequential activation of the coil groups, I connected three red LEDs with consistent polarity from A-B, B-C, and C-A. I drove the generator shaft with a cordless drill set to a relatively low speed (just enough to provide sufficient voltage to light the LEDs), and filmed it with my phone in “Slow Motion” mode. This was enough to see the phase sequence of the coil activations. (With another set of three LEDs in the reverse direction, you could see the other half of the three phases, as well.)
Calculating sequences like the Fibonacci numbers sounds straightforward enough. If we call the Nth Fibonacci number F(n), then they’re defined as F(0)=F(1)=1; F(n), for N greater than 1, is F(n-1)+F(n-2). So, F(2)=F(1)+F(0)=2; F(3)=F(2)+F(1)=3; etc.
The sequence is recursively defined, but if you code it up that way, you run into a problem. Naïve use of the recursive Fibonacci algorithm is horrendously inefficient. Say you’re computing F(5). Well, that’s F(4)+F(3). Easy. Except you need F(4) and F(3). F(4) is F(3)+F(2) and F(3) is F(2)+F(1). With each level, the number of calls to the function doubles.
This is O(2^N), which means that computing the function for large values of N will be prohibitively slow for some reasonable value of N, even if you have an amazingly fast computer. Recursive Fibonaccis are manageable for F(5), hairy for F(10), and F(40) and above will slow down even a modern Core i9 workstation to a crawl.
The solution is to cache your results. Whenever you calculate a Fibonacci number, store its result in memory. Now, when calculating F(5), we have F(4) and F(3) in memory, and merely have to perform an addition to calculate F(5), instead of the whole pyramid of recursive lookups. Recursive O(2^N) calculations like this are simply not feasible if done in the usual straightforward way — calculating one term of the sequence could take longer than the projected lifetime of the universe. With caching, each term is simply two array lookups and an addition, and happens in almost no time at all.
The drawback is that these arrays can get very large. Exploring the Hofstadter Q sequence, I read that the existence of numbers Q(n) in the sequence has been proven up to 10^10. Ten billion is a fairly low number in terms of these things — but that’s still some 80GB of memory. Each term in the sequence has to be stored, which uses eight bytes of memory for a 64-bit unsigned integer. (32-bit numbers aren’t large enough.)
The Hofstadter Q sequence is more convoluted than the Fibonaccis. It is defined as Q(1)=Q(2)=1, and Q(n>2)=Q(n-Q(n-1))+Q(n-Q(n-2)). So the preceding two terms tell the algorithm how far back in the sequence to go to find the two terms to add. With Fibonaccis, it’s enough to keep the previous two terms in memory. Not so for the Hofstadter Q sequence — it’s unclear as yet just how far back you would need to go, so you may need the whole sequence.
It’s apparently not currently known whether Q(n) is even defined for all n (although it most likely is). According to the Online Encyclopedia of Integer Sequences (OEIS) page, Roman Pearce had computed that a(n) exists for n <= 10^10 as of August 2014.
I was able to extend this result to 2×10^10, and confirm that Q(n) does extend at least that far. It may be possible to extend this somewhat farther, but the cache is getting unwieldy for a workstation with “only” 64GB of physical memory — the commit size is over 200GB.
Last weekend, on a whim, I asked GPT-4 “Please teach me how to create simple neural networks in Python using PyTorch.” I wasn’t sure how well that would go, but figured it was worth a try.
I not only learned how to do that, but found out that GPT-4, at least when it isn’t making things up, is an amazing tutor. It not only provided the relevant code, but explained how it works, helped walk me through some snags installing the required libraries, and is continuing to explain how to tweak the code to implement new features of PyTorch for more efficient network training. I can now analyze arbitrary .csv file data with neural networks. Amazing.
I had heard that, given sufficient data, a complex enough network, and enough training time, neural networks can learn the patterns underlying almost anything. So I decided to see how well it would do with the task I always start out with when learning a new language — generating images of the Mandelbrot Set.
An image of the Mandelbrot Set, as imagined by a 1500-neuron network.
That’s far from the best image of the Mandelbrot Set I’ve ever created — but there’s a reason. As JFK said, we do such things “not because they are easy, but because they are hard.” The Mandelbrot Set is, after all, a literally infinitely-complex object. Keep zooming in, and there will always be more somewhat-similar-but-not-quite-identical detail.
Creating such images is traditionally done by calculating the number of iterations for each point in the image, and coloring the point accordingly. The neural-network approach I used (which to be clear is not even approximately the most efficient way to do it) does it somewhat differently. Data on millions of randomly-chosen points and their associated iteration levels is stored in a .csv file. This file is then read into memory and used as the training (and verification) dataset to train a feedforward neural network to learn what iteration levels are associated with what points. Then, when training is done, this network is used as the function to draw the Set — it is queried for each point in the image instead of doing the iteration calculations for that point.
This network doesn’t have vision. It is given a pair of numbers (representing the location in the complex plane) and outputs a single number (its guess at the iteration level). The image is somewhat unclear because it was, in effect, drawn by an “artist” who cannot see. It learned, through massively-repeated trials, what the Set looks like. Nobody “told” it, for example, that the Set is symmetrical about the X axis. It is, but the network had to figure that out for itself.
At first, the images only approximately resembled the Mandelbrot Set. But neural network design is still very much an art as well as a science (at least for now), so increasing the width and depth and switching to Kaiming initialization (to avoid the vanishing gradient problem) resulted in an image that meets my initial goal: the locations of the second-level Mandelbrot lakes are visible. The coloration at the edges even hints at the infinitely-thin “Devil’s Polymer” links that connect the mini-lakes to the main lobes.
GPT-4 still does get some things wrong. When asking it to guide me through tasks like obtaining a diamond pickaxe and then an Elytra in Minecraft (tasks that I know well), it mostly did a good job, but didn’t seem to know, for example, that hunger, Endermen, and Pillagers are not things that you have to be concerned about when playing on Peaceful mode. But even so, I was able to follow its directions to accomplish those goals.
This is a new form of intelligence, if perhaps not sentience just yet. I’ve often said that I love living in the future. It just got dramatically more futuristic.
You want to swap them so that A becomes B and B becomes A, but you don’t have any extra memory. If you start with A=B , for instance, the information that was in A is lost.
Can this be done? Surprisingly, yes, using the XOR swap algorithm:
A = A XOR B; B = B XOR A; A = A XOR B;
A is first changed to be a bitwise XOR of itself and B. As long as B is still available, the information in A could be recovered by repeating the operation.
Next, B is XORed with the new value of A. This leaves B with the information that was originally in A. Since A still contains the combination, both pieces of information are still recoverable.
Finally, A is XORed with B. Since B contains the original value that was in A, A will now contain the other half of the information — the value originally in B.
Now, for the story behind the story…
The idea, once known, is easy enough to prove — but I wanted to know who had come up with it. I tried asking ChatGPT, and it knew exactly the algorithm I was talking about, and rephrased what it does. It then very confidently said that it was discovered by Richard Hamming in the 1950s, and gave textbook and paper citations of his to back it up.
Very impressive — except it seems to be a hallucination. Maybe Hamming did discover the XOR swap. It wouldn’t surprise me at all. (After all, he’s the Hamming in “Hamming codes.” But the two references ChatGPT gave were duds. Hamming does mention XOR in his book on communications, but only briefly, where it is relevant to error-correcting codes.
