John D. Cook

A paper came out in 1964 with the title H = W." The remarkably short title was not cryptic, however. The people for whom the paper was written knew exactly what it meant. There were two families of function spaces, one denoted with H and another denoted withW, that were speculated to be the same, [...]The post My favorite paper: H = W first appeared on John D. Cook.

If you change the coefficients of a polynomial a little bit, do you change the location of its zeros a little bit? In other words, do the roots of a polynomial depend continuously on its coefficients? You would think so, and you'd be right. Sorta. It's easy to see that small change to a coefficient [...]The post Wilkinson's polynomial first appeared on John D. Cook.

You would think that interpolating at more points would give you a more accurate approximation. There's a famous example by Runge that proves this is not the case. If you interpolate the function 1/(1 + x^2) over the interval [-5, 5], as you add more interpolation points the maximum interpolation error actually increases. Here's an [...]The post Interpolation instability first appeared on John D. Cook.

The most well-known generalization of the inverse of a matrix is the Moore-Penrose pseudoinverse.But there is another notion of generalized inverse, the Drazin pseudoinverse, for square matrices. If a matrix A has an inverseA-1 then it also has a Moore-Penrose pseudoinverse A+ and a Drazin pseudoinverse AD and A-1 = A+ = AD. When the [...]The post Drazin pseudoinverse first appeared on John D. Cook.

I've mentioned the Moore-Penrose pseudoinverse of a matrix a few times, most recently last week. This post will give an application of the pseudoinverse: computing effective graph resistance. Given a graphG, imagine replacing each edge with a one Ohm resistor. The effective resistance between two nodes inG is the electrical resistance between those the two [...]The post Effective graph resistance first appeared on John D. Cook.

An earlier post claimed that there practical advantages to partitioning a matrix, thinking of the matrix as a matrix of matrices. This post will give an example. LetM be a square matrix and suppose we need to multiply M by its transpose MT. We can compute this product faster than multiplying two arbitrary matrices of [...]The post Multiplying a matrix by its transpose first appeared on John D. Cook.

Pop quiz: what does the following code do? bool is_leap_year_fast(uint32_t y) { return ((y * 1073750999) & 3221352463) <= 126976; } It determines whether the year y is a leap year in the Gregorian calendar, of course. :) It's very efficient, though I don't image that would ever matter. But it's very clever. Gregorian vs [...]The post A bit-twiddling marvel first appeared on John D. Cook.

It's often useful to partition a matrix, thinking of it as a matrix whose entries are matrices. For example, you could look at the matrix 6 * 6 as a 2 * 2 matrix whose entries are 3 * 3 matrices. M is not a diagonal matrix of real numbers, but its block structure is [...]The post Matrices of Matrices first appeared on John D. Cook.

IJK (@iconjack) has calculated the probability of rolling a Yahtzee in no more than n rolls. The first few numerical values are: p(1) = 0.0007716 p(2) = 0.0126316 p(3) = 0.0460286 The probability is 0.95 after 23 rolls, and 0.99 after 32 rolls. Here's a plot.The post Probability of rolling a Yahtzee first appeared on John D. Cook.

The term trinomial coefficient is used a couple different ways. The most natural use of the term is a generalization of bionomial coefficients to three variables, i.e. numbers of the form wherei +j +k =n. These numbers are the coefficients of yj zk in the expansion of (x + y + z)n. But there's another [...]The post Trinomial Coefficients and Kings first appeared on John D. Cook.

I saw an integral posted online that came from this year's MIT Integration Bee. My thoughts on seeing this were, in order: It looks like a beta function. The answer is a small number. You can evaluate the integral using the substitution u = 1 - x2025. I imagine most students' reactions would be roughly [...]The post Riff on an integration bee integral first appeared on John D. Cook.

Here's another little chess puzzle by Martin Gardner, taken from the same paper as earlier. The task is to place two rooks, two bishops, and two knights on a 4 by 4 chessboard so that no piece attacks any other. As before, there are two basic solutions, here and here, plus symmetries.The post Another little chess puzzle first appeared on John D. Cook.

