Tool recursion

Posted on by John

“Literature about Lisp rarely resists that narcissistic pleasure of describing Lisp in Lisp.” — Christian Queinnec, Lisp in Small Pieces

 

Applying software development tools to themselves has a dark side and a light side.

There’s a danger of becoming obsessed with one’s tools and never getting around to using them. If it’s your job to cut down a tree, there’s some benefit to sharpening your ax, but you can’t only sharpen your ax. At some point you hit diminishing return and it’s time to start chopping.

But there are benefits to self-referential systems, such as macros that use Lisp to generate Lisp, or writing a C compiler in C, or using Emacs to tweak Emacs. There’s a kind of consistency that results, and there can be a compound return on effort. But as with writing a recursive procedure, there has to be a base case, a point at which you stop recursing. Otherwise you go down the black hole of becoming absorbed in your tool and never using it for work.

Even though I’ve used Emacs for a long time, I’ve never understood the recursive fascination some people have with it. For example, part of the elevator pitch for Emacs is that it’s self-documenting. You can pull up help on Emacs from inside Emacs. But you can also type your questions into a search engine without having to learn an arcane help API. What’s the advantage to the former?

For one thing, using Emacs help inside Emacs works without a network connection. For another, you avoid the risk of being distracted by something you see when you’re using your web browser. But the most subtle benefit is the compound effect of self-reference. You can use the same navigation commands in the help system that you can when editing text, you can execute code snippets in place, etc.

When I hear “Isn’t it cool that you can do X in X?” my first thought is “Yeah, that sounds cool” but my second thought is “But why would you want to do that? Sounds like it could be really hard.” I’m starting to appreciate that there are sometimes long-term benefits to these sort of recursive tool uses even if they’re not optimal in the short run.

New Twitter account: ElementFact

Posted on by John

I started a new Twitter account this morning: @ElementFact. I’m thinking the account will post things like scientific facts about each element but also some history around how the element was discovered and named and other lore associated with the element.

@ElementFact icon

We’ll see how this goes. I’ve started many Twitter accounts over the years. Some have taken off and some have not.

Six months ago I started @TensorFact as an experiment to see what would happen with a narrowly focused account. It did moderately well, but I ran out of ideas for content. This will be the last week for that account.

You can see a list of my current Twitter accounts here.

Approximating a golden spiral with circular arcs

Posted on by John

The previous post included this image of a logarithm spiral passing through the corners of squares in a sequence of golden rectangles.

The portion of the spiral in each square looks like a quarter of a circle. How well would circular arcs approximate the spiral?

Very well. Here’s a plot.

The circular arc inside the blue square is plotted in blue, the arc inside the green box in green, etc. The logarithmic spiral is plotted on top with a dashed black line. You have to zoom in closely to see any difference between the logarithmic spiral and its circular approximations.

For aesthetic applications, circular arcs are good enough and probably easier to work with. For a sort of three-dimensional analog of this approximation, see this post on the geometry of the Sydney Opera House.

Sometimes discontinuities in first or second derivatives are visually noticeable, but here they’re not. The approximation of the logarithmic spiral by a sequence of quarter circles has a jumps in curvature, which is roughly a second derivative. I suppose it’s more noticeable when curvature jumps from positive to zero or from positive to negative. Here it’s jumping from one positive value (the reciprocal of the circle radius) to another positive value (the reciprocal of a smaller radius).

Related posts

Logarithmic spiral

Posted on by John

I’ve seen an image similar to the following many times, but I don’t recall any source going into detail regarding how the spiral is constructed. This post will do just that.

The previous post constructed iterated golden rectangles. We start with a golden rectangle and imagine chopping of first the blue, then the green, then the orange, and then the red square. We could continue this process on the inner most rectangle, over and over.

At this point, many sources would say “Hey look! We can draw a spiral that goes through two corners of each square” without explicitly stating an equation for the spiral. We’ll find spiral, making everything explicit.

In the previous post we showed how to find the limit of the iterative process at the intersection of the two diagonal lines below.

We showed that the intersection is at

x0 = (2φ + 1)/(φ + 2)

and

y0 = 1/(φ + 2).

Logarithmic spirals

A logarithmic spiral centered at the origin has the polar equation

r(θ) = a exp(kθ)

for some constants a and k. Our spiral will be such a spiral shifted to center at (x0, y0).

Imagine a spiral going from the lower left to the top left of the blue square, then to the top left of the green square, then to the top right of the orange square etc., passing through two corners of every square. Every time θ goes through a quarter turn, i.e. π/2 radians, our rectangles get smaller by a factor of φ. We can use this to solve for k because

