John D. Cook

A crinkle crankle wall, also called a serpentine wall, is a wavy wall that may seem to sacrifice some efficiency for aesthetics. The curves add visual interest, but they use more material than a straight way. Except they don’t! They use more bricks than a straight wall of the same thickness but they don’t have […]

An m by n rook graph is formed by associating a node with each square of an m by n chess board and connecting two nodes with an edge if a rook can legally move from one to the other. That is, two nodes are connected if they are either in the same row or […]

The P vs NP conjecture has always seemed a little odd to me. Or rather the interpretation of the conjecture that any problem in P is tractable. How reassuring is to to know a problem can be solved in time less than some polynomial function of the size of the input if that polynomial has […]

Programming languages differ in the names they use for inverse trig functions, and in some cases differ in their return values for the same inputs. Choice of range If sin(θ) = x, then θ is the inverse sine of x, right? Maybe. Depends on how you define the inverse sine. If -1 ≤ x ≤ […]

I recently had to work with the function f(x; k) = arctan( k tan(x) ) The semicolon between x and k is meant to imply that we’re thinking of x as the argument and k as a parameter. This function is an example of the coming full circle theme I’ve written about several times. Here’s […]

Phys.com published an article a couple days ago NASA finds Neptune moons locked in ‘dance of avoidance’. The article is based on the scholarly paper Orbits and resonances of the regular moons of Neptune. The two moons closest to Neptune, named Naiad and Thalassa, orbit at nearly the same distance, 48,224 km for Naiad and […]

Suppose you want to compute the natural logarithms of every floating point number, correctly truncated to a floating point result. Here by floating point number we mean an IEEE standard 64-bit float, what C calls a double. Which logarithm is hardest to compute? We’ll get to the hardest logarithm shortly, but we’ll first start with […]

The Sketchviz site lets you enter GraphViz code and get out something that looks hand-drawn. I decided to try it on some of the GraphViz diagrams I’ve made for this blog. Here’s a diagram from my post on Rock, Paper, Scissors, Lizard, Spock. The Sketchviz site defaults to Tinos font, which does not look hand-drawn. […]

If you have two sequences, and one is a permutation of the other, how do you measure how far apart the two sequences are? This post was motivated by the previous post on anagram statistics. For a certain dictionary, the code used in that post found that the longest anagram pairs were the following: certifications, […]

An anagram of a word is another word formed by rearranging its letters. For example, “restful” and “fluster” are anagrams. How common are anagrams? What is the largest set of words that are anagrams of each other? What are the longest words which have anagrams? You’ll get different answers to these questions depending on what […]

Many of you have been following my blog for years. Thank you for your time and your feedback. But there are always newcomers, and so periodically I like to write a sort of orientation post. You can subscribe to this blog by RSS or email. I also have a monthly newsletter where I highlight the […]

The previous post looked at an example of strange floating point behavior taking from book End of Error. This post looks at another example. This example, by Siegfried Rump, asks us to evaluate 333.75 y6 + x2 (11 x2 y2 – y6 – 121 y4 – 2) + 5.5 y8 + x/(2y) at x = […]

Here is an example fiendishly designed to point out what could go wrong with floating point arithmetic, even with high precision. I found the following example by Jean-Michel Muller in John Gustafson’s book End of Error. The task is to evaluate the following function at 15, 16, 17, and 9999. Here e(0) is defined by […]

A killer app is an program so useful that people will buy a larger system just to use it. For example, the VisiCalc spreadsheet was a killer app for the Apple II, maybe the first program to be called a “killer app.” People would buy an Apple II just so they could run VisiCalc. Microsoft […]

Robert Bosch has a new book coming out next week titled OPT ART: From Mathematical Optimization to Visual Design. This post will look at just one example from the book: creating images of Frankenstein’s monster [1] using dominoes. The book includes two images, a low-resolution image made from 3 sets of dominoes and a high […]

A couple weeks ago I wrote about how De Bruijn sequences can be used to attack locks where there is no “enter” key, i.e. the lock will open once the right symbols have been entered. Here’s a variation on this theme: what about locks that let you press more than one button at a time? […]