The map that takes a quaternionx to the quaternion qx is linear, so it can be represented as multiplication by a matrix. The same is true of the map that takesx toxq, but the two matrices are not the same because quaternion multiplication does not commute. Letq =a + bi + cj +dkand let qM [...]The post Multiplying by quaternions on the left and right first appeared on John D. Cook.

I just revised a post from a week ago about rotations. The revision makes explicit the process of embedding a 3D vector into the quaternions, then pulling it back out. The 3D vector is embedded in the quaternions by making it the vector part of a quaternion with zero real part: (p1,p2,p3) (0, p1,p2,p3) [...]The post Embeddings, Projections, and Inverses first appeared on John D. Cook.

The other day I stumbled on an article [1] that advocated writing abasab and loga(b) as ab. This is a special case of Knuth's up arrow and down arrow notation. Knuth introduces his arrows with the intention of repeating them to represent hyperexponentiation and iterated logarithms. But the emphasis in [1] is more on the [...]The post Alternative exp and log notation first appeared on John D. Cook.

This morning I ran across the following tip from Joost Helberg on Mastodon: TIL don't report numbers with three digits after the decimal point. People may interpret the decimal point as a thousands separator. Using 2 or 4 digits, although wrong, avoids off by a factor thousand errors. I usually report four decimal places, but [...]The post Decimal Separator and Internationalization first appeared on John D. Cook.

Here's a puzzle by Martin Garnder [1]. Can a queen, king, rook, bishop, and knight be placed on a 4^2 board so no piece attacks another? There are two solutions, plus symmetries. Note that in all non-attacking chess puzzles, the colors of the pieces are irrelevant. In the solutions I chose the piece colors to [...]The post A crowded little chess puzzle first appeared on John D. Cook.

The Boolean satisfiability problem is to determine whether there is a way to assign values to variables in a set of Boolean formulas to make the formulas hold [1]. If there is a solution, the next task would be to enumerate the solutions. You can solve the famous eight queens problem, or its generalization ton-queens, [...]The post Formulating eight queens as a SAT problem first appeared on John D. Cook.

There are 92 ways to place eight queens on a chessboard so that no queen is attacking any other. These fall into 12 equivalence classes. The 92 solutions are all rotations and reflections of these 12 basic solutions. If you think about the previous numbers a minute, you might wonder why the total number of [...]The post Special solutions to the eight queens problem first appeared on John D. Cook.

How many bishops can you place on a chessboard so that no bishop is attacking any other bishop? For a standard 8 * 8 chessboard the answer is 14. In general, for an n * n chessboard the answer is 2n - 2. Here's one way to place the maximum number of non-attacking bishops. To [...]The post The non-attacking bishops problem first appeared on John D. Cook.

This morning I wrote about the frequencies of names for popes and kings. This involved sorting strings with Roman numerals since it's common for popes and kings to have Roman numerals after their names. Something that surprised me was that sorting Roman numerals alphabetically roughly sorts them in numerical order, especially for small numbers. It's [...]The post Sorting Roman numerals first appeared on John D. Cook.

After I wrote the code to make the bar graph of papal names for the previous post, I decided to reuse the code to make a similar graph for monarchs of England. Just as there is some complication in counting papal names, there are even more complications in counting names of English monarchs. Who was [...]The post Frequency of names of English monarchs first appeared on John D. Cook.

The new pope chose the name Leo XIV. That made me curious about the distribution of names of popes and so I made the graph below. (I'm Protestant, so wasn't familiar to me.) Looks like Leo is tied with Clement for fourth place, the top three names being John, Benedict, and Gregory. There are a [...]The post Frequency of papal names first appeared on John D. Cook.

The recent post Converting between quaternions and rotation matrices describes an algorithm as a mathematically correct but numerically suboptimal method/" Let's just look at a small piece of that post. The post explains how to find a rotation matrix to describe the same rotation as pre- and post- multiplying by a unit quaternion q, and [...]The post Square root of a small number first appeared on John D. Cook.

Large language models display emergence behaviors: when the parameter count is scaled to a certain value, suddenly the LLM is capable of performing a new task not possible at a smaller size.Some say the abruptness of this change is merely a spurious artifact of how it is measured. Even so, many would like to understand, [...]The post Why do LLMs have emergent properties? first appeared on John D. Cook.

