John D. Cook

I've written a couple posts lately about reverse engineering the internal state of a random number generator, first Mersenne Twister then lehmer64. This post will look at xorshift128, implemented below. import random # Seed the generator state a: int = random.getrandbits(32) b: int = random.getrandbits(32) c: int = random.getrandbits(32) d: int = random.getrandbits(32) MASK = [...]The post Recovering the state of xorshift128 first appeared on John D. Cook.

If you look very closely at my previous post, you'll notice that I initialize a 128-bit integer with a 64-bit value. The 128-bit unsigned integer represents the internal state of a random number generator. Why not initialize it to a 128-bit value? I was trying to keep the code simple. A surprising feature of C [...]The post Initialize and print 128-bit integers in C first appeared on John D. Cook.

A couple days ago I wrote about hacking the Mersenne Twister. I explained how to recover the random number generator's internal state from a stream of 640 outputs. This post will do something similar with the lehmer64 random number generator. This generator is very simple to implement. Daniel Lemire found it to be the fastest [...]The post Hacking the lehmer64 RNG first appeared on John D. Cook.

This morning I wrote a post about the probability that a random matrix over a finite field is invertible. If the field has q elements and the matrix has dimensions n * n then the probability is In that post I made observation that p(q, n) converges very quickly as a function of n [1]. [...]The post Euler function first appeared on John D. Cook.

What is the inverse of shifting a sequence to the right? Shifting it to the left, obviously. But wait a minute. Suppose you have a sequence of eight bits abcdefgh and you shift it to the right. You get 0abcdefg. If you shift this sequence to the left you get abcdefg0 You can't recover the [...]The post Inverse shift first appeared on John D. Cook.

The two latest posts have involved invertible matrices with 0 and 1 entries. If you fill an n * n matrix with 0s and 1s randomly, how likely is it to be invertible? What kind of inverse? There are a couple ways to find the probability that a binary matrix is invertible, depending on what [...]The post Probability that a random binary matrix is invertible first appeared on John D. Cook.

The previous post looked at the tempering step of the Mersenne Twister, formulating a sequence of bit operations as multiplication by a matrix mod 2. This post will look at the components more closely. The theorems of linear algebra generally hold independent of the field of scalars. Typically the field is or , but [...]The post The linear algebra of bit twiddling first appeared on John D. Cook.

The Mersenne Twister (MT) is a random number generator with good statistical properties but bad cryptographic properties. In buzzwords, it's a PRNG but not a CSPRNG. This post will show how the internal state of a MT generator can be recovered from its output. We'll do this using linear algebra. The bit twiddling approach is [...]The post Reverse engineering Mersenne Twister with Linear Algebra first appeared on John D. Cook.

Curvature is conceptually simple but usually difficult to calculate. For a level set curve f(x,y) = c, such as in the previous couple posts, the equation for curvature is Even whenf has a fairly simple expression, the expression for can be complicated. If we define then the level set of f(x,y) = c is [...]The post Calculating curvature first appeared on John D. Cook.

The previous post constructed a triangular analog of the squircle, the unit circle in thep-norm wherep is typically around 4. The casep = 2 is a Euclidean circle and the limit as p is a Euclidean square. The previous post introduced three functions Li(x,y) such that the level set of each function forms [...]The post Smoothed polygons first appeared on John D. Cook.

TimF left a comment on my guitar pick post saying the image was a squircle-ish analog for an isosceles triangle." That made me wonder what a more direct analog of the squircle might be for a triangle. A squircle is not exactly a square with rounded corners. The sides are continuously curved, but curved most [...]The post Triangular analog of the squircle first appeared on John D. Cook.

I try to maintain a consistent work environment across computers that I use. The computers differ for important reasons, but I'd rather they not differ for unimportant reasons. Unified keys One thing I do is remap keys so that the same key does the same thing everywhere, to the extent that's practical. This requires remapping [...]The post Unified config files first appeared on John D. Cook.

