Chasing the Dragon Curve
Not dogma, just what I'm learning and thinking about right now.
Comments and feedback are welcome on Mastodon.
"If you're thinking without writing, then you just think you're thinking."
—Leslie Lamport
In a previous article, The Dragon Curve, I introduced the Dragon Curve fractal. I discussed how the Dragon Curve was discovered by repeatedly folding a piece of paper in half in the same direction, and then observing the resulting folds along the edge of the paper. Here is a GIF from the Wikipedia article on Dragon Curves that wonderfully illustrates the idea.
However, if we want to make really big curves, with hundreds of folds, we need to find a way to calculate the turns without resorting to the physical world. We need an algorithm.
The Iterative Approach
In my previous article, I described how we could visualize the folds in the paper. If we write down the turns as “R” and “L,” respectively, the first four folds would result in the following sequences of turns:
1: R
2: RRL
3: RRLRRLL
4: RRLRRLLRRRLLRLL
Looking at the Dragon Curve this way, we can deduce that each iteration is formed by starting with the previous iteration, adding an “R,” and then appending the “mirror image” of the previous iteration. Here, “mirror image” means: in reverse order, with each turn inverted (from “R” to “L,” and vice versa). Using this simple algorithm, we can indeed calculate the Dragon Curve to any desired length.
This is the approach that I initially explored as a teenager on an Apple ][e. Unfortunately, this approach has a number of drawbacks, including inefficiency. Let’s explore solutions that would allow us to calculate any given turn on the Dragon Curve without calculating or iterating over the whole curve each time.
A Calculated Approach
To clarify, we want to derive an algorithm that will take any positive integer as an argument, representing an arbitrary point on the Dragon Curve, and return a symbol representing the direction the curve should turn at that point. This could be an “R” or “L,” but it could just as easily be a “0” or “1,” or “1” or “-1.”
Let’s start by revisiting the list of the first four iterations of curve given above. This depiction is actually misleading, I think, because it conveys the illusion that the curve grows by continually adding turns to the end of the previous iteration. In truth, if the curve is actually created by folding, then the original fold should always remain in the middle of the sequence. More like this.
1: R
2: R R L
3: R R L R R L L
4: RRLRRLLRRRLLRLL
Viewing it this way, you could say that each iteration of the curve consists of an “R,” with the previous iteration inserted before it, and the “mirror image” of the previous iteration added to the end. This is a slightly different conceptualization that will be useful shortly–hold the thought, we’ll come back to it.
My Second Approach
As I described in my previous article, I didn’t make much headway until I analyzed the even and odd turns separately, as I showed in this diagram.
1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
R L R L R L R L
R R L R R L L
This diagram shows the odd-numbered turns on one line, and the even-numbered turns on the line below. My eureka moment came when I realized, first, that the odd numbered turns simply alternated right and left and, second, that the even numbered turns consisted of the previous iteration of the curve. In my mind, this meant that each iteration of the curve contained a copy of the previous iterarion.
Another way to look at this is that each iteration of the curve may be formed by taking the previous sequence, and interleaving alternating Rs and Ls between each of its elements, like so:
1: R
Interleave R L
2: R R L
Interleave: R L R L
3: R R L R R L L
Interleave: R L R L R L R L
4: RRLRRLLRRRLLRLL
This approach seems to fit nicely with the observation we made above that the initial turn becomes the middle turn in successive iterations of the curve.
Turning Insight into Algorithm
So, how do we derive an algorithm from all of this? It appears that we have to approach the odd and even turns separately. Let’s look at the odds first.
Before we begin, I propose that from this point forward we use “1” and “0” to represent right and left turns (it doesn’t matter which one is which, really). This will make it easier to explore mathematical solutions to this problem.
Now, as we can see in the first diagram of the previous section, the odd-numbered turns alternate between right and left ad infinitum. With that insight, it is rather simple to create a function that takes positive, odd integers and returns two alternating, repeating values. In this case, we can just find the remainder when the turn argument is divided by four (using the modulo operator).
# Ruby (for odd turns)
def dragon_curve(turn)
turn % 4
end
// Javascript (for odd turns)
function dragonCurve(turn) {
return turn % 4;
}
These functions both return alternating values of 1 and 3. Since we want zeroes and ones, there are any number of ways to convert these values. We can stick with simple math.
# Ruby (for odd turns)
def dragon_curve(turn)
(turn % 4) % 3
end
// Javascript (for odd turns)
function dragonCurve(turn) {
return (turn % 4) % 3;
}
This gives us a never-ending stream of alternating ones and zeroes for all positive, odd integers.
Turning now to the even numbers, we showed that the even-numbered turns of a given iteration represent the same sequence as the previous iteration. Another way to say this is that turn two of the current iteration is the same as turn one of the previous iteration, and turn four is the same as the previous turn two, etc. Therefore, the algorithm for determining the value of an even numbered turn is to divide the turn argument by two, and find the value of that turn. If the argument is still even, then we divide it by two again. This process will continue until it results in an odd argument that can be evaluated using the odd-turn algorithm above.
# Ruby
def dragon_curve(turn)
if turn.even?
dragon_curve(turn / 2)
else
(turn % 4) % 3
end
end
// Javascript
function dragonCurve(turn) {
if (turn % 2 == 0) {
return dragonCurve(turn / 2);
} else {
return (turn % 4) % 3;
}
}
The above algorithm takes a recursive approach for simplicity, but the same result could be accomplished without recursion. The real question is, are we satisfied with this solution? I wasn’t. Lets see what else we can do.
Binary to the Rescue
One of the many approaches I tried while investigating the Dragon Curve was to look at the binary representation of the turn numbers to see if they could help me. In other words, I wanted to know, could I derive the correct value in the sequence by looking only at the binary representation of the turn number? The answer to this question was quite surprising, at least to me!
As before, lets begin by looking at the odd-numbered turns. Here are the binary representations of the odd numbers one through nine (I will use four binary digits throughout for clarity):
1: 0001
3: 0011
5: 0101
7: 0111
9: 1001
We can note a few things from the start: first, all binary odd numbers end with a one; second, the second-to-last digit appears to alternate values, just as we require! Could this be that simple? Let’s check using our previous algorithm.
In binary math, the equivalent of performing % 4 is to simply truncate the binary number to its last two digits:
1 % 4: 01
3 % 4: 11
5 % 4: 01
7 % 4: 11
9 % 4: 01
If we then apply % 3 to the resulting values, we will get the inverse of the first digits (that is, the left-most digits) from the diagram above:
(1 % 4) % 3: 1
(3 % 4) % 3: 0
(5 % 4) % 3: 1
(7 % 4) % 3: 0
(9 % 4) % 3: 1
This confirms that we can use the second-to-last digit of the binary representation of an odd turn number to determine the value of the Dragon Curve at that turn. Moreover, since the choice of 0 or 1 to represent right and left turns is entirely arbitrary, I will simply use the second to last digit as-is (that is, I will not apply the % 3 step, as it is unnecessary). In fact, I liked this result so much that I named the second-to-last binary digit the “penultabit.” (Yes, I just made that up–please use with attribution! :-D)
Lets look now at the even-numbered turns. Contrary to binary odd numbers, the binary representation of even numbers will always end in zero.
2: 0010
4: 0100
6: 0110
8: 1000
10: 1010
Now, following our previous algorithm, we want to reduce these numbers in half repeatedly until we reach an odd result. Doing this with binary numbers is trivial: to divide a binary number in half, you simply “shift” its bits one place to the right. Another way of saying this is that we drop the right-most digit. Again, since all of our arguments are even (that is, they all end in a zero), we can just say that we want to “trim” the trailing zero from the binary number.
In our previous algorithm we used recursion to reduce the turn argument by halves until we reached an odd result. The equivalent process here is simply to trim all trailing zeroes from the binary number, giving us an odd value that we already know how to translate.
2 (reduces to 1): 0010 -> 001
4 (reduces to 1): 0100 -> 01
6 (reduces to 3): 0110 -> 011
8 (reduces to 1): 1000 -> 1
10 (reduces to 5): 1010 -> 101
Now, using the odd-number algorithm, we can simply take the penultabit of each result as our final value! Note that for some values, we will need to infer the presence of a leading zero on the left. The need for this can be seen in the case of the value 8 above, which would reduce to “1”. In order to have a “penultabit,” we will need to pad the binary representation with a leading zero.
Why is this so interesting? This means that all we have to do for any given turn on the curve is convert the turn argument to binary, apply a simple transformation, and extract the correct result (the penultabit!). Moreover, we can merge the odd- and even-number algorithms into one simple approach! The steps will look like this:
- Convert the turn argument to binary.
- Trim any trailing zeroes (no effect on odd numbers!).
- Return the penultabit of the result (padding with a zero on the left, as needed).
Could it really be that simple? Let’s look one more time and compare to the result from our original approach above.
Trim/Pad Penulta- Check
Zeroes bit Value
1: 0001 -> 0001 -> 0 -> R
2: 0010 -> 001 -> 0 -> R
3: 0011 -> 0011 -> 1 -> L
4: 0100 -> 01 -> 0 -> R
5: 0101 -> 0101 -> 0 -> R
6: 0110 -> 011 -> 1 -> L
7: 0111 -> 0111 -> 1 -> L
8: 1000 -> 01 -> 0 -> R
9: 1001 -> 1001 -> 0 -> R
10: 1010 -> 101 -> 0 -> R
11: 1011 -> 1011 -> 1 -> L
12: 1100 -> 11 -> 1 -> L
13: 1101 -> 1101 -> 0 -> R
14: 1110 -> 111 -> 1 -> L
15: 1111 -> 1111 -> 1 -> L
It worked! That’s cool! What will this look like in code? Let’s see!
# Ruby
def dragon_curve(turn)
("0" << turn.to_s(2)).gsub(/0+$/,"")[-2]
end
This is a bit cryptic, so let’s break it down. First, we start with the string “0.” This has the effect of padding all of the binary representations with a left zero (remember, if the argument reduces to only one binary digit, then we have no penultabit!). Then, we append the binary representation of the turn argument (it is now a string). Next, we use String#gsub to match and delete trailing zeroes from the string. Finally, we return the penultabit (index -2).
Let’s see this in JavaScript. The function names are different, but this is essentially the same as the Ruby code.
function dragonCurve(turn) {
return ("0" + turn.toString(2)).replace(/0+$/,"").slice(-2, -1);
}
Now, can we improve this? Maybe. Your homework, should you choose to accept it, is to design a regular expression matcher that will extract the penultabit without trimming the trailing zeroes. What do you think? As for me, I think I’m all set with what we have here.
I don’t know about you, but I had a lot of fun with this!