John D. Cook

Lucas numbers [1] are sometimes called the companions to the Fibonacci numbers. This sequence of numbers satisfies the same recurrence relation as the Fibonacci numbers, Ln+2 = Ln + Ln+1 but with different initial conditions: L0 = 2 and L1 = 1. Lucas numbers are analogous to Fibonacci numbers in many ways, but are also [...]The post Lucas numbers and Lucas pseudoprimes first appeared on John D. Cook.

Given a hash value, can you determine what algorithm produced it? Or what algorithm probably produced it? Obviously if a hash value is 128 bits long, then a 128-bit algorithm produced it. Such a hash value might have been produced by MD5, but not by SHA-1, because the former produces 128-bit hashes and the latter [...]The post Identifying hash algorithms first appeared on John D. Cook.

Random number generators are subtle. Unless the generator is some physical device, random number generators (RNGs) are usually technically pseudorandom number generators (PRNGs), deterministic algorithms designed to mimic randomness. Suppose you have a PRNG that produces the digits 0 through 9. How might you test the output to see whether it (acts like it) is [...]The post Testing random number generators first appeared on John D. Cook.

Why do Venn diagrams almost always show the intersections of three sets and not more? Can Venn diagrams be generalized to show all intersections of more sets? That depends on the rules you give yourself for generalization. If you require that your diagram consist of circles, then three is the limit. As John Venn put [...]The post Limitations on Venn diagrams first appeared on John D. Cook.

I was just talking to a colleague about edit distance because it came up in a project we're working on. Technically, we were discussing Levenshtein distance. It sounds more impressive to say Levenshtein distance, but it's basically how much editing effort it would take to turn one block of text into another. Edit distance is [...]The post Edit distance first appeared on John D. Cook.

The birthday problem is a party trick with serious practical applications. It's well known to people who have studied probability, but the general public is often amazed by it. If you have a group of 23 people, there's a 50-50 chance that at least two people have the same birthday. With a larger group, say [...]The post Birthday problem approximation first appeared on John D. Cook.

I keep running into the function f(z) = (1 - z)/(1 + z)." I wrote this three years ago and it's still true. This function came up implicitly in the previous post. Ramanujan's excellent approximation for the perimeter of an ellipse with semi-axes a and b begins by introducing = (a - b)/(a + [...]The post (1 - z) / (1 + z) first appeared on John D. Cook.

Ramanujan discovered an incredibly accurate approximation for the perimeter of an ellipse. This post will illustrate how accurate the approximation is and push its limits. As with all computations involving ellipses, the error of Ramanujan's approximation increases as eccentricity increases. But the error increases slowly, asymptotically approaching an upper bound that is remarkably small. Let [...]The post Error in Ramanujan's approximation for ellipse perimeter first appeared on John D. Cook.

Someone with no exposure to probability or statistics likely has an intuitive sense that averaging random variables reduces variance, though they wouldn't state it in those terms. They might, for example, agree that the average of several test grades gives a better assessment of a student than a single test grade. But data from a [...]The post The Cauchy distribution's counter-intuitive behavior first appeared on John D. Cook.

I recently ran across a theorem connecting the arithmetic mean, geometric mean, harmonic mean, and the golden ratio. Each of these comes fairly often, and there are elegant connections between them, but I don't recall seeing all four together in one theorem before. Here's the theorem [1]: The arithmetic, geometric, and harmonic means of two [...]The post Arithmetic, Geometry, Harmony, and Gold first appeared on John D. Cook.

I keep running into Edward John Routh (1831-1907). He is best known for the Routh-Hurwitz stability criterion but he pops up occasionally elsewhere. The previous post discussed Routh's mnemonic for moments of inertia and his stretch" theorem. This post will discuss his triangle theorem. Before stating Routh's theorem, we need to say what a cevian [...]The post Ceva, cevians, and Routh's theorem first appeared on John D. Cook.

Edward John Routh (1831-1907) came up with a mnemonic for summarizing many formulas for moment of inertia of a solid rotating about an axis through its center of mass. Routh's mnemonic is I = MS / k where M is the mass of an object, S is the sum of the squares of the semi-axes, [...]The post Moments of inertia mnemonic first appeared on John D. Cook.