In the previous post I wrote about representing rotations with quaternions. This representation has several advantages, such as making it clear how rotations compose. Rotations are often represented as matrices, and so it's useful to be able to go between the two representations. A unit-length quaternion (q0, q1, q2, q3) represents a rotation by an [...]The post Converting between quaternions and rotation matrices first appeared on John D. Cook.

Every rotation in 3D fixes an axis [1]. This is Euler's rotation theorem from 1775. Another way to state the theorem is that no matter how you rotate a sphere about its center, two points stay fixed. The composition of two rotations is a rotation. So the first rotation fixes some axis, the second rotation [...]The post Composing rotations using quaternions first appeared on John D. Cook.

This is the 5,000th post on this blog. I started blogging in 2008, and Wayne Joubert started contributing posts last year. We've written an average of between five and six posts a week for the last 17 years. I thought about listing some of the most popular posts over the years, but that's not as [...]The post 5,000th post first appeared on John D. Cook.

I recently ran across a simple way to generate random points uniformly distributed on a sphere: Generate random points in a cube until you get one inside the sphere, then push it to the surface of the sphere by normalizing it [1]. In more detail, to generate random points on the unit sphere, generate triples [...]The post A simple way to generate random points on a sphere first appeared on John D. Cook.

I recently ran into Recaman's sequence. N. J. A. Sloane, the founder of the Online Encyclopedia of Integer Sequences calls Recaman's sequence one of his favorites. It's sequence A005132 in the OEIS. This sequence starts at 0 and thenth number in the sequence is the result of moving forward or backwardn steps from the previous [...]The post Recaman's sequence first appeared on John D. Cook.

The last four post have looked at the bifurcation diagram for the logistic map. There was one post on the leftmost region, where there is no branching. Then two posts on the region in the middle where there is period doubling. Then a post about the chaotic region in the end. This post returns the [...]The post Cycle order in period doubling region first appeared on John D. Cook.

The last several posts have been looking at the bifurcation diagram below in slices. The first post looked at the simple part, corresponding to the horizontal axis r running from 0 to 3. The next post looked at the first fork, forr between 3 and 3.4495. The previous post looked at the period doubling region, [...]The post An island of stability in a sea of chaos first appeared on John D. Cook.

The last couple posts have been looking at the logistic bifurcation diagram a little at a time. The first post in the series looked at the details of that part of the diagram that looks like the graph of a function, where there parameterr in the logistic map f(x) =rx(1 -x) varies from o to [...]The post Spacing between branches first appeared on John D. Cook.

The previous post looked at iterations of the logistic map f(x) =rx(1 -x) for 0 r 3. This post will look at the range 3 r 1 + 6. If you're not familiar with the logistic map I'd suggest reading the previous post first then coming back to this one. The [...]The post The first fork first appeared on John D. Cook.

Five years ago I wrote a blog post entitled Logistic bifurcation diagram in detail. Looking back at that post it doesn't seem to be that much in detail," though it does go into more detail than most popular accounts. The logistic map is given by f(x) =rx(1 -x) wherex is a variable between 0 and [...]The post The simple part of the logistic map isn't that simple first appeared on John D. Cook.

It's possible to place n queens on an n * n chess board so that no queen is attacking any other queen, provided n > 3. A queen is able to move any number of squares in any horizontal, vertical, or diagonal direction. Another way to put it is that the queen can move in [...]The post n-queens in 3D first appeared on John D. Cook.

In the latest two posts, we have needed to find the percentage points for a chi square random variable when the parameter , the number of degrees of freedom, is large. In Volume 2 of Knuth's magnum opus TAOCP, he gives a table of percentage points for the chi square distribution for small values of [...]The post Knuth's series for chi squared percentage points first appeared on John D. Cook.

In the previous post I needed to know the tail percentile points for a chi squared distribution with a huge number of degrees of freedom. When the number of degrees of freedom is large, a chi squared random variable has approximately a normal distribution with the same mean and variance, namely mean and [...]The post Chi squared approximations first appeared on John D. Cook.