a exp(k(θ + π/2)) = φ a exp(kθ)

and so

exp(kπ/2) = φ

and

k = 2log(φ) / π.

To summarize what we know so far, if we shift our spiral to the origin, it has equation in polar form

r(θ) = a exp(kθ)

where we now know k but don’t yet know a.

Finding θ and a

To get our actual spiral, we have to shift the origin to (x0, y0) which we have calculated above. Converting from polar to rectangular coordinates so we can do the shift, we have

x(θ) = x0 + a exp(kθ) cos(θ)

y(θ) = y0 + a exp(kθ) sin(θ)

We can find the parameter a by knowing that our spiral passes through the origin, the bottom left corner in the plots above. At what value of θ does the curve go through the origin? We have a choice; values of θ that differ by multiples of 2π will give different values of a.

The angle θ is the angle made by the line connecting (0, 0) to (x0, y0). We can find θ via

θ0 = atan2(-y0, –x0).

Here’s Python code to find θ0:

    import numpy as np

    phi = (1 + 5**0.5)/2
    y0 = 1/(2+phi)
    x0 = (2*phi + 1)*y0
    theta0 = np.arctan2(-y0, -x0)

Then we solve for a from the equation x(θ0) = 0.

    k = 2*np.log(phi)/np.pi
    a = -x0 / (np.exp(k*theta0)*np.cos(theta0)))

Plots

Now we have all the parameters we need to define our logarithmic spiral. The following code draws our logarithmic spiral on top of the plot of the rectangles.

    t = np.linspace(-20, theta0, 1000)
    def x(t): return x0 + a*np.exp(k*t)*np.cos(t)
    def y(t): return y0 + a*np.exp(k*t)*np.sin(t)
    plt.plot(x(t), y(t), "k-")

The result is the image at the top of the post.

Iterated golden rectangles in detail

Posted on by John

I’ve seen the illustration of nesting golden rectangles many times, but I’ve never seen a presentation go into much detail. This post will go into more detail than usual, including Python code.

Start with a golden rectangle in landscape mode. We’ll plot our rectangle with the lower left corner at the origin and the upper right corner at (φ, 1) where φ is the golden ratio. No imaging cutting off the largest square you can on the left side, shown in blue.

Next, focus on the remaining rectangle and imagine cutting off the square on top, shown in green.

Now focus on the remaining rectangle and imagine cutting off the square on the right, shown in orange.

Finally, focus on the remaining rectangle and imagine cutting off the square on bottom, shown in red.

So we’ve cut off left, top, right, and bottom. We’re left with a rectangle with one side of each color above. We could repeat the process above on this rectangle, cutting off left, top, right, and bottom, and so on ad infinitum.

Where does this process end in the limit? Draw two diagonal lines as shown below.

Note that these diagonals cut the innermost rectangle in the same way as the outermost rectangle. So every time we repeat the four steps above, we will always have two diagonals that intersect in the same place. So the limit of the process converges on the point that is the intersection of the two diagonal lines.

The two diagonals lines have equations

y = -(1/φ)x + 1

and

y = φx – φ

and so we can calculate their intersection to be at

x0 = (2φ + 1)/(φ + 2)

and

y0 = 1/(φ + 2).

So the construction process, in the limit, converges to the point (x0, y0) where the diagonals cross.

Here’s Python code to product the final plot above.

    import numpy as np
    import matplotlib.pyplot as plt
    
    phi = (1 + 5**0.5)/2
    
    def plotrect(lowerleft, upperright, color):
        x0, y0 = lowerleft
        x1, y1 = upperright
        plt.plot([x0, x1], [y0, y0], c=color)
        plt.plot([x0, x1], [y1, y1], c=color)
        plt.plot([x0, x0], [y0, y1], c=color)
        plt.plot([x1, x1], [y0, y1], c=color)
    
    plt.gca().set_aspect("equal")   
 
    plotrect((0, 0), (phi, 1), "black")
    plotrect((0, 0), (1, 1), "blue")
    plotrect((1, 2-phi), (phi, 1), "green")
    plotrect((2*phi - 2,0), (phi, 2-phi), "orange")
    plotrect((1,0), (2*phi-2,2*phi-3), "red")
    plt.plot([0, phi], [1, 0], "--", color="gray")
    plt.plot([1, phi], [0, 1], "--", color="gray")
    plt.savefig("golden_rect5.png")

I intend to find the equation of the spiral that touches two corners of each square in the next post.

Mentally calculating the day of the week

Posted on by John