Adding up an array of numbers is simple: just loop over the array, adding each element to an accumulator. Usually that’s good enough, but sometimes you need more precision, either because your application need a high-precision answer, or because your problem is poorly conditioned and you need a moderate-precision answer [1]. There are many algorithms […]

Any positive number can be found at the beginning of a factorial. That is, for every positive positive integer n, there is an integer m such that the leading digits of m! are the digits of n. There’s a tradition in math to use the current year when you need an arbitrary numbers; you’ll see […]

Having access to arbitrary precision arithmetic does not necessarily make numerical calculation difficulties go away. You still need to know what you’re doing. Before you extend precision, you have to know how far to extend it. If you don’t extend it enough, your answers won’t be accurate enough. If you extend it too far, you […]

Thirty years ago, a lot of US states thought it would be a good idea to compute someone’s drivers license number (DLN) from their personal information [1]. In 1991, fifteen states simply used your Social Security Number as your DLN. Eleven other states computed DLNs by applying a hash function to personal information such as […]

Yesterday I wrote about Householder’s higher-order generalizations of Newton’s root finding method. For n at least 2, define and iterate Hn to find a root of f(x). When n = 2, this is Newton’s method. In yesterday’s post I used Mathematica to find expressions for H3 and H4, then used Mathematica’s FortranForm[] function to export […]

Are there infinitely many positive integers n such that tan(n) > n? David P. Bellamy and Felix Lazebnik [1] asked in 1998 whether there were infinitely many solutions to |tan(n)| > n and tan(n) > n/4. In both cases the answer is yes. But at least as recently as 2014 the problem at the top […]

There are variations on Newton’s root finding method that use higher derivatives and converge faster. Alston Householder developed a sequence of such methods of the form where the superscripts in parentheses indicate derivatives. When n = 2, Householder’s method reduces to Newton’s method. Once Newton’s method is close enough to a root, the error is […]

The utility numfmt, part of Gnu Coreutils, formats numbers. The main uses are grouping digits and converting to and from unit suffixes like k for kilo and M for mega. This is somewhat useful for individual invocations, but like most command line utilities, the real value is using it as part of pipeline. The --grouping […]

I wanted to stress test the bc calculator a little and so I calculated π to 10,000 digits a couple different ways. First I ran time bc -l <<< "scale=10000;4*a(1)" which calculates π as 4 arctan(1). This took 2 minutes and 38 seconds. I imagine bc is using some sort of power series to compute […]

The previous post looked at an algorithm for generating De Bruijn sequences B(k, n) where k is a prime number. These are optimal sequences that contain every possible consecutive sequence of n symbols from an alphabet of size k. As noted near the end of the post, the case k = 2 is especially important […]

Last week I wrote about a way to use De Bruijn cycles. Today I’ll write about a way to generate De Bruijn cycles. De Bruijn cycles Start with an alphabet of k symbols. B(k, n) is the set of cycles of that contain every sequence of n symbols, and is as short as possible. Since […]

Google announced today that it has demonstrated “quantum supremacy,” i.e. that they have solved a problem on a quantum computer that could not be solved on a classical computer. Google says Our machine performed the target computation in 200 seconds, and from measurements in our experiment we determined that it would take the world’s fastest […]

As I mentioned in my computational survivalist post, I’m working on a project where I have a dedicated computer with little more than basic Unix tools, ported to Windows. It’s given me new appreciation for how the standard Unix tools fit together; I’ve had to rely on them for tasks I’d usually do a different […]

If you look at a sine wave, its curvature is sorta like its values. When sine is zero, the curve is essentially a straight line, and the curvature is zero. When sine is at its maximum, the function bends the most and so the curvature is at a maximum. This makes sense analytically. The second […]

Suppose you have a keypad that will unlock a door as soon as it sees a specified sequence of four digits. There’s no “enter” key to mark the end of a four-digit sequence, so the four digits could come at any time, though they have to be sequential. So, for example, if the pass code […]

My previous post contained the image below. The point of the post was that the numbers that came up in yet another post made the fractal image above when you wrote them in binary. Here’s the trick I used to make that image. To make the pattern of 0’s and 1’s easier to see, I […]