Yesterday a friend and I had a conversation about category theory, how it can be a useful pattern description language, but also about how people have unrealistic expectations for it, believing category theory can deliver something for nothing. Later I ran across the following post from Qiaochu Yuan. It felt as if he had overheard [...]The post The mythology of category theory first appeared on John D. Cook.

I saw a post on X saying Changing a hyphen to an en-dash increases your PDF file size by ~10 bytes. My first thought was that it had something to do with hyphen being an ASCII character and an en-dash not. Changing a hyphen to an en-dash would make a UTF-8 encoded text file a [...]The post Changing one character in a PDF first appeared on John D. Cook.

I saw a post on X that plotted the function (logx)^2 + (logy)^2 = 1. Of course the plot of x^2 + y^2 = 1 is a circle, but I never thought what taking logs would do to the shape. Here's what the contours look like setting the right hand side equal to 1, 2, [...]The post The shape of a guitar pick first appeared on John D. Cook.

A couple days ago I wrote a post about turning a trick into a technique, finding another use for a clever way to construct simple, accurate approximations. I used as my example approximating the Bessel function J(x) with (1 + cos(x))/2. I learned via a helpful comment on Mathstodon that my approximation was the first-order [...]The post Approximating even functions by powers of cosine first appeared on John D. Cook.

When a function is not differentiable in the classical sense there are multiple ways to compute a generalized derivative. This post will look at three generalizations of the classical derivative, each applied to the ReLU (rectified linear unit) function. The ReLU function is a commonly used activation function for neural networks. It's also called the [...]The post Three ways to differentiate ReLU first appeared on John D. Cook.

Someone said a technique is a trick that works twice. I wanted to see if I could get anything interesting by turning the trick in the previous post into a technique. The trick created a high-order approximation by subtracting a multiple one even function from another. Even functions only have even-order terms, and by using [...]The post Turning a trick into a technique first appeared on John D. Cook.

Suppose you have an arc a, a portion of a circle of radius r, and you know two things: the length c of the chord of the arc, and the lengthbof the chord of half the arc, illustrated below. Here is the central angle of the arc. Then the length of the arc, r, [...]The post Circular arc approximation first appeared on John D. Cook.

The previous post looks at the nonlinear pendulum equation and what difference it makes to the solutions if you linearize the equation. If the initial displacement is small enough, you can simply replace sin with . If the initial displacement is larger, you can improve the accuracy quite a bit by solving the linearized [...]The post Closed-form solution to the nonlinear pendulum equation first appeared on John D. Cook.

There's a nice formula for thenth derivative of a product. It looks a lot like the binomial theorem. There is also a formula for thenth derivative of a quotient, but it's more complicated and less known. We start by writing the quotient rule in an unusual way. Applying the quotient rule twice gives the following. [...]The post nth derivative of a quotient first appeared on John D. Cook.

The equation of motion for a pendulum is the differential equation whereg is the acceleration due to gravity and is the length of the pendulum. When this is presented in an introductory physics class, the instructor will immediately say something like we're only interested in the case where is small, so we can [...]The post How nonlinearity affects a pendulum first appeared on John D. Cook.

The previous post gave a simple and accurate approximation for the smaller angle of a right triangle. Given aright triangle with sides a,b, andc, wherea is the shortest side andc is the hypotenuse, the angle opposite side a is approximately in radians. The previous post worked in degrees, but here we'll use radians. If the [...]The post Approximation to solve an oblique triangle first appeared on John D. Cook.

Suppose you have a right triangle with sidesa,b, andc, wherea is the shortest side andc is the hypotenuse. Then the following approximation from [1] for the angle Aopposite side a seems too simple and too accurate to be true. In degrees, A a 172 / (b + 2c). The approximation above only involves simple [...]The post Simple approximation for solving a right triangle first appeared on John D. Cook.

AI coding agents improved greatly last summer, and again last December-January. Here are my experiences since my last post on the subject. The models feel subjectively much smarter. They can accomplish a much broader range of tasks. They seem to have a larger, more comprehensive in-depth view of the code base and what you are [...]The post An AI Odyssey, Part 4: Astounding Coding Agents first appeared on John D. Cook.