In my previous post I mentioned John Conway’s Doomsday rule for calculating the day of the week for any date. This method starts off very simple, but gets more complicated when you actually use it.

This post will present an alternative method that’s easier to use in practice and can be described more succinctly.

Here’s the algorithm.

  1. Take the last two digits of the year and add the number of times 4 divides that number.
  2. Add a constant corresponding to the month.
  3. Add the day of the month.
  4. Subtract 1 for January or February of a leap year for .
  5. Take the remainder by 7.

The result is a number that tell you the day of the week.

To be even more succinct, let y be the number formed by the last two digits of the date. Let d be the day of the month. Let L equal 1 if the year is a leap year and the date is in January or February and 0 otherwise. Then the algorithm above can be written as

(y + ⌊y/4⌋ + d – L + month constant) % 7.

Here ⌊x⌋ is the floor of x, the greatest integer no greater than x, and x % 7 is the remainder when x is divided by 7.

Update: There are multiple ways to compute the year share, i.e. y + ⌊y/4⌋, that are equivalent mod 7 and easier to carry out mentally than the direct approach.

I’ve deliberately left out a couple details above. What are these month constants, and how does the number at the end give you a day of the week?

Customizing for the 21st century

I learned the method above in the 20th century, and the rule was optimized for the 20th century. You had to subtract 1 for dates in the 21st century.

Also, when I learned the method, it numbered the days of the week with Sunday = 1, Monday = 2, etc. Now I would find it easier to start with Sunday = 0.

Here’s an updated table of month constants that eliminates the need to adjust for dates in the 20th century, and numbers the days of the week from 0.

    | January | 6 | February | 2 | March     | 2 |
    | April   | 5 | May      | 0 | June      | 3 |
    | July    | 5 | August   | 1 | September | 4 |
    | October | 6 | November | 2 | December  | 4 |

If you’d like to number Sunday as 1 rather than 0, add 1 to all the numbers above.

The article I learned this method from came with suggested mnemonics for remembering the month constants. But when you change the constants like I’ve done here, you have to come up with new mnemonics.

Examples

I’m writing this post on Saturday, May 7, 2022. Let’s verify that the method gives the correct day of the week today.

Start with 22, and add 5 because ⌊22/4⌋ = 5. The number for May is 0, so there’s nothing to add for the month. We add 7 because today’s the 7th. This gives us

22 + 5 + 7 = 34

which gives a remainder of 6 mod 7, so this is day 6. Since we started with 0 for Sunday, 6 is Saturday.

Next, let’s do January 15, 2036. We get

36 + 9 + 6 + 15 – 1 = 65

which is 2 mod 7. so January 15 will fall on a Tuesday in 2036. Note that we subtracted 1 because 2036 will be a leap year and our date is in January.

If we want to look at Christmas 2036, we have

36 + 9 + 4 + 25 = 74

which is 4 mod 7, so December 25 will fall on a Thursday in 2036. We didn’t subtract 1 because although 2036 is a leap year, we’re looking at a date after February.

Other centuries

For dates in the 20th century, add 1.

For dates in the 22nd century, subtract 1.

If by some reason you’re reading this article in the 22nd century, make your own table of month constants by subtracting 1 from the numbers in the table above.

More details

When I was at University of Texas, humanities majors had to take a class we called “math for poets.” The class was a hodgepodge of various topics, and the most popular topic when I taught the class was this method. Here’s a handout I gave the class.

That handout is a little slower paced than this blog post, and goes into some explanation for why the method works. (The method was meant to motivate modular arithmetic, one of the topics on the syllabus, so explaining why the method works was secretly the whole point of teaching it.)

The handout is still valid. You can follow it verbatim, or you can replace the table of month constants with the one above and ignore the 21st century correction step.

Related posts

John Conway and mental exercise rituals

Posted on by John

Drawing of John Conway with horned sphere

John Horton Conway (1937–2020) came up with an algorithm in 1973 for mentally calculating what day of the week a date falls on. His method, which he called the “Doomsday rule” starts from the observation that every year, the dates 4/4. 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, and 11/7 fall on the same day of the week [1], what Conway called the “doomsday” of that year. That’s Monday this year.

Once you know the doomsday for a year you can bootstrap your way to finding the day of the week for any date that year. Finding the doomsday is a little complicated.

Conway had his computer set up so that it would quiz him with random dates every time he logged in.

Mental exercises

Recently I’ve been thinking about mental exercise rituals, similar to Conway having his computer quiz him on dates. Some people play video games or solve Rubik’s cubes or recite poetry.

