John D. Cook

How can you possibly solve a mission-critical problem with millions of variables-when the worst-case computational complexity of every known algorithm for that problem is exponential in the number of variables? SAT (Satisfiability) solvers have seen dramatic orders-of-magnitude performance gains for many problems through algorithmic improvements over the last couple of decades or so. The SAT [...]The post Getting some (algorithmic) SAT-isfaction first appeared on John D. Cook.

In the previous post I mentioned that the general strategy for computing a mathematical function using tables is to first reduce the function argument to be within the range of the tabulated values, and then to use interpolation to compute the function at values that are not directly tabulated. The second step is always the [...]The post Computing (z) for complex z with tables first appeared on John D. Cook.

It takes some skill to use tables of mathematical functions; it's not quite as simple as it may seem. Although it's no longer necessary to use tables, it's interesting to look into the details of how it is done. For example, the Handbook of Mathematical Functions edited by Abramowitz and Stegun tabulates sines and cosines [...]The post Calculating trig functions from tables first appeared on John D. Cook.

The previous post looked at two simple approximations for the perimeter of an ellipse. Approximations are necessary since the perimeter of an ellipse cannot be expressed as an elementary function of the axes. Kepler noted in 1609 that you could approximate the perimeter of an ellipse as the perimeter of a circle whose radius is [...]The post Rapidly convergent series for ellipse perimeter first appeared on John D. Cook.

In 1609, Kepler remarked that the perimeter of an ellipse with semiaxes a and b could be approximated either as P 2(ab) or P (a + b). In other words, you can approximate the perimeter of an ellipse by the circumference of a circle of radius r where r is either the geometric mean [...]The post Kepler's ellipse perimeter approximations first appeared on John D. Cook.

A few days ago I wrote about eigenvector centrality, a way of computing which nodes in a network are most important. Rather than simply looking for the most highly connected nodes, it looks for nodes that are highly connected to nodes that are highly connected. It's the idea behind Google's PageRank algorithm. Adjacency matrices One [...]The post Power method and centrality first appeared on John D. Cook.

Anyone with more than casual experience with ChatGPT knows that prompt engineering is a thing. Minor or even trivial changes in a chatbot prompt can have significant effects, sometimes even dramatic ones, on the output [1]. For simple requests it may not make much difference, but for detailed requests it could matter a lot. Industry [...]The post The search for the perfect prompt first appeared on John D. Cook.

A basic question to ask about a network is which nodes are most important. A simple way of answering this question would be to say the most well-connected nodes, i.e. the nodes with the most edges. This approach is known as degree centrality. It's not a bad place to start. It's easy to understand and [...]The post Eigenvector centrality first appeared on John D. Cook.

The other day I was looking at how many lumens LED lights put out per watt. I found some data on Wikipedia, and as you might expect the relation between watts and lumens is basically linear, though not quite. If you were to do a linear regression on the data you'd get a relation lumens [...]The post Fitting a line without an intercept term first appeared on John D. Cook.

I read something recently that said in passing that the solutions to the equation tan x = x are the zeros of the Bessel function J3/2. That brought two questions to mind. First, where have I seen the equation tan x = x before? And second, why should its solutions be the roots of a [...]The post Solutions to tan(x) = x first appeared on John D. Cook.

The previous post showed how to compute logarithms using tables. It gives an example of calculating a logarithm to 15 figures precision using tables that only allow 4 figures of precision for inputs. Not only can you bootstrap tables to calculate logarithms of real numbers not given in the tables, you can also bootstrap a [...]The post Computing logarithms of complex numbers first appeared on John D. Cook.

My favorite quote from Richard Feynman is his remark that nearly everything is really interesting if you go into it deeply enough." This post will look at something that seems utterly trivial-looking up numbers in a table-and show that there's much more to it when you dig a little deeper. More than just looking up [...]The post Using a table of logarithms first appeared on John D. Cook.