A few days ago I wrote a post on Newton's diameter theorem. The theorem says to plot the curve formed by the solutions to f(x, y) = 0 where f is a polynomial in x and y of degree n. Next plot several parallel lines that cross the curve at n points and find the [...]The post More on Newton's diameter theorem first appeared on John D. Cook.

The previous post looked at the FP4 4-bit floating point format. This post will look at another 4-bit floating point format, NF4, and higher precision analogs. NF4 and FP4 are common bitsandbytes 4-bit data types. If you download LLM weights from Hugging Face quantized to four bits, the weights might be in NF4 or FP4 [...]The post Gaussian distributed weights for LLMs first appeared on John D. Cook.

In ancient times, floating point numbers were stored in 32 bits. Then somewhere along the way 64 bits became standard. The C programming language retains the ancient lore, using float to refer to a 32-bit floating point number and double to refer to a floating point number with double the number of bits. Python simply [...]The post 4-bit floating point FP4 first appeared on John D. Cook.

Letf(x,y) be annth degree polynomial inx andy. In general, a straight line will cross the zero set off inn locations [1]. Newton defined a diameter to be any line that crosses the zero set off exactlyn times. If f(x,y) =x^2 +y^2 - 1 then the zero set off is a circle and diameters of the [...]The post Newton diameters first appeared on John D. Cook.

The post AI and reasoning: Are we in danger? first appeared on John D. Cook.

We know a lot about Robert Oppenheimer and Los Alamos national laboratory from the movie.Many AI researchers today read avidly the classic work by Richard Rhodes, the making of the atomic bomb. But there's a stronger connection between Oppenheimers work and current AI research that's sometimes not noticed. By the end of World War [...]The post Oppenheimer's legacy: How the national labs forged the age of hyperscale AI first appeared on John D. Cook.

If you know the distance d to a satellite, you can compute a circle of points that passes through your location. That's because you're at the intersection of two spheres-the earth's surface and a sphere of radius d centered on the satellite-and the intersection of two spheres is a circle. Said another way, one observation [...]The post Intersecting spheres and GPS first appeared on John D. Cook.

The Wikipedia article on modern triangle geometry has an image labeled Artzt parabolas" with no explanation. A quick search didn't turn up anything about Artzt parabolas [1], but apparently the parabolas go through pairs of vertices with tangents parallel to the sides. The general form of a conic section is ax^2 + bxy + cy^2 [...]The post Finding a parabola through two points with given slopes first appeared on John D. Cook.

Andrzej Odrzywolek recently posted an article on arXiv showing that you can obtain all the elementary functions from just the function and the constant 1. The following equations, taken from the paper's supplement, show how to bootstrap addition, subtraction, multiplication, and division from the eml function. See the paper and supplement for how to obtain [...]The post Mathematical minimalism first appeared on John D. Cook.

The date of Easter The church fixed Easter to be the first Sunday after the first full moon after the Spring equinox. They were choosing a date in the Roman (Julian) calendar to commemorate an event whose date was known according to the Jewish lunisolar calendar, hence the reference to equinoxes and full moons. The [...]The post Lunar period approximations first appeared on John D. Cook.

Today is Orthodox Easter. Western churches celebrated Easter last week. Why are the Eastern and Western dates of Easter different? Is Eastern Easter always later than Western Easter? How far apart can the two dates be? Why the dates differ Easter is on the first Sunday after the first full moon in Spring [1]. East [...]The post The gap between Eastern and Western Easter first appeared on John D. Cook.

There's a lot of mathematics just off the beaten path. You can spend a career in math and yet not know all there is to know about even the most basic areas of math. For example, this post will demonstrate something you may not have seen about decimal forms of fractions. Let p > 5 [...]The post Distribution of digits in fractions first appeared on John D. Cook.

Saw a post on X saying that the latitude of the Pyramid of Giza is the same as the speed of light. I looked into this, expecting it to be approximately true. It's exactly true in the sense that the speed of light in vacuum is 299,792,458 m/s and the line of latitude 29.9792458 N [...]The post The Great Pyramid of Giza and the Speed of Light first appeared on John D. Cook.