Curiously, what some people do for a mental warm-up others do for a mental cool-down, such as mentally reviewing something they’ve memorized as a way to fall asleep.

What are some mental exercise rituals that you’ve done or heard of other people doing? Please leave examples in the comments.

More on Conway

The drawing at the top of the page is a sketch of Conway by Simon Frazer. The strange thing coming out of Conway’s head in the sketch is Alexander’s horned sphere, a famous example from topology. Despite appearances, the boundary of Alexander’s horned sphere is topologically equivalent to a sphere.

Conway was a free-range mathematician, working in a wide variety of areas, ranging from the classification of finite simple groups to his popular Game of Life. Of the 26 sporadic groups, three are named after Conway.

Here are some more posts where I’ve written about John Conway or cited something he wrote.

[1] Because this list of dates is symmetric in month and day, the rule works on both sides of the Atlantic.

Quartal melody: Star Trek fanfare

Posted on by John

Intervals of a fourth, such as the interval from C to F, are common in western music, but consecutive intervals of this size are not. Quartal harmony is based on intervals of fourths, and quartal melodies use a lot of fourths, particularly consecutive fourths.

Maybe the most famous quartal melody is the opening fanfare to Star Trek (original series). Here’s a transcription of the opening line:

And here is the same music with the intervals of a fourth circled.

The theme opens with two consecutive fourths, there’s an augmented fourth in the middle, then two more consecutive fourths. There are two major thirds in the phrase above, which you could call diminished fourths.

Incidentally, there are four bell tones before the melody above begins, and the interval between the first two tones is a fourth.

Making the sheet music

Here’s the Lilypond source code I used to create the images above.

    \begin{lilypond}

    \score {
        \relative e'{
        \time 4/4
        \partial 2 a4. d8 |
        \tuplet 3/2 {g4~ 4 ges4} \tuplet 3/2 {d4 b4 e4} |
        a2 ~ 4 ~ 8 8 |
        des1
    }
    \end{lilypond}

This uses a few Lilypond features I hadn’t used before.

  • The \partial command for the two pickup notes.
  • The \tuple command for the triples.
  • The shortcut of not repeating the names repeated notes.

The last point applies twice, writing g4 4 rather than g4 g4 and writing a2 4 8 8 rather than a2 a4 a8 a8.

Related posts

Why target ads at pregnant women

Posted on by John

I’m listening to a podcast interviewing Neil Richards, the author of Why Privacy Matters. Richards makes a couple interesting points about the infamous example of Target figuring out which women were pregnant based on their purchase history.

First, pregnancy is a point at which women are open to trying new things. So if a company can get a woman to buy a baby stroller at their store, they may be able to get her to remain a customer for years to come. (Richards mentioned going off to college as another such milestone, so a barrage of advertising is aimed at first-year college students.)

Second, women understandably freaked-out over the targeted ads. So Target hid the ads in with irrelevant ads. They might show a woman ads for lawnmowers and baby wipes. That way the baby wipe ads didn’t seem so on-the-nose. The target audience would see the ad without feeling like they’re being targeted.

Just to be clear, I’m not writing this post to offer how-to advice for doing creepy advertising. The info here is presumably common knowledge in the advertising industry, but it’s not common knowledge for the public.

Curiously simple approximations

Posted on by John

As I’ve written about here and elsewhere, the following simple approximations are fairly accurate.

log10 x ≈ (x-1)/(x+1)

loge x ≈ 2 (x – 1)/(x + 1)

log2 x ≈ 3(x – 1)/(x + 1)

It’s a little surprising that each is as accurate as it is, but it’s also surprising that the approximations for loge and loge are small integer multiples of the approximation for log10.

Logarithms in all bases are proportional: If b and β are two bases, then for all x,

logβ(x) = logb(x) / logb(β).

So it’s not surprising that the approximations above are proportional. But the proportionality constants are not what the equation above would predict.

There are a couple things going on. First, these approximations are intended for rough mental calculations, so round numbers are desirable. Second, we want to minimize the error over some range. The approximation for logb(x) needs to work over the interval from 1/√b to √b. The approximations don’t work outside this range, but they don’t need to since you can always reduce the problem to computing logs in this interval. These two goals work together.

We could make the log10 x approximation more accurate near 1 if we multiplied it by 0.9. That would make the approximation a little harder to use, but it wouldn’t improve the accuracy over the interval 1/√10 to √10. The constant 1 works just as well as 0.9, and it’s easier to multiply by 1.

Here’s a plot of the approximation errors. Notice that different bases are plotted over different ranges since the log for each base b needs to work from 1/√b to √b.