I recently came across an upper bound I hadn't seen before [1]. Given a binomial coefficient C(r, k), let n = min(k, r - k) and m = r - n. Then for any > 0, C(n + m, n) (1 + )n + m / n. The proof follows quickly from applying [...]The post Binomial bound first appeared on John D. Cook.

I was skimming through the book Mathematical Reflections [1] recently. He was discussing a set of generalizations [2] of the Star of David theorem from combinatorics. The theorem is so named because if you draw a Star of David by connecting points in Pascal's triangle then each side corresponds to the vertices of a triangle. [...]The post Separable functions in different contexts first appeared on John D. Cook.

Body Roundness Index (BRI) is a proposed replacement for Body Mass Index (BMI) [1]. Some studies have found that BRI is a better measure of obesity and a more effective predictor of some of the things BMI is supposed to predict [2]. BMI is based on body mass and height, and so it cannot distinguish [...]The post Body roundness index first appeared on John D. Cook.

I've written a couple posts on the approximation by the Indian astronomer Aryabhata (476-550). The approximation is accurate for x in [-/2, /2]. The first post collected a Twitter thread about the approximation into a post. The second looked at how far the coefficients in Aryabhata's approximation are from the optimal approximation as a ratio [...]The post A couple more variations on an ancient theme first appeared on John D. Cook.

Write the letters of the alphabet around a circle, then strike out the letters that are symmetrical about a vertical line. The remaining letters are grouped in clumps of 3, 1, 4, 1, and 6 letters. I've heard that this observation is due to Martin Gardner, but I don't have a specific reference. In case [...]The post Finding pi in the alphabet first appeared on John D. Cook.

A few days ago I wrote about the approximation for cosine due to the Indian astronomer Aryabhata (476-550) and gave this plot of the error. I said that Aryabhata's approximation is not quite optimal since the ripples in the error function are not of equal height." This was an allusion to the equioscillation theorem. Chebyshev [...]The post Optimal rational approximation first appeared on John D. Cook.