Excerpt from from John Carmack's review of the book Bullshit Jobs. He talks about how software developers bemoan duct taping systems together, and would rather work on core technologies. He thinks it is some tragic failure, that if only wise system design was employed, you wouldn't be doing all the duct taping. Wrong. Every expansion [...]The post Duct tape value creation first appeared on John D. Cook.

Suppose you design an experiment, an A/B test of two page designs, randomizing visitors to Design A or Design B. You planned to run the test for 800 visitors and you calculated some confidence level for your experiment. You decide to take a peek at the data after only 300 randomizations, even though your [...]The post Condition on your data first appeared on John D. Cook.

Suppose you're running an A/B test to determine whether a web page produces more sales with one graphic versus another. You plan to randomly assign image A or B to 1,000 visitors to the page, but after only randomizing 500 visitors you want to look at the data. Is this OK or not? Of course [...]The post Can you look at experimental results along the way or not? first appeared on John D. Cook.

In LaTeX, sections are labeled with commands like \label{foo} and referenced like \ref{foo}. Referring to sections by labels rather than hard-coded numbers allows references to automatically update when sections are inserted, deleted, or rearranged. For every reference there ought to be a label. A label without a corresponding reference is fine, though it might be [...]The post One-liner to troubleshoot LaTeX references first appeared on John D. Cook.

I was reading an article [1] that refers to a well-known trigonometric series" that I'd never seen before. This paper cites [2] which gives the series as Note that the right hand side is not a series in but rather in sin . Motivation Why might you know sin and want to calculate [...]The post A well-known" series first appeared on John D. Cook.

Probability and cryptography have this in common: really smart people can be confidently wrong about both. I wrote years ago about how striking it was to see two senior professors arguing over an undergraduate probability exercise. As I commented in that post, Professors might forget how to do a calculus problem, or make a mistake [...]The post Probability, cryptography, and naivete first appeared on John D. Cook.

Richard Feynman's Nobel Prize winning discoveries in quantum electrodynamics were partly inspired by his randomly observing a spinning dinner plate one day in the cafeteria. Paul Feyerabend said regarding science discovery, The only principle that does not inhibit progress is: anything goes" (within relevant ethical constraints, of course). Ideas can come from anywhere, including physical [...]The post Thinking by playing around first appeared on John D. Cook.

The well-known Weierstrass approximation theorem says that polynomials are dense in C[0, 1]. That is, given any continuous function f on the unit interval, and any > 0, you can find a polynomial P such that f and P are never more than apart. This means that linear combinations of the polynomials 1, [...]The post Approximation by prime powers first appeared on John D. Cook.

I've written before about three simple approximations for logarithms, for base 10 log10(x) (x - 1)/(x + 1) base e, loge(x) 2(x - 1)/(x + 1) and base 2 log2(x) 3(x - 1)/(x + 1). These can be used to mentally approximate logarithms to moderate accuracy, accurate enough for quick estimates. Here's [...]The post Logarithm approximation curiosity first appeared on John D. Cook.

A Mersenne number is a number of the form 2k - 1. A Mersenne prime is a Mersenne number which is also a prime. It turns out that if 2k - 1 is prime then k must be prime, so Mersenne numbers have the form 2p - 1 is prime. What about the converse? If [...]The post Iterated Mersenne primes first appeared on John D. Cook.

A video has been making the rounds in which a well-known professor [1] says that if something has a 20% probability of happening in one attempt, then it has a 40% chance of happening in two attempts, a 60% chance in happening in three attempts, etc. This is wrong, but it's a common mistake. And [...]The post Small probabilities add, big ones don't first appeared on John D. Cook.

This post is a series of quick thoughts related to logistic regression. It starts with this article on moving between logit and probability scales. *** Logistic regression models the probability of a yes/no event occurring. It gives you more information than a model that simply tries to classify yeses and nos. I advised a client [...]The post Logistic regression quick takes first appeared on John D. Cook.

Suppose you'd like to evaluate the function for small values of z, say z = 10-8. This example comes from [1]. The Python code from numpy import exp def f(z): return (exp(z) - 1 - z)/z**2 print(f(1e-8)) prints -0.607747099184471. Now suppose you suspect numerical difficulties and compute your result to 50 decimal places using bc [...]The post Numerical application of mean value theorem first appeared on John D. Cook.

