John D. Cook

In my previous post I illustrated the Levenshtein edit distance by comparing the opening paragraphs of Finnegans Wake by James Joyce and a parody by Adam Roberts. In this post I’ll show how to align two sequences using the sequence alignment algorithms of Needleman-Wunsch and Hirschberg. These algorithms can be used to compare any sequences, though they […]

I ran into a delightfully strange blog post today called Finnegans Ewok that edits the first few paragraphs of Finnegans Wake to make it into something like Return of the Jedi. The author, Adam Roberts, said via Twitter “What I found interesting here was how little I had to change Joyce’s original text. Tweak a couple […]

Differential privacy, specifically ε-differential privacy, gives strong privacy guarantees, but it can be overly cautious by focusing on worst-case scenarios. The generalization (ε, δ)-differential privacy was introduced to make ε-differential privacy more flexible. Rényi differential privacy (RDP) is a new generalization of ε-differential privacy by Ilya Mironov that is comparable to the (ε, δ) version but has several […]

The most common way of measuring information is Shannon entropy, but there are others. Rényi entropy, developed by Hungarian mathematician Alfréd Rényi, generalizes Shannon entropy and includes other entropy measures as special cases. Rényi entropy of order α If a discrete random variable X has n possible values, where the ith outcome has probability pi, then the Rényi entropy […]

Curry-Howard-Lambek is a set of correspondences between logic, programming, and category theory. You may have heard of the slogan proofs-as-programs or propositions-as-types. These refer to the Curry-Howard correspondence between mathematical proofs and programs. Lambek’s name is appended to the Curry-Howard correspondence to represent connections to category theory. The term Curry-Howard isomorphism is often used but is an overstatement. Logic […]

Scott Hanselman interviewed attorney Gary Nissenbaum in show #647 of Hanselminutes. The title was “How GDPR is effecting the American Legal System.” Can Europe pass laws constraining American citizens? Didn’t we settle that question in 1776, or at least by 1783? And yet it is inevitable that European law effects Americans. And in fact Nissembaum […]

Let p be a prime. If the repeating decimal for the fraction a/p has even period, the the second half of the decimals are the 9’s complement of the first half. This is known as Midy’s theorem. For a small example, take 1/7 = 0.142857142857… and notice that 142 + 857 = 999. That is, 8, 5, […]

The General Conference on Weights and Measures voted today to redefine the kilogram. The official definition no longer refers to the mass of the International Prototype of the Kilogram (IPK) stored at the BIPM (Bureau International des Poids et Measures) in France. The Coulomb, kelvin, and mole have also been redefined. The vote took place today, 2018-11-16, and […]

Deep learning has spurred interest in novel floating point formats. Algorithms often don’t need as much precision as standard IEEE-754 doubles or even single precision floats. Lower precision makes it possible to hold more numbers in memory, reducing the time spent swapping numbers in and out of memory. Also, low-precision circuits are far less complex. […]

One of my most popular posts on Twitter was an implicit criticism of the cliché “work smarter, not harder.” Productivity tip: Work hard. — John D. Cook (@JohnDCook) October 8, 2015 I agree with the idea that you can often be more productive by stepping back and thinking about what you’re doing. I’ve written before, […]

Last week Bujanda et al published a paper [1] that gives new expansions for the confluent hypergeometric function. I’ll back up explain what that means before saying more about the new paper. Hypergeometric functions Hypergeometric functions are something of a “grand unified theory” of special functions. Many functions that come up in application are special […]

How does big data impact privacy? Which is a bigger risk to your privacy, being part of a little database or a big database? Rows vs Columns People commonly speak of big data in terms of volume—the “four v’s” of big data being volume, variety, velocity, and veracity—but what we’re concerned with here might better be […]

The idea of proof of work (PoW) was first explained in a paper Cynthia Dwork and Moni Naor [1], though the term “proof of work” came later [2]. It was first proposed as a way to deter spam, but it’s better known these days through its association with cryptocurrency. If it cost more to send […]

The Hagia Sophia (Greek for “Holy Wisdom”) was a Greek Orthodox cathedral from 537 to 1453. When the Ottoman Empire conquered Constantinople the church was converted into a mosque. Then in 1935 it was converted into a museum. No musical performances are allowed in the Hagia Sophia. However, researchers from Stanford have modeled the acoustics […]

There are several things in math and statistics named gamma. Three examples are the gamma function the gamma constant the gamma distribution This post will show how these are related. We’ll also look at the incomplete gamma function which connects with all the above. The gamma function The gamma function is the most important function […]