In the previous post, I did a simulation to illustrate a theorem about the number of steps needed in the Euclidean algorithm. The distribution of the number of steps is asymptotically normal, and fornumbers 0 <a<b<x the mean is asymptotically 12 log(2) log(x) / ^2. What about the variance? The reference cited in the previous [...]The post Variance of variances. All is variance. first appeared on John D. Cook.

The worst case run time for the Euclidean algorithm occurs when you give the algorithm a pair of consecutive Fibonacci numbers. The algorithm takes n steps to compute the greatest common divisor of Fn+1 and Fn+2. Thenth Fibonacci number is the nearest integer to n/5 where = (1 + 5)/2 is the golden ratio. [...]The post Distribution of run times for Euclidean algorithm first appeared on John D. Cook.

The previous post looked at adjoints in the context of linear algebra. This post will look at adjoints in the context of category theory. The adjoint of a linear operator T between inner product spaces V and Wis the linear operatorT* such that for allv inV and allw inW, Tv, wW = v, [...]The post Adjunctions first appeared on John D. Cook.

The transpose of a matrix turns the matrix sideways. Suppose A is an m * n matrix with real number entries. Then the transpose A is ann * m matrix, and the (i,j) element of A is the (j,i) element ofA. Very concrete. The adjoint of a linear operator is a more abstract concept, though [...]The post Transpose and Adjoint first appeared on John D. Cook.

I've heard that barbershop quartets often sing the 7th in a dominant 7th a little flat in order to bring the note closer in tune with the overtone series. This post will quantify that assertion. The overtones of a frequencyf are 2f, 3f, 4f, 5f, etc. The overtone series is a Fourier series. Here's a [...]The post Overtones and Barbershop Quartets first appeared on John D. Cook.

I ran across a video that played around with the equipentatonic scale [1]. Instead of dividing the octave into 12 equal parts, as is most common in Western music, you divide the octave into 5 equal parts. Each note in the equipentatonic scale has a frequency 21/5 times its predecessor. The equipentatonic scale is used [...]The post Equipentatonic scale first appeared on John D. Cook.

I've written about the Coupon Collector Problem and variations several times, most recently here. Brian Beckman left a comment linking to an article he wrote, which in turn links to a paper on the Double Dixie Cup Problem[1]. The idea behind the Coupon Collector Problem is to estimate how long it will take to obtain [...]The post The multiple coupon collector problem first appeared on John D. Cook.

Musician Adam Neely made a video asking What is the fastest music humanly possible? He emphasizes that he means the fastest music possible to hear, not the fastest to perform. The video cites a psychology article [1] from 1894 that found that most people can reliably distinguish an inter-onset interval (time between notes) of 100 [...]The post Morse code and the limits of human perception first appeared on John D. Cook.

Toward the end of last year I wrote several blog posts about calendars. The blog post about the Gregorian calendar began with this paragraph. The time it takes for the earth to orbit the sun is not an integer multiple of the time it takes for the earth to rotate on its axis, nor is [...]The post Running the Gregorian calendar backwards first appeared on John D. Cook.

The Fredholm alternative is so called because it is a theorem by the Swedish mathematician Erik Ivar Fredholm that has two alternative conclusions: either this is true or that is true. This post will state a couple forms of the Fredholm alternative. Mr. Fredholm was interested in the solutions to linear integral equations, but his [...]The post Fredholm Alternative first appeared on John D. Cook.

The previous post on kernels and cokernels mentioned that for a linear operator T:VW, the index ofT is defined as the difference between the dimension of its kernel and the dimension of its cokernel: index T = dim ker T- dim cokerT. The index was first called the Fredholm index, because of it came up [...]The post Fredholm index first appeared on John D. Cook.

The kernel of a linear transformation is the set of vectors mapped to 0. That's a simple idea, and one you'll find in every linear algebra textbook. The cokernel is the dual of the kernel, but it's much less commonly mentioned in textbooks. Sometimes the idea of a cokernel is there, but it's not given [...]The post Kernel and Cokernel first appeared on John D. Cook.