John D. Cook

A palindrome is a word or sentence that remains the same when its characters are reversed. For example, the word “radar” is a palindrome, as is the sentence “Madam, I’m Adam.” I was thinking today about Morse code palindromes, sequences of Morse code that remain the same when reversed. This post will look at what […]The post Morse code palindromes first appeared on John D. Cook.

There is an apocryphal story that someone from the Manhattan Project asked a mathematician how to uniformly distribute 100 points on a sphere. The mathematician replied that it couldn’t be done, and the project leader thought the mathematician was being uncooperative. If this story is true, the mathematician’s response was correct but unhelpful. He took […]The post Spreading out points on a sphere first appeared on John D. Cook.

Monte Carlo integration, or “integration by darts,” is a general method for evaluating high-dimensional integrals. Unfortunately it’s slow. This motivated the search for methods that are like Monte Carlo integration but that converge faster. Quasi-Monte Carlo (QMC) methods use low discrepancy sequences that explore a space more efficiently than random samples. These sequences are deterministic […]The post Quasi-Monte Carlo integration: periodic and nonperiodic first appeared on John D. Cook.

Howard Aiken on the uses of computers, 1955: If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the basic logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence I have […]The post Differential Equations and Department Stores first appeared on John D. Cook.

A while back I wrote about a simple equation for the shape of an egg. That equation is useful for producing egg-like images, but it’s not based on extensive research into actual eggs. I recently ran across a more realistic, but also more complicated, equation for modeling the shape of real eggs [1]. The equation […]The post Empirical formula for the shape of an egg first appeared on John D. Cook.

I’ve started reading Paul Nahin’s new book “In Pursuit of ζ(3).” The actual title is “In Pursuit of Zeta-3.” I can understand why a publisher would go with such a title, but I assume most people who read this blog are not afraid of Greek letters. I’ve enjoyed reading several of Nahin’s books, so I […]The post Computing ζ(3) first appeared on John D. Cook.

The previous post looked at the multiplicative group of integers modulo a number of the form n = pq where p and q are prime. This post looks at general n. The multiplicative group mod n consists of the integers from 1 to n-1 that are relative prime to n. So the size of this group […]The post How small can a multiplicative group be? first appeared on John D. Cook.

One way of looking at RSA encryption, a way that generalizes to new methods, is that the method is based on group operations inside a group of unknown order, i.e. unknown to most people. Another way of putting it is that RSA encryption takes place in a group where everybody knows how to multiply but […]The post Encryption in groups of unknown order first appeared on John D. Cook.

I got an email from Fr. John Rickert today, and with his permission I’ll share part of it here. A sin of commission occurs when we do something we should not do. A system is consistent (or maybe I should say “sound”) if the results of proofs really are true. Gödel’s 2nd Incompleteness Theorem says […]The post Logic in moral terminology first appeared on John D. Cook.

Missing data throws a monkey wrench into otherwise elegant plans. Yesterday’s post on genetic sequence data illustrates this point. DNA sequences consist of four bases, but we need to make provision for storing a fifth value for unknowns. If you know there’s a base in a particular position, but you don’t know what its value […]The post Missing data first appeared on John D. Cook.

