Cache And Carry

Posted on 2023-06-30 by M. Eric Carr

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.

I’m reminded of Seymour Cray’s (NSFW but 100% true) quote about memory…

Posted in Algorithms, BASIC, Coding, Math | Leave a comment

Neural-Network Fractals

Posted on 2023-05-30 by M. Eric Carr

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.

Posted in Algorithms, Coding, Fractals, Machine Learning / Neural Networks, Minecraft, Python | Tagged , , , , , | Leave a comment

The Old XOR Switcheroo

Posted on 2023-04-24 by M. Eric Carr

Suppose you have two binary integers A and B.

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.

Posted in Algorithms, Assembly, Coding, Digital, Math | Tagged , , , | Leave a comment

Kilofarad

Posted on 2023-03-31 by M. Eric Carr

I know what kilo means. I know what farad means. But even so, I never thought I’d have a use for the word kilofarad — let alone have one on my desk.

One kilofarad (two 500F caps in parallel). Hard to believe, but there it is.

The farad, named after Michael Faraday, is the SI unit of capacitance. It is equal to one coulomb of charge per volt. One coulomb is equivalent to one amp-second: one amp of current flowing for one second transfers one coulomb of charge.

This suggests an experiment: Charge a parallel pair of 500F capacitors (a kilofarad compound capacitor) at a constant 1A, as measured by a trusted DVM. Put another meter in DC voltage mode across the capacitor, and log the rate of change of voltage. (One kilofarad should be one millivolt per coulomb of charge, so we can use voltage as a “gas gauge” for how much charge is stored.)

For a textbook 1kF capacitor charged at a constant 1.0 amps, voltage should rise at 1mV per second, or 3.6V per hour. Since the power supply will have to provide some overvoltage in order to make up for any system losses and keep 1A flowing, this experiment has to be carefully monitored to avoid overcharging the capacitors.

It’s not that they’re particularly expensive. It’s that a 1kF capacitor, charged to 2.7V, stores some 3.6kJ of energy. That’s enough to lift even my 100kg posterior some 3.33m, or almost 11 feet, straight up. To imagine what a failed cap would be like, imagine sitting on an ejection chair powered by an explosive charge powerful enough to launch a large adult ten feet in the air. That’s how much energy is in there — at only 2.7V!
(“Danger: Low Voltage”…??)

Charging at a constant 1A (kept generally within 1mA) resulted in the following voltage/charge curve. (Upon reaching 2.75V, the power supply was disconnected and the capacitors allowed to self-discharge. Effective capacitance was not measured past that point.) Interestingly, voltage rose more slowly with increasing charge. The orange curve on the chart shows effective capacitance to each point. When charged to at least 1.1V or so, the two 500F capacitors do seem to make a one-kilofarad pair.

…At least, if there has been no significant loss of charge. Measuring that will need either a controlled-current load, or simultaneous monitoring of both voltage and current, since any simple resistive load will likely experience significant changes in resistance as it heats up.

Voltage (blue, volts) and effective capacitance (orange, kilofarads)
Posted in Analog, Components, Electronics, Fundamentals, Mad Science, Reviews, Science, Toys | Tagged , , , , , , , , , , , , , | Leave a comment