The most obvious way to approximate the derivative of a function numerically is to use the definition of derivative and stick in a small value of the step size h. f'(x) ( f(x + h) - f(x) ) / h. How small should h be? Since the exact value of the derivative is the [...]The post Numerical differentiation with a complex step first appeared on John D. Cook.

Bob Carpenter wrote today about how Markov chains cannot thoroughly cover high-dimensional spaces, and that they do not need to. That's kinda the point of Monte Carlo integration. If you want systematic coverage, you can/must sample systematically, and that's impractical in high dimensions. Bob gives the example that if you want to get one integration [...]The post MCMC and the coupon collector problem first appeared on John D. Cook.

It's easier to go up a ladder than to come down, literally and metaphorically. Gian-Carlo Rota made a profound observation on the application of theory. One frequently notices, however, a wide gap between the bare statement of a principle and the skill required in recognizing that it applies to a particular problem. This isn't quite [...]The post Up and down the abstraction ladder first appeared on John D. Cook.

I learned to use the command line utility make in the context of building C programs. The program make reads an input file to tell it how to make things. To make a C program, you compile the source files into object files, then link the object files together. You can tell make what depends [...]The post Making documents with makefiles first appeared on John D. Cook.

Good general theory does not search for the maximum generality, but for the right generality." - Saunders Mac Lane One of the benefits of a scripting language like Python is that it gives you generalizations for free. For example, take the function sorted. If you give it a list of integers, it will return [...]The post Applied abstraction first appeared on John D. Cook.

One time when I was in grad school, I was a teaching assistant for a business math class that included calculus and a smattering of other topics, including a little bit of probability. I made up examples involving a deck of cards, but then learned to my surprise that not everyone was familiar with playing [...]The post A deck of cards first appeared on John D. Cook.

The other day I ran across this photo of Saturn's moon Titan taken by the James Webb Space Telescope (JWST). If JWST can see Titan with this kind of resolution, how well could it see Pluto or other planets? In this post I'll do some back-of-the-envelope calculations, only considering the apparent size of objects, ignoring [...]The post What can JWST see? first appeared on John D. Cook.

I ran across a graphic yesterday made by taking a sequence of steps of the same length, turning left on the nth step if n is prime, and otherwise continuing in the same direction. Here's my recreation of the first 1000 steps: You can see that in general it makes a lot of turns at [...]The post Fizz buzz walk first appeared on John D. Cook.

The traditional approach to teaching differential equations is to present a collection of techniques for finding closed-form solutions to ordinary differential equations (ODEs). These techniques seem completely unrelated [1] and have arcane names such as integrating factors, exact equations, variation of parameters, etc. Students may reasonably come away from an introductory course with the false [...]The post Closed-form solutions to nonlinear PDEs first appeared on John D. Cook.

Julia. Scala. Lua. TypeScript. Haskell. Go. Dart. Various computer languages new and old are sometimes proposed as better alternatives to mainstream languages. But compared to mainstream choices like Python, C, C++ and Java (cf. Tiobe Index)-are they worth using? Certainly it depends a lot on the planned use: is it a one-off small project, or [...]The post Choosing a Computer Language for a Project first appeared on John D. Cook.

This weekend I ran across a blog post The Rodeo Clown Theory of Personal Development. The title comes from a hypothetical example of a goal you don't know how to achieve: becoming a rodeo clown. Let's say you decide you want to be a rodeo clown. And let's say you're me and you have no [...]The post On greedy algorithms and rodeo clowns first appeared on John D. Cook.

There's a little program called strings that searches for what appear to be strings inside binary file. I'll refer to it as strings(1) to distinguish the program name from the common English word strings. [1] What does strings(1) consider to be a string? By default it is a sequence of four or more bytes that [...]The post Finding strings in binary files first appeared on John D. Cook.