I recently ran across a post on X describing a process for creating a random fractal. First, pick a random point c inside a hexagon. Then at each subsequent step, pick a random side of the hexagon and create the triangle formed by that side andc. Updatec to be the center of the new triangle [...]The post Random hexagon fractal first appeared on John D. Cook.

I recently found out about Andrica's conjecture: the square roots of consecutive primes are less than 1 apart. In symbols, Andrica's conjecture says that if pn and pn+1 are consecutive prime numbers, then pn+1 - pn < 1. This has been empirically verified for primes up to 2 * 1019. If the conjecture is true, [...]The post Root prime gap first appeared on John D. Cook.

Last week I wrote about the orbit of Artemis II. The orbit of Artemis I was much more interesting. Because Artemis I was unmanned, it could spend a lot more time in orbit. The Artemis I mission took 25 days while Artemis II will take 10 days. Artemis I took an unusual path, orbiting the [...]The post A Three- and a Four- Body Problem first appeared on John D. Cook.

Landauer's principle gives a lower bound on the amount of energy it takes to erase one bit of information: E >= log(2) kB T where kB is the Boltzmann constant and T is the ambient temperature in Kelvin. The lower bound applies no matter how the bit is physically stored. There is no theoretical lower [...]The post Toffoli gates are all you need first appeared on John D. Cook.

The best way to run AI and remain HIPAA compliant is to run it locally on your own hardware, instead of transferring protected health information (PHI) to a remote server by using a cloud-hosted service like ChatGPT or Claude. [1]. There are HIPAA-compliant cloud options, but they're both restrictive and expensive. Even enterprise options are [...]The post HIPAA compliant AI first appeared on John D. Cook.

This post will look at the problem of updating an average grade as a very simple special case of Bayesian statistics and of Kalman filtering. Suppose you're keeping up with your average grade in a class, and you know your average after n tests, all weighted equally. m = (x1 + x2 + x3 + [...]The post Kalman and Bayes average grades first appeared on John D. Cook.

I used the term perilune in yesterday's post about the flight path of Artemis II. When Artemis isclosest to the moon it will be furthest from earth because its closest approach to the moon, its perilune, is on the side of the moon opposite earth. Perilune is sometimes called periselene. The two terms come from [...]The post Roman moon, Greek moon first appeared on John D. Cook.

I was looking through an old geometry book [1] and saw a hyperbolic analog of Napier's mnemonic for spherical trigonometry. In hindsight of course there's a hyperbolic analog: there's a hyperbolic analog of everything. But I was surprised because I'd never thought of this before. I suppose the spherical version is famous because of its [...]The post Hyperbolic version of Napier's mnemonic first appeared on John D. Cook.

The Artemis II mission launched yesterday. Much like the Apollo 8 mission in 1968, the goal is to go around the moon in preparation for a future mission that will land on the moon. And like Apollo 13, the mission will swing around the moon rather than entering lunar orbit. Artemis II will deliberately follow [...]The post Artemis II, Apollo 8, and Apollo 13 first appeared on John D. Cook.

Pentagonal numbers are truncated triangular numbers. You can take the diagram that illustrates thenth pentagonal number and warp it into the base of the image that illustrates the (2n - 1)st triangular number. If you added a diagram for the (n - 1)st triangular number to the bottom of the image on the right, you'd [...]The post Pentagonal numbers are truncated triangular numbers first appeared on John D. Cook.

I'm skeptical that quantum computing will become practical. However, if it does become practical before we're prepared, the world's financial system could collapse. Everyone agrees we should prepare for quantum computing, even those of us who doubt it will be practical any time soon. Quantum computers exist now, but the question is when and if [...]The post Quantum Y2K first appeared on John D. Cook.

Peter Vogel posted the following image on X yesterday. The receive side of the coin is a decision tree for decoding Morse code. The shape is what makes this one interesting. Decision trees are typically not very compact. Each branch is usually on its own horizontal level, with diagonal lines going down from each node [...]The post Morse code tree first appeared on John D. Cook.