As mentioned in the previous post, the Gauss-Wantzel theorem says you can construct a regular n-gon with a straight edge and compass if and only if n has the form 2k F where k is a non-negative integer and F is a product of distinct Fermat primes. Let’s look at the binary representation of these […]

If you know the sine of any angle, you can find its cosine from the Pythagorean theorem. And if you know the sine of an angle you can find the sine of any multiple of that angle using the identity for the sine of a sum. You can find that sin 30° = 1/2 from […]

Suppose you want to sent pictures from Jupiter back to Earth. A lot could happen as a bit travels across the solar system, and so you need some way of correcting errors, or at least detecting errors. The simplest thing to do would be to transmit photos twice. If a bit is received the same […]

Yesterday I wrote a post looking at the frequency of Koine Greek letters and the corresponding entropy. David Littleboy asked what an analogous calculation would look like for a language like Japanese. This post answers that question. First of all, information theory defines the Shannon entropy of an “alphabet” to be bits where pi is […]

Kenneth G. Libbrecht has posted a 523-page book on snow to arXiv.

Would the letters in an ancient Greek text carry more or less information than in modern English? To address this question, I downloaded a copy of the Greek New Testament from Project Gutenberg and ran the word frequency script from my previous post. This lead to the follow table of letters and percent frequency. α […]

Once in a while I need to know what characters are in a file and how often each appears. One reason I might do this is to look for statistical anomalies. Another reason might be to see whether a file has any characters it’s not supposed to have, which is often the case. A few […]

A few days ago I wrote about computational survivalists, people who prepare to be able to work on computers with only software that is available everywhere. Of course nothing is available everywhere, and so each person interprets “everywhere” to mean computers they anticipate using. If you need to edit a text file on a Windows […]

The idea behind differential privacy is that it doesn’t make much difference whether your data is in a data set or not. How much difference your participation makes is made precise in terms of probability statements. The exact definition doesn’t for this post, but it matters that there is an exact definition. Someone designing a […]

Queueing theory is the study of waiting in line. That may not sound very interesting, but the subject is full of surprises. For example, when a server is near capacity, adding a second server can cut backlog not just in half but by an order of magnitude or more. More on that here. In this […]

There are a couple different ways to combine random variables into a new random variable: means and mixtures. To take the mean of X and Y you average their values. To take the mixture of X and Y you average their densities. The former makes the tails thinner. The latter makes the tails thicker. When […]

Primes usually look odd. They’re literally odd [1], but they typically don’t look like they have a pattern, because a pattern would often imply a way to factor the number. However, 12345678910987654321 is prime! I posted this on Twitter, and someone with the handle lagomoof replied that the analogous numbers are true for bases 2, […]

Some programmers and systems engineers try to do everything they can with basic command line tools on the grounds that someday they may be in an environment where that’s all they have. I think of this as a sort of computational survivalism. I’m not much of a computational survivalist, but I’ve come to appreciate such […]

How many days are in a year? 365. How many times does the earth rotate on its axis in a year? 366. If you think a day is the time it takes for earth to rotate once around its axis, you’re approximately right, but off by about four minutes. What we typically mean by “day” […]

In the previous post, I said that Lissajous curves are the result of plotting a curve whose x and y coordinates come from (undamped) harmonic oscillators. If we add a little bit of dampening, multiplying our cosine terms by negative exponentials, the resulting curve is called a harmonograph. Here’s a bit of Mathematica code to […]

Suppose that over time the x and y coordinates of a point are both given by a harmonic oscillator, i.e. x(t) = cos(nx t + φx) y(t) = cos(ny t + φy) Then the resulting path is called a Lissajous curve. If you add a z coordinate also given by harmonic oscillator z(t) = cos(nz […]

For an ellipsoid with equation the Gaussian curvature at each point is given by Now suppose a ≥ b ≥ c > 0. Otherwise relabel the coordinate axes so that this is the case. Then the largest curvature occurs at (±a, 0, 0), and the smallest curvature occurs at (0, 0, ±c). You could prove […]

Take a calculator and enter any number. Then press the cosine key over and over. Eventually the numbers will stop changing. You will either see 0.99984774 or 0.73908513, depending on whether your calculator was in degree mode or radian mode. This is an example of a fixed point, a point that doesn’t change when you […]