Arshad Khan left a comment on my post on the less and more utilities saying on ubuntu if I do less on a pdf file, it shows me the text contents of the pdf." Apparently this is an undocumented feature of GNU less. It works, but I don't see anything about it in the man [...]The post Extract text from a PDF first appeared on John D. Cook.

This post ties together the previous three posts. In this post, I said that an Archimedean spiral has the polar equation r = b 1/n and applied this here to rolls of carpet. When n = 1, the length of the spiral for running from 0 to T is approximately bT^2 with the [...]The post Length of a general Archimedean spiral first appeared on John D. Cook.

If you know the dimensions of a carpet, what will the dimensions be when you roll it up into a cylinder? If you know the dimensions of a rolled-up carpet, what will the dimensions be when you unroll it? This post answers both questions. Flexible carpet: solid cylinder The edge of a rolled-up carpet can [...]The post How big will a carpet be when you roll or unroll it? first appeared on John D. Cook.

An Archimedean spiral has the polar equation r = b 1/n This post will look at the case n = 1. I may look at more general values of n in a future post. (Update: See here.) The case n = 1 is the simplest case, and it's the case I needed for the client [...]The post Approximating a spiral by rings first appeared on John D. Cook.

It's occasionally necessary to evaluate a hypergeometric function at a large negative argument. I was working on a project today that involved evaluating F(a, b; c; z) where z is a large negative number. The hypergeometric function F(a, b; c; z) is defined by a power series in z whose coefficients are functions of a, [...]The post Hypergeometric function of a large negative argument first appeared on John D. Cook.

When I first started using Unix, I used a program called more" to read files. The name makes sense because each time you press the space bar, more will show you more of your file, one screen at a time. Now everyone uses less, and more is all but forgotten. Daniel Halbert wrote more in [...]The post More is less first appeared on John D. Cook.

I recently ran across a tweet from Allen Downey saying So much of 20th century statistics was just a waste of time, computing precise answers to useless questions. He's right. I taught mathematical statistics at GSBS [1, 2] several times, and each time I taught it I became more aware of how pointless some of [...]The post Precise answers to useless questions first appeared on John D. Cook.

An article by Y. L. Cheung [1] gives reasons why poker is usually played with five cards. The author gives several reasons, but here I'll just look at one reason: pairs don't act like you might expect if you have more than five cards. In five-card poker, the more pairs the better. Better here means [...]The post Pairs in poker first appeared on John D. Cook.

Yesterday I stumbled on the fact that the size of Jupiter is roughly the geometric mean between the sizes of Earth and the Sun. That's not too surprising: in some sense (i.e. on a logarithmic scale) Jupiter is the middle sized object in our solar system. What I find more surprising is that a systematic [...]The post Solar system means first appeared on John D. Cook.

The size of Jupiter is approximately the geometric mean of the sizes of Sun and Earth. In terms of radii, The ratio on the left equals 9.95 and the ratio on the left equals 10.98. The subscripts are the astronomical symbols for the Sun (, U+2609), Jupiter (, U+2643), and Earth (, U+1F728). I produced [...]The post Earth : Jupiter :: Jupiter : Sun first appeared on John D. Cook.

I was listening to the latest episode of the Space Rocket History podcast. The show includes some audio from a documentary on Pioneer 11 that mentioned that a man would weigh 500 pounds on Jupiter. My immediate thought was Is that all?! Is this man' a 100 pound boy?" The documentary was correct and my [...]The post Gravity on Jupiter first appeared on John D. Cook.

Are guidance documents laws? No, but they can have legal significance. The people who generate regulatory guidance documents are not legislators. Legislators delegate to agencies to make rules, and agencies delegate to other organizations to make guidelines. For example [1], Even HHS, which has express cybersecurity rulemaking authority under the Health Insurance Portability and Accountability [...]The post Are guidance documents laws? first appeared on John D. Cook.

A week or two ago I wrote about Laguerre's root-finding method and made some associated images. This post gives a couple more examples. Laguerre's method is very robust in the sense that it is likely to converge to a root, regardless of the starting point. However, it may be difficult to predict which root the [...]The post More Laguerre images first appeared on John D. Cook.