John D. Cook

If and when large-scale quantum computing becomes practical, most public key encryption algorithms currently in use would be breakable. Cryptographers have known this since Peter Shor published his quantum factoring algorithm in 1994. In 2017 researchers submitted 69 algorithms to the NIST Post-Quantum Cryptography Standardization Process. In 2019 NIST chose 26 of these algorithms to […]

Courant & Hilbert is a classic applied math textbook, still in print nearly a century after the first edition came out. The actual title of the book is Methods of Mathematical Physics, but everyone calls it Courant & Hilbert after the authors, Richard Courant and David Hilbert. I was surprised to find out recently that […]

For an n by n real matrix A, Hadamard’s upper bound on determinant is where aij is the element in row i and column j. See, for example, [1]. How tight is this upper bound? To find out, let’s write a little Python code to generate random matrices and compare their determinants to Hadamard’s bounds. […]

Ten years ago I wrote about how cosine makes a decent approximation to the normal (Gaussian) probability density. It turns out you get a much better approximation if you raise cosine to a power. If we normalize cosk(t) by dividing by its integral we get an approximation to the density function for a normal distribution […]

Programmers like highly expressive programming languages, but programing managers do not. I wrote about this on Twitter a few months ago. Q: Why do people like Lisp so much? A: Because Lisp is so expressive. Q: Why don’t teams use Lisp much? A: Because Lisp is so expressive. Q: Why do programmers complain about Java? […]

Routine computer tasks and system programming require different tools, though I’m not entirely sure why. Many people have thought about how inconsistent shells and system programming languages are and tried to unite them. Wouldn’t it be nice to use one language for everything? But attempts to bring system languages down to the shell, or to […]

Yesterday I posted on @TopologyFact The uniform limit of continuous functions is continuous. John Baez replied that this theorem was proved by his “advisor’s advisor’s advisor’s advisor’s advisor’s advisor.” I assume he was referring to Christoph Gudermann. The impressive thing is not that Gudermann was able to prove this simple theorem. The impressive thing is […]

Suppose you have a computer that can evaluate and compose continuous functions of one real variable and can do addition. What kinds of functions could you compute with it? You could compute functions of one variable by definition, but could you bootstrap it to compute functions of two variables? Here’s an example that shows this […]

The first step in solving a cubic equation is to apply a change of variables to reduce an equation of the form x³ + bx² + cx + d = 0 to one of the form y³ + py + q = 0. This process can be carried further through Tschirnhausen transformations, a generalization of […]

The so-called “leapfrog” integrator is a numerical method for solving differential equations of the form where x is a function of t. Typically x is position and t is time. This form of equation is common for differential equations coming from mechanical systems. The form is more general than it may seem at first. It […]

Let Ω be an open set in some Euclidean space and v a real-valued function on Ω. Dirichlet principle Dirichlet’s integral for v, also called the Dirichlet energy of v, is Among functions with specified values on the boundary of Ω, Dirichlet’s principle says that minimizing Dirichlet’s integral is equivalent to solving Laplace’s equation. In […]

People who haven’t written large programs think that writing software is easy. All you have to do is break a big problem into smaller problems until you have something so small that it’s easy to program. The problem is putting the pieces back together. If you’ve only written small programs, you haven’t had many pieces […]

Here’s a silly graph by Richard West with a serious point. States with longer names tend to have higher covid19 mortality. Of course no one believes there’s anything about the length of a state’s name that should impact the health of its residents. The correlation is real, but it’s a coincidence. The variation between mortality […]

You can read the title of this post as ((Morse code) golf) or as (Morse (code golf)). Morse code is a sort of approximate Huffman coding of letters: letters are assigned symbols so that more common letters can be transmitted more quickly. You can read about how well Morse code achieves this design objective here. […]

I’ve written several times about the “squircle,” a sort of compromise between a square and a circle. It looks something like a square with rounded corners, but it’s not. Instead of having flat sizes (zero curvature) and circular corners (constant positive curvature), the curvature varies continuously. A natural question is just what kind of circle […]

A couple days ago I wrote a post about some doubled words I found on my site. Someone asked about triple words, so I looked. Here are some of the things I found. One example was a post where I commented on a song from Fiddler on the Roof where Teva sings If I were […]

Curvature is a measure of how tightly a curve bends. A circle of radius r has curvature 1/r. So a small circle has high curvature and a big circle has small curvature. In general the curvature of a curve at a point is defined to be the curvature of the circle that best fits at […]

Double words such as “the the” are a common source of writing errors. On the other hand, some doubled words are legitimate. You might, for example, find “had had” or “that that” in a grammatically correct sentence. I’ve been looking through my web site to purge erroneous double words, and found a few doubles that […]

A while back I ran across a paper [1] giving a trick for evaluating integrals of the form where M is large and f is an increasing function. For large M, the integral is asymptotically That is, the ratio of A(M) to I(M) goes to 1 as M goes to infinity. This looks like a […]

A parabola and a catenary can look very similar but are not the same. The graph of y = x² is a parabola and the graph of y = cosh(x) = (ex + e–x)/2 is a catenary. You’ve probably seen parabolas in a math class; you’ve seen a catenary if you’ve seen the St. Louis […]

The Sierpiński triangle is a fractal that comes up in unexpected places. I’m not that interested in fractals, and yet I’ve mentioned the Sierpiński triangle many times on this blog just because I run into it while looking at something else. The first time I wrote about the Sierpiński triangle was when it came up […]