In 1999, Harvard law professor Lawrence Lessig stated that software is a kind of law. The algorithms of tech giants have an influence comparable to, and maybe in some ways greater than, statutory law. The code is law. … Activists concerned with defending liberty, privacy or access must watch the code coming from the Valley—call […]

Differential privacy is a strong form of privacy protection with a solid mathematical definition. Roughly speaking, a query is differentially private if it makes little difference whether your information is included or not. This intuitive idea can be made precise as follows. Queries and algorithms First of a differential privacy is something that applies to queries, […]

I stopped posting to the @FormalFact Twitter account last July, but I didn’t deactivate the account. Now I’m going to restart it. Unlike my other Twitter accounts, I don’t plan to have a regular posting schedule. I may not post often. We’ll see how it goes. I’ve changed the account name from @FormalFact to @LogicPractice. The […]

Every rational number can be expanded into a continued fraction with positive integer coefficients. And the process can be reversed: given a sequence of positive integers, you can make them the coefficients in a continued fraction and reduce it to a simple fraction. In 1954, Arthur Porges published a one-page article pointing out that continued fractions […]

There’s an old saying that if you want to hide a tree, put it in a forest. An analogous principle in privacy is that a record preserves privacy if it’s like a lot of other records. k-anonymity The idea of k-anonymity is that every database record appears at least k times when you restrict your attention to […]

Since integration is the inverse of differentiation, you can think of integration as “dividing” by d. J. P. Ballantine [1] shows that you can formally divide by d and get the correct integral. For example, he arrives at using long division! [1] J. P. Ballantine. Integration by Long Division. The American Mathematical Monthly, Vol. 58, […]

A few weeks ago I wrote about how there are many ways to summarize the operating characteristics of a test. The most basic terms are accuracy, precision, and recall, but there are many others. Nobody uses all of them. Each application area has their own jargon. Biometric security has its own lingo, and it doesn’t […]

In the previous post, I mentioned that modal logic has a lot of interpretations and a lot of axiom systems. It can also have a lot of operators. This post will look at Security Logic, a modal logic for security applications based on a seminal paper by Glasgow et al [1]. It illustrates how modal and […]

Modal logic extends propositional logic with two new operators, □ (“box”) and ◇ (“diamond”). There are many interpretations of these two symbols, the most common being necessity and possibility respectively. That is, □p means the proposition p is necessary, and ◇p means that p is possible. Another interpretation is using the symbols to represent things a person knows to […]

Many encryption algorithms rely on the difficulty of factoring a large number n. If you want to make n hard to factor, you want it to have only two factors. Otherwise, the more factors n has, the smaller the smallest factor must be. So if you want n to be the product of two large primes, p and q, you want […]

“There is no point in being precise when you don’t know what you’re talking about.” — John Tukey It’s a familiar trope in science fiction that the smartest character will answer questions with excess precision. On Star Trek, Scottie might give a number to one significant figure and Spock will correct him giving the same […]

The idea of format-preserving encryption is to encrypt data while keeping its form, a sort of encryption in kind. An encrypted credit card number would look like a credit card number, a string of text would be replaced with a string of text, etc. Format preserving encryption (FPE) is useful in creating a test or demo […]

I’ve mentioned a couple times that Jacobi elliptic functions are generalizations of sines and cosines. In an earlier post I showed how you can make sn and cn from sine and cosine by a nonlinear rescaling of the input. In this post I’ll look at a linear scaling of the input and a sum of sines or […]

In 1956, Thornton Fry wrote an article entitled “Mathematics as a Profession Today in Industry” [1]. The number of mathematicians working in industry had increased dramatically in the preceding few years, and Fry speculated on what the future might hold. I expected the article might have a few amusing predictions, extrapolations from things that seemed […]

The US government does not prohibit the transfer of PHI (protected health information) offshore [1], but it does subject offshore data processing to extra reporting [2] and more scrutiny in general. The CMS (Centers for Medicare & Medicaid Services, part of the Department of Health and Human Services) has said Given the unique risks associated with […]

It’s much easier to convert meters to kilometers than to convert yards to miles. You know what’s even easier? Not converting meters to kilometers! You only need one unit of length, say a meter. You could express all distances in terms of meters and dispense with kilometers, millimeters, etc. And in fact, this is essentially […]

The US uses a mix of imperial and metric units of measure. Some people, almost all outside the US, are quite agitated by this. In practice, the two systems coexist peacefully. Americans buy milk by the gallon and wine by the milliliter. Milk typically comes in gallon jugs, and wine typically comes in 750 milliliter […]

