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.

This post will venture further into abstract mathematics than most of my posts. If this isn't what you're looking for, you might try browsing here for more concrete articles. Incidentally, although I'm an applied mathematician, I also appreciate pure math. I imagine most applied mathematicians do as well. But what I do not appreciate is [...]The post Topological Abelian Groups first appeared on John D. Cook.

I was poking around Richard Stanley's site today and found the following problem on his miscellaneous page. Find a positive integer n < 10,000,000 such that the first four digits (in the decimal expansion) of n1,000,000 are all different. The problem should be solved in your head. The solution is not unique, but the solution [...]The post Millionth powers first appeared on John D. Cook.

One day Eric Temple Bell (1883-1960) was looking at the power series for the double exponential function, exp(exp(x)) and noticed a similarity to the power series for exp(x). You can find his account in [1]. He would have calculated the series by hand, but we have the advantage of software like Mathematica. We can get [...]The post Mr. Bell and Bell numbers first appeared on John D. Cook.

In this post we want to count the number of ways to divide a regular polygon [1] into triangles by connecting vertices with straight lines that do not cross. Squares For a square, there are two possibilities: we either connect the NW and SE corners, or we connect the SW and NE corners. Pentagons For [...]The post How many ways can you triangulate a regular polygon? first appeared on John D. Cook.

Last week I wrote about a hypothetical radio station that plays the top 100 songs in some genre, with songs being chosen randomly according to Zipf's law. Thenth most popular song is played with probability proportional to 1/n. This post is a variation on that post looking at text consisting of the the 1,000 most [...]The post 1000 most common words first appeared on John D. Cook.

As longtime readers of this blog have probably noticed, I like to poke around in Unicode occasionally. It's an endless system of rabbit holes to explore. This morning I was looking at the Miscellaneous Mathematical Symbols block. These are mostly obscure symbols, though I'm sure for each symbol that I think is obscure, there is [...]The post Miscellaneous mathematical symbols first appeared on John D. Cook.

If any field of mathematics has been thoroughly combed over, it's Euclidean geometry. But once in a while someone will come up with a new theorem that seems it should have been discovered centuries ago. Here's a theorem conjectured by Paul Erds in 1935 and proved by Louis Mordell later the same year. If from [...]The post Erds-Mordell triangle theorem first appeared on John D. Cook.

Here's a strange integral I ran across recently [1]. It's a little surprising that the integral even exists, and more surprising that its value has a simple expression. Here's a plot of the integrand. The plot doesn't do justice to all the activity on the left end. There are an infinite number of increasingly vertical [...]The post Logarithmic sawtooth first appeared on John D. Cook.

Eight years ago I wrote a blog post on the Leading digits of powers of 2. In that post I said that Benford's law gives remarkably good predictions for the distribution of leading digits of 2n. In this post I'll make that statement stronger. A sequence obeys Benford's law, in base 10, if the proportion [...]The post When Benford's law is exact first appeared on John D. Cook.

The exponential sum of the day page draws a new figure each day by plotting the partial sums of and drawing a line between consecutive terms. Herem,d, andy are the month, day, and last two digits of the year. Today's sum has an unusual number of lines that are parallel to the horizontal and vertical [...]The post Lots of flat sides first appeared on John D. Cook.

Suppose you want to hear the top 100 songs in some music genre, so you listen to a radio station that specializes in that kind of music. How long would it take to hear each of the songs at least once? This is a variation on the coupon collector problem. If a radio station plays [...]The post Top 100 radio first appeared on John D. Cook.

If you see a light moving in the sky, how could you tell whether it's an airplane or a satellite? If it is a satellite, could you tell how high of an orbit it's in? For an object in a circular orbit, v^2 = /r wherer is the orbit radius and is the standard [...]The post Estimating satellite altitude from apparent motion first appeared on John D. Cook.

The Korteweg-De Vries (KdV) equation is a nonlinear PDE used to model shallow water waves. The linear counterpart omits the nonlinear term in the middle. This variant is useful in itself, but also for understanding the nonlinear KdV equation. Solitons Solutions to the linear KdV equation spread out over time. The nonlinear term in the [...]The post Linear KdV dispersion first appeared on John D. Cook.

