John D. Cook

A probable prime is a number that passes a test that all primes pass and that most composite numbers fail. Specifically, a Fermat probable prime is a number that passes Fermat’s primality test. Fermat’s test is the most commonly used, so that’s nearly always what anyone means by probable prime unless they’re more specific. A […]

Here is a plot of the first 30 Chebyshev polynomials. Notice the interesting patterns in the white space. Forman Acton famously described Chebyshev polynomials as “cosine curves with a somewhat disturbed horizontal scale.” However, plotting cosines with frequencies 1 to 30 gives you pretty much a solid square. Something about the way Chebyshev polynomials disturb […]

Suppose you fill two n×n matrices with random integers. What is the probability that the determinants of the two matrices are relatively prime? By “random integers” we mean that the integers are chosen from a finite interval, and we take the limit as the size of the interval grows to encompass all integers. Let Δ(n) […]

If a function is smooth and has thin tails, it can be well approximated by sinc functions. These approximations are frequently used in applications, such as signal processing and numerical integration. This post will illustrate sinc approximation with the function exp(-x²). The sinc approximation for a function f(x) is given by where sinc(x) = sin(πx)/πx. […]

The most obvious way to compute the determinant of a 2×2 matrix can be numerically inaccurate. The biggest problem with computing ad – bc is that if ad and bc are approximately equal, the subtraction could lose a lot of precision. William Kahan developed an algorithm for addressing this problem. Fused multiply-add (FMA) Kahan’s algorithm […]

Given a curve of a fixed length, how do you maximize the area inside? This is known as the isoperimetric problem. The answer is to use a circle. The solution was known long before it was possible to prove; proving that the circle is optimal is surprisingly difficult. I won’t give a proof here, but […]

The curse of dimensionality refers to problems whose difficulty increases exponentially with dimension. For example, suppose you want to estimate the integral of a function of one variable by evaluating it at 10 points. If you take the analogous approach to integrating a function of two variables, you need a grid of 100 points. For […]

I’ve recently started reading One Giant Leap, a book about the Apollo missions. In a section on nuclear testing, the book describes what was believed to be a connection between weapon tests and tornadoes. In 1953 and 1954 there were all-time record outbreaks of tornadoes across the US, accompanied by fierce thunderstorms. The belief that […]

It’s hard to understand anything from just one example. One of the reason for studying other planets is that it helps us understand Earth. It can even be helpful to have more examples when the examples are purely speculative, such as xenobiology, or even known to be false, i.e. counterfactuals, though here be dragons. The […]

This post will take a familiar theorem in a few less familiar directions. The Fundamental Theorem of Algebra (FTA) says that an nth degree polynomial over the complex numbers has n roots. The theorem is commonly presented in high school algebra, but it’s not proved in high school and it’s not proved using algebra! A […]

The first fundamental theorem of calculus says that integration undoes differentiation. The second fundamental theorem of calculus says that differentiation undoes integration. This post looks at the fine print of these two theorems, in their basic forms and when generalized to Lebesgue integration. Second fundamental theorem of calculus We’ll start with the second fundamental theorem […]