For every integer m > 1, it’s possible to choose N so that the proportion of primes in the sequence 1, 2, 3, … N is 1/m. To put it another way, you can make the odds against one of the first N natural numbers being prime any integer value you’d like [1]. For example, suppose you wanted […]

There are only three posts on this top 10 list that are also on the top 10 list for Hacker News. Why programmers are not paid in proportion to productivity Selection bias and bombers Automate to save mental energy, not time The most important skill in software development Golden powers are nearly integers Ten life […]

My previous post looked at Jacobi functions from a reference perspective: given a Jacobi function defined one way, how do I relate that to the same function defined another way, and how would you compute it? This post explores the analogy between trigonometric functions and Jacobi elliptic functions. Related basic Jacobi functions to trig functions […]

The Jacobi elliptic functions sn and cn are analogous to the trigonometric functions sine and cosine. The come up in applications such as nonlinear oscillations and conformal mapping. Unfortunately there are multiple conventions for defining these functions. The purpose of this post is to clear up the confusion around these different conventions. The image above is […]

The first time you see matrices, if someone asked you how you multiply two matrices together, your first idea might be to multiply every element of the first matrix by the element in the same position of the corresponding matrix, analogous to the way you add matrices. But that’s not usually how we multiply matrices. […]

Suppose you have a number that you believe to be prime. You start reading your number aloud, and someone interrupts “Stop right there! No prime starts with the digits you’ve read so far.” It turns out the person interrupting you shouldn’t be so sure. There are no restrictions on the digits a prime number can […]

Suppose you have two baseball teams, A and B, playing in the World Series. If you like, say A stands for Houston Astros and B for Milwaukee Brewers. Suppose that in each game the probability that A wins is p, and the probability of A losing is q = 1 – p. What is the probability that A will win the series? […]

You can find a large collection of physical constants in scipy.constants. The most frequently used constants are available directly, and hundreds more are in a dictionary physical_constants. The fine structure constant α is defined as a function of other physical constants: The following code shows that the fine structure constant and the other constants that […]

As you read this blog post, you probably have a hierarchy of contexts in the back of your mind. It comes so naturally to you that you don’t consciously think of it. If you’re reading this in a web browser, you probably know what browser you’re using. If not, you’re at least aware that you […]

For each prime p, there is only one group with p elements, the cyclic group with that many elements. It would be plausible to think there is only one group of order n if and only if n is prime, but this isn’t the case. If p and q are primes, then there are ostensibly at least two groups of order pq: […]

Sturm’s separation theorem says that the zeros of independent solutions to an equation of the form alternate. That is, between any two consecutive zeros of one solution, there is exactly one zero of the other solution. This is an important theorem because a lot of differential equations of this form come up in applications. If […]

Here’s today’s exponential sum, 10/1/2018: And here’s what it would look like if September had 31 days, 9/31/2018:

Last evening my electricity went out and this morning it was restored. This got met thinking about systems that fail occasionally [1]. Electricity goes out often enough that we prepare for it. We have candles and flashlights, my work computer is on a UPS, etc. A residential power outage is usually just an inconvenience, especially […]

If you know the vertices of a polygon, how do you compute its area? This seems like this could be a complicated, with special cases for whether the polygon is convex or maybe other considerations. But as long as the polygon is “simple,” i.e. the sides meet at vertices but otherwise do not intersect each […]

According to this paper [1], the empirical distribution of real passwords follows a power law [2]. In the authors’ terms, a Zipf-like distribution. The frequency of the rth most common password is proportional to something like 1/r. More precisely, fr = C r–s where s is on the order of 1. The value of s that […]

C. A. R. Hoare wrote an article How Did Software Get So Reliable Without Proof? in 1996 that still sounds contemporary for the most part. In the 1980’s many believed that programs could not get much bigger unless we started using formal proof methods. The argument was that bugs are fairly common, and that each bug has […]

This morning Sir Michael Atiyah gave a presentation at the Heidelberg Laureate Forum with a claimed proof of the Riemann hypothesis. The Riemann hypothesis (RH) is the most famous open problem in mathematics, and yet Atiyah claims to have a simple proof. Simple proofs of famous conjectures If anyone else claimed a simple proof of […]

Fermat’s little theorem says that if p is a prime and a is not a multiple of p, then ap-1 = 1 (mod p). Euler’s generalization of Fermat’s little theorem says that if a is relatively prime to m, then aφ(m) = 1 (mod m) where φ(m) is Euler’s so-called totient function. This function counts the number of positive […]