Differential equations, especially nonlinear differential equations, rarely have a closed-form solution, but sometimes it happens. As I wrote about a year ago It is unusual for a nonlinear PDE to have a closed-form solution, but it is not unheard of. There are numerous examples of nonlinear PDEs, equations with important physical applications, that have closed-form [...]The post Closed-form minimal surface solutions first appeared on John D. Cook.

The fundamental solution" to a PDE solves the equation with the right-hand side set to . Intuitively, you can think of the delta function as striking something with a hammer in order to see how it rings. An aside on rigor A novice might be OK with the explanation above. A sophomore might rightly object [...]The post Fundamental solution first appeared on John D. Cook.

The following quote stuck with me when I read it years ago. Looking back I appreciate it even more. Now, when solving differential equations, or indeed solving any problem, it is permissible to use any methods at all, no matter how dubious, provided that once the solution has been found it can be proved to [...]The post No matter how dubious first appeared on John D. Cook.

What to do first after scoping out and starting a data science project? I've started an unsupervised learning project based on textual data. The first thing I like to do is actually look at the data. Is it noisy? What are the features-complex feature engineering needed? How heterogeneous? What generalization and overfitting challenges? Analysis can [...]The post Looking at Your Data first appeared on John D. Cook.

An ellipse has equation and a hyperbola has equation Similarly the superellipse has equation and the superhyperbola When p = 2, the absolute value signs are unnecessary and the superellipse and superhyperbola reduce to the ellipse and hyperbola respectively. Increasingp makes the superellipse more like a rectangle. But unlike a rectangle with rounded corners, the [...]The post Superhyperbola first appeared on John D. Cook.

The glass disk game is played on a grid. You have translucent colored glass disks you can either place on an edge or a vertex. There are two kinds of disks that can be placed on an edge: blue or yellow. A vertex with a blue and yellow disk looks green. There are two kinds [...]The post The glass disk game first appeared on John D. Cook.

This post started out as a thread on X. Here I've edited it into a blog post. The image below and the fact cited can be found in JPL Publication 89-24. In 1960 it didn't seem that it would be possible to explore the solar system beyond Jupiter without greatly improved propulsion. Then the gravitational [...]The post Voyager's slingshot maneuvers first appeared on John D. Cook.

When Voyager 1 and 2 left Earth, their internal computers were programmed to use Golay error correction codes. Images transmitted from Jupiter and Saturn were encoded using Golay codes. After leaving Saturn, the software was upgraded to use Reed-Solomon error correction codes. I didn't realize how much difference the change of encoding made until I [...]The post Advantages of Reed-Solomon codes over Golay codes first appeared on John D. Cook.

The previous post mentioned that Martin Gardner announced that Ramanujan's conjecture that exp(163) in an integer had been proven. This was an April Fool's joke in 1975. Gardner said Working by hand, he [Ramanujan] found the value to be 262537412640768743.999999999999... The calculations were tedious, and he was unable to verify the next decimal digits. Calculating [...]The post Hand calculating exp(x) first appeared on John D. Cook.

Yesterday I ran across this approximation for and posted it on X. 3 log(640320) / 163 This approximation is good to 15 decimal places, and so the approximation is exact to within the limits of floating point arithmetic. I said in a follow up comment that the 163 term looked familiar from [...]The post Very accurate pi approximation first appeared on John D. Cook.

What is the interior of a circle? Obvious. What is the interior of a parabola? Not quite as obvious. What is the interior of a hyperbola? Not at all obvious. Is it possible to define interior in a way that applies to all conic sections? Circles If you remove a circle from the plane, there [...]The post Interior of a conic first appeared on John D. Cook.

Community best practices are useful for helping use a software product more effectively. I've just completed a small project using the Z3 solver. Here are some things I've learned: My project involves an optimization problem: for a subset of Boolean variables, maximize the count of how many are true. My specific problem is solved much [...]The post Lessons Learned With the Z3 SAT/SMT Solver first appeared on John D. Cook.

The last chord of the James Bond theme is known as the James Bond chord. If you've ever seen a Bond movie, you'll recognize it. Here's a quick video showing how to play it on guitar. I tried asking Grok 3 to generate some LilyPond code for sheet music a few days ago. LilyPond is [...]The post Grokking the James Bond chord first appeared on John D. Cook.