The home page for the OpenSSL project says OpenSSL is a robust, commercial-grade, and full-featured toolkit for the Transport Layer Security (TLS) and Secure Sockets Layer (SSL) protocols. It is also a general-purpose cryptography library. … If you’ve never heard of the project before, you would rightly suppose that OpenSSL implements SSL (and its successor […]The post Also a crypto library first appeared on John D. Cook.

There are special compression algorithms for genetic sequence data, but I was curious how well simply zipping a text file would work. I downloaded a 14 MB text file containing DNA sequence data from a fruit fly and compressed it as a zip file and as a 7z file. The result was about 3.5 MB, […]The post Naive compression of genetic data first appeared on John D. Cook.

FM radio transmits a signal by perturbing (modulating) the frequency of a carrier wave. If the carrier has frequency ω and the signal has frequency q, then the FM signal is cos(ωt + β cos(qt)). To understand the modulated signal, it’s useful to write it as a sum of simple sines and cosines with no […]The post FM signal approximation first appeared on John D. Cook.

Psychologists say that random rewards are more addictive than steady, predictable rewards. But I believe this only applies to relatively frequent feedback. If rewards are too infrequent, there’s no emotional connection between behavior and reward. The connection becomes more intellectual and less visceral as feedback becomes less frequent and less predictable. Nassim Taleb distinguishes between […]The post Black Swan Gratification first appeared on John D. Cook.

Old cryptography never dies. After a method is broken, its use declines, but never goes to zero. And when I say “broken,” I do not mean no longer recommended, but broken to the point of being trivial to decrypt. I recently ran across an anecdote from World War I showing this is nothing new. The […]The post Using cryptography broken 50 years ago first appeared on John D. Cook.

I generally despise emoji, but I reluctantly learned a few things about them this morning. My latest couple blog posts involved chess, and I sent out a couple tweets using chess symbols. Along the way I ran into a mystery: sometimes the black pawn is much larger than other chess symbols. I first noticed this […]The post Unicode and Emoji, or The Giant Pawn Mystery first appeared on John D. Cook.

The eight queens problem is to place eight queens on a chessboard so that no queen attacks another. Because queens are allowed to move any number of spaces horizontally, vertically, or diagonally, this means no queen can be on the same row, column, or diagonal as any other queen. For example, the following image gives […]The post Queens on a donut first appeared on John D. Cook.

I needed to make an image of a chessboard for the next blog post, and I’m not very good at image editing, so I make one using Excel. There are Unicode characters for chess pieces— white king is U+2654, etc.—and so you can make a chessboard out of (Unicode) text. ♔♕♖♗♘♙♚♛♜♝♞♟ I placed the character […]The post How to make a chessboard in Excel first appeared on John D. Cook.

I needed to know the frequencies of letters at the beginning of words for a project. The overall frequency of letters, wherever they appear in a word, is well known. Initial frequencies are not so common, so I did a little experiment. I downloaded the Canterbury Corpus and looked at the frequency of initial letters […]The post Initial letter frequency first appeared on John D. Cook.

Garrison Keillor’s fictional Lake Wobegon is a place “where all the children are above average.” Donald Knuth alluded to this in his exercise regarding “Lake Wobegon Dice,” a set of dice where the roll of each die is (probably) above average. Let A be a six-sided die with a 5 on one side and 3’s […]The post Lake Wobegon Dice first appeared on John D. Cook.

Index of coincidence is a statistic developed by William Friedman for use in cryptanalysis. It measures how unevenly symbols are distributed in a message. It’s a kind of signature that could be used, for example, to infer the language of a text, even if the text has been encrypted with a simple substitution cipher. It […]The post Index of coincidence first appeared on John D. Cook.

I was reading a book on orbital mechanics recently [1], and one of the things that stood out was the use of two variations on sine and cosine, functions the book denotes by S and C. Strictly speaking, the functions are defined to be the analytic continuation of the middle expressions to the full complex […]The post S and C functions first appeared on John D. Cook.

It’s simpler to search the web than to search software-specific documentation. You can just type your query into a search engine and not have to be bothered by the differences in offline documentation systems for different software. But there are a couple disadvantages. First, the result may not be that relevant. For example, maybe you […]The post Offline documentation first appeared on John D. Cook.

Carver Mead on engineering: Engineering isn’t something you study and learny, and memorize, and know where to look up. Engineering is understanding things all the way to the bottom, no matter what field they are called, and being able use that to build stuff and make it work. I edited the quote slightly. Mead was […]The post Engineering attitude first appeared on John D. Cook.

I was reading a book on computer algebra and ran across an interesting theorem about Carmichael numbers in the one of the exercises. I’ll present that theorem below, but first I’ll back up and say what a pseudoprime is and what a Carmichael number is. Fermat’s theorem If p is a prime number, then for […]The post Searching for pseudoprimes first appeared on John D. Cook.

I ran across an interesting footnote in Wolfram Koepf’s book Computer Algebra. Gosper’s algorithm [1] was probably the first algorithm which would not have been found without computer algebra. Gosper writes in his paper: “Without the support of MACSYMA and its developer, I could not have collected the experiences necessary to provoke the conjectures that […]The post Finding computer algebra algorithms with computer algebra first appeared on John D. Cook.

Problem statement Suppose you have a large number of points in 3D space and you want to find a sphere containing all the points. You’d like the sphere to be as small as possible, but you’re willing to accept a slightly larger sphere in exchange for simplicity or efficiency. False starts If you knew the […]The post Approximate minimal bounding sphere first appeared on John D. Cook.

The floor of a real number x, written ⌊x⌋, is the largest integer less than or equal to x. So, for example, ⌊π⌋ = 3 and ⌊-π⌋ = -4. The previous post applied the floor function to a complex number z. What does that mean? You can’t just say it’s the largest integer [1] less than z because the […]The post Complex floor and a surprising pattern first appeared on John D. Cook.

A recent post looked at an example from one of Michael Trott’s tomes. This post looks at another example from the same tome. Trott made a contour plot of the Gauss map over the complex plane. I copied his code (almost) and reproduced his plot. ContourPlot[ Abs[1/(x + I y) - Floor[1/(x + I y)]], […]The post Plotting the Gauss map first appeared on John D. Cook.

A few days ago I wrote about an analog of the Collatz conjecture for polynomials with coefficients mod m. When m = 2, the conjecture is true, but when m = 3 the conjecture is false. I wrote some Mathematica code on that post to work with polynomials as polynomials. Then a comment on that […]The post Collatz analog in C first appeared on John D. Cook.

The following 2D bifurcation diagram is famous. You’ve probably seen it elsewhere. If you have seen it, you probably know that it has something to do with chaos, iterated functions, fractals, and all that. If you’d like to read in more detail about what exactly the plot means, see this post. I was reading Michael […]The post 3D bifurcation diagram first appeared on John D. Cook.

Balaji Srinivasan asks in a Twitter thread why we’re not far more productive given the technology available. Here I collect the five possible explanations he mentions. The Great Distraction. All the productivity we gained has been frittered away on equal-and-opposite distractions like social media, games, etc. The Great Dissipation. The productivity has been dissipated on […]The post Where has all the productivity gone? first appeared on John D. Cook.

I learned this morning via a comment that Twitter supports alt text descriptions for images. I didn’t think that it did, and said that it didn’t, but someone kindly corrected me. When I post equations as images on this site, I always include the LaTeX source code in an alt tag. That way someone using […]The post Alt tags on tweet images first appeared on John D. Cook.

I was reading through Michael Trott’s Mathematica Guidebook for Programming and ran across the following plot. I find the image aesthetically interesting. I also find it interesting that the image is the phase portrait of a differential equation whose solution doesn’t look that interesting. That is, the plot of (x(t), x ‘(t)) is much more […]The post Nonlinear phase portrait first appeared on John D. Cook.

The Collatz conjecture, a.k.a. the 3n + 1 problem, a.k.a. the hailstone conjecture, asks whether the following sequence always terminates. Start with a positive integer n. If n is even, set n ← n /2. Otherwise n ← 3n + 1. If n = 1, stop. Otherwise go back to step 1. The Collatz conjecture […]The post Polynomial analog of the Collatz conjecture first appeared on John D. Cook.

This weekend I had to enter an alphabetic passcode on a numeric keypad. The keypad used the same letter-to-digit convention as a phone, but the letters were not printed on the keypad. That made me think about how much better the Major system is. I wondered what phone keypads would look like if they used […]The post Major memory system telephone keypad first appeared on John D. Cook.

The previous post ended by plotting the error in approximating exp(x) with (2+x)/(2 – x): The error is much larger on the right end than the left. That made me wonder what the error might look like in the complex plane. Does the slice along real axis exhibit the minimum and maximum error, or are […]The post Approximation error over unit disk first appeared on John D. Cook.

I was watching one of Brian Douglas’ videos on control theory (Discrete Control #5) and ran into a simple derivation of an approximation I presented earlier. Back in April I wrote several post on simple approximations for log, exp, etc. In this post I gave an approximation for the exponential function: The control theory video […]The post Simple derivation of exponential approximation first appeared on John D. Cook.

Converting text to all upper case or all lower case is a fairly common task. One way to convert text to upper case would be to use the tr utility to replace the letters a through z with the letters A through Z. For example, $ echo Now is the time | tr '[a-z]' '[A-Z]' […]The post Upper case, lower case, title case first appeared on John D. Cook.

NIST publication 800-90B, Recommendations for the Entropy Sources Used for Random Bit Generation, contains an interesting continued fraction. Define a function where is the incomplete gamma function. NIST 800-90B gives [1] a continued fraction implement F, but the continued fraction includes a parameter k for no apparent reason. NIST cites a paper that in turn […]The post Continued fraction from entropy source testing first appeared on John D. Cook.

Several people responded to my previous post asserting that screen readers would not be able to read text formatted via Unicode variants. Maybe some screen readers can’t handle this, but there’s no reason they couldn’t. Before I go any further, I’d like to repeat my disclaimer from the previous post: It’s a dirty hack, and […]The post Removing Unicode formatting first appeared on John D. Cook.

Twitter does not directly provide support for formatting text in bold, italic, etc. But it does support Unicode characters [1], and so a hack to get around the formatting limitation is to replace letters with Unicode variants. For example, you could tweet How to include bold or italic text in a tweet. I cheated in […]The post How to format text in Twitter first appeared on John D. Cook.

The Lotka-Volterra equations are a system of nonlinear differential equations for modeling a predator-prey ecosystem. After a suitable change of units the equations can be written in the form where ab = 1. Here x(t) is the population of prey at time t and y(t) is the population of predators. For example, maybe x represents rabbits […]The post Predator-Prey period first appeared on John D. Cook.

Yesterday I wrote about rates of convergence for natural cubic splines. This brief post reports similar results for more boundary conditions. As explained in the earlier post, a cubic spline that interpolates a function f at n+1 points satisfies 4n -2 equations in 4n variables. Two more equations are necessary to uniquely determine the interpolating […]The post Error estimates for splines with more boundary conditions first appeared on John D. Cook.

A theorem by Paley and Wiener says that a Fourier series with random coefficients produces Brownian motion on [0, 2π]. Specifically, produces Brownian motion on [0, 2π]. Here the Zs are standard normal (Gaussian) random variables. Here is a plot of 10 instances of this process. Here’s the Python code that produced the plots. import […]The post Random Fourier series first appeared on John D. Cook.

Suppose you want to approximate a function with a polynomial by interpolating it at evenly spaced points. You might reasonably expect that the more points you use, the better the approximation will be. That might be true, but it might not. As explained here, for some functions the maximum approximation error actually increases as the […]The post Rate of natural cubic spline convergence first appeared on John D. Cook.

Yesterday I wrote about how to interpolate a Brownian path. If you’ve created a discrete Brownian path with a certain step size, you can go back and fill in at smaller steps as if you’d generated the values from the beginning. This means that instead of generating samples in order as a random walk, you […]The post The fractal nature of Brownian motion first appeared on John D. Cook.

Accuracy isn’t everything. Sometimes when you’re approximating a function you care more about matching a function’s qualitative behavior than matching its numerical values. One example is interpolating monotonic data. Say your data show that increasing input always increases output. It’s likely you want a function that interpolates your data to have the same property and […]The post Monotonic interpolation first appeared on John D. Cook.

Let W(t) be a standard Wiener process, a.k.a. a one-dimensional Brownian motion. We can produce a discrete realization of W by first setting W(0) = 0. Then let W(1) be a sample from a N(0, 1) random variable. Then let W(2) be W(1) plus another N(0, 1) sample. At each integer n > 0, W(n) […]The post Interpolating Brownian motion first appeared on John D. Cook.

Ran across a fun quote this afternoon: There are in this world optimists who feel that any symbol that starts off with an integral sign must necessarily denote something that will have every property that they should like an integral to possess. This of course is quite annoying to us rigorous mathematicians; what is even […]The post Anything that starts with an integral sign first appeared on John D. Cook.