The set of lines perpendicular to a curve are tangent to a second curve called the evolute. The lines perpendicular to the ellipse below are tangent to the curve inside called an astroid. If we replace the ellipse with an egg, we get a similar shape, but less symmetric. The equation for the egg is […]

If you’re going to run a test on rabbits, you have to decide how many rabbits you’ll use. This is your sample size. A lot of what statisticians do in practice is calculate sample sizes. A researcher comes to talk to a statistician. The statistician asks what effect size the researcher wants to detect. Do […]

Imagine seeing the following calculation: The correct result is and so the first calculation is off by 25 orders of magnitude. But there’s a variation on the calculation above that is correct! A theorem by Édouard Lucas from 1872 that says for p prime and for any nonnegative integers m and n, So while the […]

Suppose you’re given two points (x1, y1) and (x2, y2) with y1 and y2 positive. Find the smooth positive curve f(x) that passes through the two points such that the area of the surface formed by rotating the graph of f around the x-axis is minimized. You can state this as a problem in calculus […]

How do the frequencies of chemical element names in English text compare to the abundance of elements in Earth’s crust? Do we write most frequently about the elements that appear most frequently? It turns out the answer is “not really.” The rarest elements rarely appear in writing. We don’t have much to say about dysprosium, […]

Sam Walters posted an elegant theorem on his Twitter account this morning. The theorem follows the pattern of an equality for linear functions generalizing to an inequality for convex functions. We’ll give a little background, state the theorem, and show an example application. Let A be a real symmetric n×n matrix, or more generally a […]

Someone asked an interesting question on MathOverflow: given an odd number, can you always flip a bit in its binary representation to make it prime? It turns out the answer is no, but apparently it is very often the case an odd number is just a bit flip away from being prime. I find that […]

After finding the NASA publication I mentioned in my previous post, I poked around a while longer in the NASA Technical Reports Server and found a few curiosities. One was that at one time NASA was interested in shapes that similar to the superellipses and squircles I’ve written about before. A report [1] that I […]

NASA’s Orbital Flight Handbook, published in 1963, is a treasure trove of technical information, including a section comparing the strengths and weaknesses of several numerical methods for solving differential equations. The winner was a predictor-corrector scheme known as Gauss-Jackson, a method I have not heard of outside of orbital mechanics, but one apparently particularly well […]

How does a spacecraft orbiting a planet move from one circular orbit to another? It can’t just change lanes like a car going around a racetrack because speed and altitude cannot be changed independently. The most energy-efficient way to move between circular orbits is the Hohmann transfer orbit [1]. The Hohmann orbit is an idealization, […]

Polynomials form a vector space—the sum of two polynomials is a polynomial etc.—and the most natural basis for this vector space is powers of x: 1, x, x², x³, … But the power basis is not the only possible basis, and often not the most useful basis in application. Falling powers In some applications the […]

Many methods for numerically solving ordinary differential equations are either Runge-Kutta methods or linear multistep methods. These methods can either be explicit or implicit. The table below shows the four combinations of these categories and gives some examples of each. Runge-Kutta methods advance the solution of a differential equation one step at a time. That […]

Before I went to college, I’d heard that it took new math and science for Apollo to get to the moon. Then in college I picked up the idea that Apollo required a lot of engineering, but not really any new math or science. Now I’ve come full circle and have some appreciation for the […]

Gabriel’s horn is the surface created by rotating 1/x around the x-axis. It is often introduced in calculus classes as an example of a surface with finite volume and infinite surface area. If it were a paint can, it could not hold enough paint to paint itself! This post will do two things: explain why […]

Here’s a plot of exp(6it)/2 + exp(20it)/3: Notice that the plot has 7-fold symmetry. You might expect 6-fold symmetry from looking at the equation. Where did the 7 come from? I produced the plot using the code from this post, changing the line defining the function to plot to def f(t): return exp(6j*t)/2 + exp(20j*t)/3 […]

I realized recently that I’ve written about generalized Gibbs phenomenon, but I haven’t written about its original context of Fourier series. This post will rectify that. The image below comes from a previous post illustrating Gibbs phenomenon for a Chebyshev approximation to a step function. Although Gibbs phenomena comes up in many different kinds of […]

My first consulting project, right after I graduated college, was developing floating point algorithms for a microprocessor. It was fun work, coming up with ways to save a clock cycle or two, save a register, get an extra bit of precision. But nobody does that kind of work anymore. Or do they? There is still […]

In previous post I showed how to compute the square root of a complex number. I gave as an example that computed the square root of 5 + 12i to be 3 + 2i. (Of course complex numbers have two square roots, but for convenience I’ll speak of the output of the algorithm as the […]

Suppose you’re given a complex number z = x + iy and you want to find a complex number w = u + iv such that w² = z. If all goes well, you can compute w as follows: ℓ = √(x² + y²) u = √((ℓ + x)/2) v = sign(y) √((ℓ – x)/2). […]

“How would you go about drawing a random sample?” I thought that was kind of a silly question. I was in my first probability class in college, and the professor started the course with this. You just take a sample, right? As with many things in life, it gets more complicated when you get down […]

The Peter Principle is an idea that was developed by Lawrence Peter and expanded into a book coauthored with Raymond Hull in 1969. It says that people rise to their level of incompetence. According to the Peter Principle, competent people are repeatedly promoted until they get to a level where they’re not bad enough to […]

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 […]