As mentioned in the previous post, the ratio of consecutive Fibonacci numbers converges to the golden ratio. Is there a sequence whose ratios converge to the silver ratio the way ratios of Fibonacci numbers converge to the golden ratio? (If you're not familiar with the silver ratio, you can read more about it here.) The [...]The post Pell is to silver as Fibonacci is to gold first appeared on John D. Cook.

The number of kilometers in a mile is k = 1.609344 which is close to the golden ratio = 1.6180334. The ratio of consecutive Fibonacci numbers converges to , and so you can approximately convert miles to kilometers by multiplying by a Fibonacci number and dividing by the previous Fibonacci number. For example, you [...]The post Miles to kilometers first appeared on John D. Cook.

This post started out as a Twitter thread. The text below is the same as that of the thread after correcting an error in the first part of the thread. I also added a footnote on a theorem the thread alluded to. *** The following approximation for sin(x) is remarkably accurate for 0 < x [...]The post Ancient accurate approximation for sine first appeared on John D. Cook.

This post will give three ways to multiply by taken from [1]. Simplest approach Here's a very simple observation about : 3 + 0.14 + 0.0014. So if you need to multiply by , you need to multiply by 3 and by 14. Once you've multiplied by 14 once, you can [...]The post Mentally multiply by first appeared on John D. Cook.

For a standard normal random variable Z, the probability that Z exceeds some cutoff z is given by If you wanted to compute this probability numerically, you could obviously evaluate its defining integral numerically. But as is often the case in numerical analysis, the most obvious approach is not the best approach. The range of [...]The post A better integral for the normal distribution first appeared on John D. Cook.

Take a compass and draw a circle on a globe. Then take the same compass, opened to the same width, and draw a circle on a flat piece of paper. Which circle has more area? If the circle is small compared to the radius of the globe, then the two circles will be approximately equal [...]The post Drawing with a compass on a globe first appeared on John D. Cook.

The Poisson probability distribution gives a simple, elegant model for count data. You can even derive from certain assumptions that data must have a Poisson distribution. Unfortunately reality doesn't often go along with those assumptions. A Poisson random variable with mean also has variance . But it's often the case that data that would [...]The post The negative binomial distribution and Pascal's triangle first appeared on John D. Cook.

It is well known that the harmonic series 1 + + + 1/4 + ... diverges. But if you take the denominators as numbers in base 11 or higher, the series converges [1]. I wonder what inspired this observation. Maybe Brewster was bored, teaching yet another cohort of students that the harmonic series [...]The post A strange take on the harmonic series first appeared on John D. Cook.

Suppose you have two normal random variables, X and Y, and that the variance of X is less than the variance of Y. Let M be an equal mixture of X and Y. That is, to sample from M, you first chose X or Y with equal probability, then you choose a sample from the [...]The post Variance matters more than mean in the extremes first appeared on John D. Cook.

Orbital mechanics is fascinating. I've learned a bit about it for fun, not for profit. I seriously doubt Elon Musk will ever call asking me to design an orbit for him. [1] One of the things that makes orbital mechanics interesting is that it can be counter-intuitive. For example, atmospheric friction can make a satellite [...]The post Increasing speed due to friction first appeared on John D. Cook.

Draw a quadrilateral by pick four arbitrary points on a circle and connecting them cyclically. Now multiply the lengths of the pairs of opposite sides. In the diagram below this means multiplying the lengths of the two horizontal-ish blue sides and the two vertical-ish orange sides. Ptolemy's theorem says that the sum of the two [...]The post Ptolemy's theorem first appeared on John D. Cook.

There is a simple rule of thumb for converting between (circular) trig identities and hyperbolic trig identities known as Osborn's rule: stick an h on the end of trig functions and flip signs wherever two sinh functions are multiplied together. Examples For example, the circular identity sin( + ) = sin() cos() + cos() sin() [...]The post Rule for converting trig identities into hyperbolic identities first appeared on John D. Cook.

This weekend I wrote three posts related to interpolation: Compression and interpolation Bessel, Everett, and Lagrange interpolation Binomial coefficients with non-integer arguments The first post looks at reducing the size of mathematical tables by switching for linear to quadratic interpolation. The immediate application is obsolete, but the principles apply to contemporary problems. The second post [...]The post Interpolation and the cotanc function first appeared on John D. Cook.

When n and r are positive integers integers, with n >= r, there is an intuitive interpretation of the binomial coefficient C(n, r), namely the number of ways to select r things from a set of n things. For this reason C(n, r) is usually pronounced n choose r." But what might something like C(4.3, [...]The post Binomial coefficients with non-integer arguments first appeared on John D. Cook.

I never heard of Bessel or Everett interpolation until long after college. I saw Lagrange interpolation several times. Why Lagrange and not Bessel or Everett? First of all, Bessel interpolation and Everett interpolation are not different kinds of interpolation; they are different algorithms for carrying out the same interpolation as Lagrange. There is a unique [...]The post Bessel, Everett, and Lagrange interpolation first appeared on John D. Cook.

Data compression is everywhere. We're unaware of it when it is done well. We only become aware of it when it is pushed too far, such as when a photo looks grainy or fuzzy because it was compressed too much. The basic idea of data compression is to not transmit the raw data but to [...]The post Compression and interpolation first appeared on John D. Cook.

Forman Acton's book Numerical Methods that Work describes Chebyschev polynomials as cosine curves with a somewhat disturbed horizontal scale, but the vertical scale has not been touched. The relation between Chebyshev polynomials and cosines is Tn(cos ) = cos(n). Some sources take this as the definition of Chebyshev polynomials. Other sources define the polynomials differently [...]The post Chebyshev polynomials as distorted cosines first appeared on John D. Cook.

The convention in math for writing numbers in bases larger than 10 is to insert capital letters after 9, starting with A. So, for example, the digits in base 12 are 0, 1, 2, ..., 9, A, and B. So if you're familiar with math but not Linux, and you run across the base32 utility, [...]The post Math's base 32 versus Linux's base 32 first appeared on John D. Cook.

I don't use sed very often, but it's very handy when I do use it, particularly when needing to make a small change to a large file. Fixing a JSON file Lately I've been trying to fix a 30 MB JSON file that has been corrupted somehow. The file is one very long line. Emacs [...]The post Editing a file without an editor first appeared on John D. Cook.

Suppose you wanted to approximate (10.3). You know it's somewhere between (10) = 9! and (11) = 10!, and linear interpolation would give you (10.3) 0.7 * 9! + 0.3 * 10! = 1342656. But the exact value is closer to 716430.69, and so our estimate is 53% too high. Not a very good [...]The post Interpolating the gamma function first appeared on John D. Cook.

One way to find the volume of a sphere would be to imagine the sphere in a box, randomly select points in the box, and count how many of these points fall inside the sphere. In principle this would work in any dimension. The problem with naive Monte Carlo We could write a program to [...]The post Too clever Monte Carlo first appeared on John D. Cook.

The other day I ran across the surprising identity and wondered how many sums of this form can be evaluated in closed form like this. Quite a few it turns out. Sums of the form evaluate to a rational number when k is a non-negative integer and c is a rational number with |c| > [...]The post Evaluating a class of infinite sums in closed form first appeared on John D. Cook.

Center a small blue sphere on every corner of ann-dimensional unit hypercube. These are the points in n for which every coordinate is either a 0 or a 1. Now inflate each of these small spheres at the same time until they touch. Each sphere will have radius 1/2. For example, the spheres centered at [...]The post Sphere spilling out first appeared on John D. Cook.

Imagine in a game of Rock, Paper, Scissors one player is free to play as usual but the other is required to choose each option the same number of times. That is, in 3n rounds of the game, the disadvantaged player much choose Rock n times, Paper n times, and Scissors n times. Obviously the [...]The post A variation on Rock, Paper, Scissors first appeared on John D. Cook.

The previous post looked at the probability that a random n by n matrix over a finite field of order q is invertible. This works out to be This function of q and n comes up in other contexts as well and has a name that we will get to shortly. Pochhammer symbols Leo August [...]The post q-analog of rising powers first appeared on John D. Cook.

If you haven equations in n unknowns over a finite field with q elements, how likely is it that the system of equations has a solution? The number of possible n * n matrices with entries from a field of size q is qn^2. The set of invertible n * n matrices over a field [...]The post Solvability of linear systems over finite fields first appeared on John D. Cook.

Most people implicitly assume medical tests are infallible. If they test positive for X, they assume they have X. Or if they test negative for X, they're confident they don't have X. Neither is necessarily true. Someone recently asked me why medical tests always have an error rate. It's a good question. A test is [...]The post Why do medical tests always have error rates? first appeared on John D. Cook.

Imagine parallel parking is available along the shoulder of a road, but no parking spaces are marked. The first person to park picks a spot on the shoulder at random. Then another car also chooses a spot along the shoulder at random, with the constraint that the second car can't overlap the first. This process [...]The post Renyi's parking constant first appeared on John D. Cook.

When we say that the planets in our solar system orbit the sun, not the earth, we mean that the motions of the planets is much simpler to describe from the vantage point of the sun. The sun is no more the center of the universe than the earth is. Describing the motion of the [...]The post Calculating when a planet will appear to move backwards first appeared on John D. Cook.

Suppose you make an x% improvement followed by a y% improvement. Together do they make an (x + y)% improvement? Maybe. The business principle of kaizen, based on the Japanese for improvement, is based on the assumption that incremental improvements accumulate. But quantifying how improvements accumulate takes some care. Add or multiply? Two successive [...]The post Do incremental improvements add, multiply, or something else? first appeared on John D. Cook.

I ran across the Clausen function the other day, and when I saw a plot of the function my first thought was that it looks sorta like a sawtooth wave. I wondered whether it also sounds like a sawtooth wave, and indeed it does. More on that shortly. The Clausen function can be defined in [...]The post The Clausen function first appeared on John D. Cook.

Suppose you're in a boring meeting and you start doodling. You draw a circle, and then you draw a triangle on the outside of that circle. Next you draw a circle through the vertices of the triangle, and draw a square outside that. Then you draw a circle through the vertices of the square, and [...]The post Limit of a doodle first appeared on John D. Cook.