The last several posts have looked at counting two kinds of permutations: those that leave no consecutive integers and those that leave no integer fixed. As n grows large, the proportion of permutations ofn elements that fall into both classes approaches 1/e. This post will look a little closer and as how fast each proportion [...]The post Rates of convergence first appeared on John D. Cook.

Yesterday I wrote a couple of posts about a combinatorics question that lead to OEIS sequence A000255. That page has this intriguing line: This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010) I love how pulling on a thread [...]The post Gluons, quarks, letters, and envelopes first appeared on John D. Cook.

The previous post looked at how to compute Q(n), the number of permutations of1, 2, 3, ..., n + 1 that contain no consecutive integers. We found a way to numerically compute Q(n) but no analytic expression that would let us compute asymptotics. The sequence Q(n) is sequence A000255 in OEIS, and OEIS gives the [...]The post Example using a generating function to find asymptotic behavior first appeared on John D. Cook.

I was working on something this week that made me wonder how many permutations break up all consecutive elements. For example, if we're looking at permutations of abcde thenacebd counts, but acdbe does not. I'd like to count the number of such permutations, and estimate for large N the number of permutations ofN elements with [...]The post Permutations with no consecutive elements first appeared on John D. Cook.

The following equation, known as the BBP formula [1], will let you compute the nth digit of directly without having to compute the previous digits. I've seen this claim many times, but I've never seen it explained in much detail how this formula lets you extract digits of . First of all, this formula [...]The post Computing the nth digit of directly first appeared on John D. Cook.

Colossus The xAI Colossus supercomputer contains 100,000 NVIDIA H100 GPUs. Upgrades are planned, ultimately up to as much as a million GPUs. The H100 has theoretical peak speed of at least 60 teraFLOPs (FP64 tensor core), though the actual number depends on the power and frequency cap settings on the GPUs. Admittedly FP64 is overkill [...]The post Colossus versus El Capitan: A Tale of Two Supercomputers first appeared on John D. Cook.

When I'm in the mood to write, you can often follow a chain of though in my posts. Recently, a post on LLM tokenization lead to a post on how Unicode characters are tokenized, which led to a post on Unicode surrogates. The latter ended by touching on Unicode's PUA (Private Use Area), which of [...]The post Unicode, Tolkien, and Privacy first appeared on John D. Cook.

At the highest level, Unicode is a simply a list of symbols. But when you look closer you find that isn't entirely true. Some of the symbols are sorta meta symbols. And while a list of symbols is not complicated, this list is adjacent to a lot of complexity. I've explored various rabbit holes of [...]The post Unicode surrogates first appeared on John D. Cook.

I recently ran across the article Something weird is happening with LLMs and chess. One of the things it mentions is how the a minor variation in a prompt can have a large impact on the ability of an LLM to play chess. One extremely strange thing I noticed was that if I gave a [...]The post Practical consequences of tokenization details first appeared on John D. Cook.

I mentioned in the previous post that not every Unicode character corresponds to a token in ChatGPT. Specifically I'm looking at gpt-3.5-turbo in tiktoken. There are 100,256 possible tokens and 155,063 Unicode characters, so the pigeon hole principle says not every character corresponds to a token. I was curious about the relationship between tokens and [...]The post ChatGPT tokens and Unicode first appeared on John D. Cook.

Large language models operate on tokens, not words, though tokens roughly correspond to words. A list of words would not be practical. There is no definitive list of all English words, much less all words in all languages. Still, tokens correspond roughly to words, while being more flexible. Words are typically turned into tokens using [...]The post The difference between tokens and words first appeared on John D. Cook.

The GELU (Gaussian Error Linear Units) activation function was proposed in [1]. This function is x (x) where is the CDF of a standard normal random variable. As you might guess, the motivation for the function involves probability. See [1] for details. The GELU function is not too far from the more familiar ReLU, [...]The post A simpler GELU activation function approximation first appeared on John D. Cook.

A common technique for memorizing numbers is to associate numbers with words. The Major mnemonic system does this by associating consonant sounds with each digit. You form words by inserting vowels as you please. There are many possible encodings of numbers, but sometimes you want to pick a canonical word for each number, what's commonly [...]The post Spreading out words in space first appeared on John D. Cook.