There are only a few examples of Fourier series that are relatively easy to compute by hand, and so these examples are used repeatedly in introductions to Fourier series. Any introduction is likely to include a square wave or a triangle wave [1]. By square wave we mean the function that is 1 on [0, […]

One source of distortion in electronic music is clipping. The highest and lowest portions of a wave form are truncated due to limitations of equipment. As the gain is increased, the sound doesn’t simply get louder but also becomes more distorted as more of the signal is clipped off. Clipping 0.2 For example, here is […]

This morning Patrick Honner posted the image below on Twitter. The image was created by Robert Bosch by solving a “traveling salesman” problem, finding a nearly optimal route for passing through 12,000 points. I find this interesting for a couple reasons. For one thing, I remember when the traveling salesman problem was considered intractable. And […]

Several people have told me they can’t understand most of my math posts, but they subscribe because they enjoy the occasional math post that they do understand. If you’re in that boat, thanks for following, and I wanted to let you know there have been a few posts lately that are more accessible than you […]

It would seem that sums and means are trivially related; the mean is just the sum divided by the number of items. But when you generalize things a bit, means and sums act differently. Let x be a list of n non-negative numbers, and let r > 0 [*]. Then the r-mean is defined to […]

I ran across someone recently who says the way to move past object oriented programming (OOP) is to go back to simply telling the computer what to do, to clear OOP from your mind like it never happened. I don’t think that’s a good idea, but I also don’t think it’s possible. Object oriented programming, […]

The previous post looked an integral that is “impossible” in the sense that it cannot be computed in closed form. It can be integrated in terms of special functions, and it can easily be computed numerically to as much accuracy as anyone would want. In this post I’ll present a simple approximation that calculus students […]

In the Broadway musical Man of La Mancha, Don Quixote sings To dream the impossible dream To fight the unbeatable foe To bear with unbearable sorrow To run where the brave dare not go Yesterday my daughter asked me to integrate the impossible integral, and this post has a few thoughts on the quixotic quest […]

Sometimes you have a poor quality source of randomness and you want to refine it into a better source. You might, for example, want to generate cryptographic keys from a hardware source that is more likely to produce 1’s than 0’s. Or maybe your source of bits is dependent, more likely to produce a 1 […]

There are numerous web sites that will let you upload a PostScript (.ps) file and download it as a PDF. Some of these online file format conversion sites look sketchy, and the ones that seem more reputable don’t always do a good job. If you want to convert PostScript to PDF locally, I’d suggest trying […]

There are two sequences of polynomials named after Chebyshev, and the first is so much more common that when authors say “Chebyshev polynomial” with no further qualification, they mean Chebyshev polynomials of the first kind. These are denoted with Tn, so they get Chebyshev’s initial [1]. The Chebyshev polynomials of the second kind are denoted […]

There’s more juice left in the lemon we’ve been squeezing lately. A few days ago I first brought up the equation which holds because both sides equal exp(inθ). Then a couple days ago I concluded a blog post by noting that by taking the real part of this equation and replacing sin²θ with 1 – […]

This morning I had someone from a pharmaceutical company call me with questions about conducting a CRM dose-finding trial and I mentioned it to my wife. Then this afternoon she was reading a book in which there was a dialog between husband and wife including this sentence: He launched into a technical explanation of his […]

This post is a list of five spinoffs of my previous post. Except for the last point it doesn’t build on the previous post per se, but I’ll use a sum from that post to illustrate five things: Putting multiple things under a summation sign in LaTeX Simplifying sums by generalizing binomial coefficients A bit […]

If you have sines and cosines of some fundamental frequency, and you’re able to take products and sums, then you can construct sines and cosines at any multiple of the fundamental frequency. Here’s a proof. Taking real parts gives us cos nθ in the first equation and the even terms of the sum in the […]

A new article [1] looks at the problem of determining the proportion of odd numbers that can be written as a power of 2 and a prime. A. de Polignac conjectured in 1849 that all odd numbers have this form. A counterexample is 127, and so apparently the conjecture was that every odd number is […]

Quick observation: I recently noticed that Chebyshev polynomials and Fibonacci numbers have analogous formulas. The nth Chebyshev polynomial satisfies for |x| ≥ 1, and the nth Fibonacci number is given by There’s probably a way to explain the similarity in terms of the recurrence relations that both sequences satisfy. More on Chebyshev polynomials Yogi Berra […]

Here are five things I appreciate about using Emacs. They also apply to any software that runs entirely on your computer. It doesn’t track me. It doesn’t show me ads. It doesn’t require two-factor authentication. It doesn’t change unless I change it. It doesn’t stop working if my internet connection stops working. Related post: Negative […]

Suppose you have a mass suspended by the combination of a spring and a rubber band. A spring resists being compressed but a rubber band does not. So the rubber band resists motion as the mass moves down but not as it moves up. In [1] the authors use this situation to motivate the following […]

In the previous post, I showed how to plot “envelopes of epicycloids.” This post will consider a variation on the same theme, hypocycloids. For the epicycloid post, we imagined two ants crawling around a circle at different speeds, and drawing lines between their positions at various times. Although the ants were traveling at different speeds, […]

Imagine two ants crawling around a circle at different speeds and draw a line between the two ants at regular time intervals. The position of the two ants at time t are (cos pt, sin pt) and (cos qt, sin qt) where p and q are integers, p > q > 0, and t comes from dividing the […]

I saw a link to So You Think You Know C? by Oleksandr Kaleniuk on Hacker News and was pleasantly surprised. I expected a few comments about tricky parts of C, and found them, but there’s much more. The subtitle of the free book is And Ten More Short Essays on Programming Languages. Good reads. […]

Most cubic polynomials with real coefficients have two turning points, a local maximum and a local minimum. But how do you quantify “most”? Here’s how one author did it [1]. Start with the cubic polynomial x³ + ax² + bx + c Since multiplying a polynomial by a nonzero constant doesn’t change how many turning […]

In the previous post, I looked at truncated probability distributions. A truncated normal distribution, for example, lives on some interval and has a density proportional to a normal distribution; the proportionality constant is whatever it has to be to make the density integrate to 1. Truncated distributions Suppose you wanted to generate random samples from […]

The Cauchy distribution is the probability distribution on the real line with density proportional to 1/(1 + x²). It comes up often as an example of a fat-tailed distribution, one that can wreak havoc on intuition and on applications. It has no mean and no variance. The truncated Cauchy distribution has the same density, with […]

In the previous post I present a bash one-liner to search directories for LaTeX files and count the commands used. College files I first tried this out on a directory that included some old files from grad school. I chose this directory because I knew it had a lot of LaTeX files, but I was […]

I started this post by wanting to look at the frequency of LaTeX commands, but then thought that some people mind find the code to find the frequencies more interesting than the frequencies themselves. So I’m splitting this into two posts. This post will look at the shell one-liner to find command frequencies, and the […]

If we have two unrelated sequences of DNA, how long would we expect the longest common substring of the the two sequences to be? Since DNA sequences come from a very small alphabet, just four letters, any two sequences of moderate length will have some common substring, but how long should we expect it to […]

If you raise any number to the fifth power, the last digit doesn’t change. Here’s a little Python code to verify this claim. >>> [n**5 for n in range(10)] [0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049] In case you’re not familiar with Python, or familiar with Python but not familiar with list […]

A while back I wrote about Kronecker products in the context of higher order Taylor series. Here’s how I described the Kronecker product in that post. The Kronecker product of an m × n matrix A and a p × q matrix B is a mp × nq matrix K = A ⊗ B. You can think of K as a block partitioned matrix. The ij block […]

Bob Martin recently posted a nice pair of articles, A Little Clojure and A Little More Clojure. In the first article he talks about how spare and elegant Clojure is. In the second article he shows how to write a program to list primes using map and filter rather than if and while. He approaches […]

This seems like a good time to discuss the difference between exponential growth and logistic growth as the covid19 pandemic is starting to look more like a logistic model and less like an exponential model, at least in many parts of the world [1]. This post is an expansion of a Twitter thread I wrote […]

The Fourier series of an odd function only has sine terms—all the cosine coefficients are zero—and so the Fourier series is a sine series. What is the sine series for a sine function? If the frequency is an integer, then the sine series is just the function itself. For example, the sine series for sin(5x) […]

“QR code” can mean a couple different things. There is a connection between these two, though that’s not at all obvious. What almost everyone thinks of as a QR code is a quick response code, a grid of black and white squares that encode some data. For example, the QR code below contains my contact […]

Para Parasolian left a comment on my post about computing the area of a polygon, suggesting that I “say something similar about computing the centroid of a polygon using a similar formula.” This post will do that, and at the same time discuss vectorization. Notation We start by listing the vertices starting anywhere and moving […]

How can you make an invertible function out of non-invertable parts? Why would you want to? Encryption functions must be invertible. If the intended recipient can’t decrypt the message then the encryption method is useless. Of course you want an encryption function to be really hard to invert without the key. It’s hard to think […]

When I hear that a system has a one in a trillion (1,000,000,000,000) chance of failure, I immediately translate that in my mind to “So, optimistically the system has a one in a million (1,000,000) chance of failure.” Extremely small probabilities are suspicious because they often come from one of two errors: Wrongful assumption of […]

Reasoning under uncertainty sounds intriguing. Brings up images of logic, philosophy, and artificial intelligence. Statistics sounds boring. Brings up images of tedious, opaque calculations followed by looking some number in a table. But statistics is all about reasoning under uncertainty. Many people get through required courses in statistics without ever hearing that, or at least […]

The Hamming distance between two sequences of symbols is the number of places in which they differ. For example, the Hamming distance between the words “hamming” and “farming” is 2, because the two worlds differ in their first and third letters. Hamming distance is natural when comparing sequences of bits because bits are either the […]