John D. Cook

One of the fiddly parts of regular expressions is how to handle line breaks. Should regular expression searches be applied one line at a time, or should an entire file be treated as a single line? This morning I was trying to track down a LaTeX file that said discussed in the Section" rather than [...]The post Regular expressions that cross lines first appeared on John D. Cook.

Here's a curious theorem I stumbled across recently [1]. Take an integerN which is not a multiple of 10. Then there is some multiple ofN which only contains the digits 1, 2, 3, 4, and 5. For example, my business phone number 8324228646 has a couple 8s and a couple 6s. But 6312 * 8324228646 [...]The post Multiples with no large digits first appeared on John D. Cook.

The expression converges to the golden ratio . Another way to say this is that the sequence defined by x0 = 1 and for n > 0 converges to . This post will be about how it converges. I wrote a little script to look at the error in approximating by xn and noticed [...]The post Golden iteration first appeared on John D. Cook.

When I was a kid, I suppose sometime in my early teens, I was interested in music theory, but I couldn't play piano. One time I asked a lady who played piano at our church to play a piece of sheet music for me so I could hear how it sounded. The music was in [...]The post Just change the key first appeared on John D. Cook.

Say you have a common 6-sided die and need to roll it until the sum of your rolls is at least 6. How many times would you need to roll? If you had a 20-sided die and you need to roll for a sum of at least 20, would that take more rolls or fewer [...]The post Rolling n-sided dice to get at least n first appeared on John D. Cook.

There are numerous memes floating around with the words Being weak is nothing to be ashamed of; staying weak is." Or some variation. I thought about this meme in the context of weak derivatives. The last couple posts have talked about distributions, also called generalized functions. The delta function, for example, is not actually a [...]The post Weak derivatives first appeared on John D. Cook.

The previous post showed how we can take the Fourier transform of functions that don't have a Fourier transform in the classical sense. The classical definition of the Fourier transform of a function f requires the integral of |f| over the real line to be finite. This implies f(x) must approach zero as x goes [...]The post Fourier transform of a Fourier series first appeared on John D. Cook.

Suppose you have a constant function f(x) = c. What is the Fourier transform of f? We will show why the direct approach doesn't work, give two hand-wavy approaches, and a rigorous definition. Direct approach Unfortunately there are multiple conventions for defining the Fourier transform. For this post, we will define the Fourier transform of [...]The post Fourier transform of a flat line first appeared on John D. Cook.

The weakest link in the privacy of cryptocurrency transactions is often outside the blockchain. There are technologies such as stealth addresses and subaddresses to try to thwart attempts to link transactions to individuals. They do a good job of anonymizing transaction data, but the weak link may be metadata, as is often the case. Cryptocurrency [...]The post Obscuring P2P nodes with Dandelion first appeared on John D. Cook.

I'm taking a break from my series on celestial navigation. The previous posts give the basics, but I haven't thought of a way to go further that I'm satisfied with. So now for something completely different: Pedersen commitments. Pedersen commitments are a building block of zero knowledge proofs (ZKP), and they give an opportunity to [...]The post What is a Pedersen commitment? first appeared on John D. Cook.

This post is a side quest in the series on navigating by the stars. It expands on a footnote in the previous post. There are six pieces of information associated with a spherical triangle: three sides and three angles. I said in the previous post that given three out of these six quantities you could [...]The post Solving spherical triangles first appeared on John D. Cook.

The previous post introduced the idea of finding your location by sighting a star. There is some point on Earth that is directly underneath the star at any point in time, and that location is called the star's GP (geographic position). That is one vertex of the navigational triangle. The other two vertices are your [...]The post The Navigational Triangle first appeared on John D. Cook.

The previous post touched on how Lewis and Clark recorded celestial observations so that the data could be turned into coordinates after they returned from their expedition. I intend to write a series of posts about celestial navigation, and this post will discuss one fundamental topic: line of position (LOP). Pick a star that you [...]The post Line of position (LOP) first appeared on John D. Cook.

I read Undaunted Courage, Stephen Ambrose's account of the Lewis and Clark expedition, several years ago [1], and now I'm listening to it as an audio book. The first time I read the book I glossed over the accounts of the expedition's celestial observations. Now I'm more curious about the details. The most common way [...]The post Lewis & Clark geolocation first appeared on John D. Cook.

A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key. Here's another example, one that's more concrete than a digital signature. Suppose you have a deck of 52 cards, 13 of each of spades, hearts, [...]The post Zero knowledge proof of compositeness first appeared on John D. Cook.

Monero has a way of generating new addresses analogous to the way HD wallets generate new addresses for Bitcoin. In both cases, the recipient's software can generate new addresses to receive payments that others cannot link back to the recipient. Monero users have two public/private keys pairs: one for viewing and one for spending. Let [...]The post Monero subaddresses first appeared on John D. Cook.

Spherical geometry In spherical geometry, the interior angles of a triangle add up to more than . And in fact you can determine the area of a spherical triangle by how much the angle sum exceeds . On a sphere of radius 1, the area equals the triangle excess Area = E = interior angle [...]The post A triangle whose interior angles sum to zero first appeared on John D. Cook.

Let be the upper half plane, the set of complex real numbers with positive imaginary part. When we measure distances the way we've discussed in the last couple posts, the geometry of is hyperbolic. What is a circle of radius r in ? The same as a circle in any geometry: it's the [...]The post A circle in the hyperbolic plane first appeared on John D. Cook.

The previous post described a metric for the Poincare upper half plane. The development is geometrical rather than analytical. There are also analytical formulas for the metric, at least four that I've seen. It's not at all obvious that the four equations are equivalent, or that any of them matches the expression in the previous [...]The post Equal things that don't look equal first appeared on John D. Cook.

One common model of the hyperbolic plane is the Poincare upper half plane . This is the set of points in the complex plane with positive imaginary part. Straight lines are either vertical, a set of points with constant imaginary part, or arcs of circles centered on the real axis. The real axis is not [...]The post Hyperbolic metric first appeared on John D. Cook.

The opening line of William Gibson's novel Neuromancer is famous: The sky above the port was the color of a television, tuned to a dead channel. When I read this line, I knew immediately what he meant, and thought it was a brilliant line. Later I learned that younger readers didn't know what he was [...]The post TV tuned to a dead channel first appeared on John D. Cook.

Suppose Alice runs a confidential restaurant. Alice doesn't want there to be any record of who visited her restaurant but does want to get paid for her food. She accepts Monero, and instead of a cash register there are two QR codes on display, one corresponding to her public view keyA and the other corresponding [...]The post How stealth addresses work in Monero first appeared on John D. Cook.

I was reading about Shackleton's incredible expedition to Antarctica, and the Weddell Sea features prominently. That name sounded familiar, and I was trying to remember where I'd heard of Weddell in math. I figured out that it wasn't Weddell exactly but Weddle I was thinking of. The Weddell Sea is named after James Weddell (1787-1834). [...]The post Weddle integration rule first appeared on John D. Cook.

The previous post includes code for solving the equation Hn = m i.e. finding the value ofn for which thenth harmonic number is the closest tom. It works well for small values ofm. It works for largem in the sense that the solution is very close tom, but it's not necessarily the best solution. For [...]The post Solving H_n = 100 first appeared on John D. Cook.

I mentioned in the previous post that the harmonic numbers Hn are never integers for n > 1. In the spirit of that post, I'd like to find the value of n such that Hn is closest to a given integer m. We have two problems to solve. First, how do we accurately and efficiently [...]The post Closest harmonic number to an integer first appeared on John D. Cook.

Jozsef Kurschak proved in 1908 that the function is never an integer for 0 < m < n. In particular, the harmonic numbers are never integers for n > 1. The function f(m,n) can get arbitrarily close to any integer value by taking m andn large enough, but it can never exactly equal an integer. [...]The post Closest consecutive reciprocal sum to an integer first appeared on John D. Cook.

Five posts on Pythagorean triangles and Pythagorean triples Primitive Pythagorean triangles with the same area Sparse binary Pythagorean triples Matrix Pythagorean triples Approximation by Pythagorean triangles Fibonacci meets PythagorasThe post Pythagorean triples first appeared on John D. Cook.

The last couple posts have been about group pairings, specifically Tate pairings as they're used in cryptography. This post will show that RSA encryption can be seen as a special case of pairing-based cryptography. The idea comes from Ben Lynn's 2007 dissertation. Lynn is the L" in BLS signatures-one of the topics in his dissertations-and [...]The post RSA as a pairing first appeared on John D. Cook.

Elliptic curve Diffie-Hellman Given a point P on an elliptic curve E, and a random number a, aP means to add P to itself a times, using the addition on E. The pointaP can be computed efficiently, even ifa is a very large number [1]. However, if E has a large number of points, and [...]The post Three-party Diffie-Hellman in one shot first appeared on John D. Cook.

Pairings can mean a variety of related things in group theory, but for our purposes a pairing is a bilinear mapping from two groups to a third group. e: G1 * G2 GT Typically the group operation on G1 and G2 is written addititvely and the group operation on GT is written multiplicatively. In [...]The post Elliptic curve pairings in cryptography first appeared on John D. Cook.

Let p be a prime number. Then the integers mod p form a finite field. The number of elements in a finite field must be a power of a prime, i.e. the order q = pn for some n. When n > 1, we can take the elements of our field to be polynomials of [...]The post Adding an imaginary unit to a finite field first appeared on John D. Cook.

Here are four theorems that generalize the Pythagorean theorem. Follow the links for more details regarding each equation. 1. Theorem by Apollonius for general triangles. 2. Edsgar Dijkstra's extension of the Pythagorean theorem for general triangles. 3. A generalization of the Pythagorean theorem to tetrahedra. 4. A unified Pythagorean theorem that covers spherical, plane, and [...]The post Four generalizations of the Pythagorean theorem first appeared on John D. Cook.

Themth elementary symmetric polynomial of degreen is the sum of all terms containing a product of m variables. So, for example, These polynomials came up in the previous post. The problem was choosing weights to minimize the variance of a weighted sum of random variables can be solved using elementary symmetric polynomials. To state the [...]The post Elementary symmetric polynomials and optimization first appeared on John D. Cook.

Suppose you have $100 to invest in two independent assets, A andB, and you want to minimize volatility. SupposeA is more volatile thanB. Then putting all your money onA would be the worst thing to do, but putting all your money onB would not be the best thing to do. The optimal allocation would be [...]The post Weighting an average to minimize variance first appeared on John D. Cook.

Excellent video by Almost Sure: What does Riemann Zeta have to do with Brownian Motion? Connects several things that I've written about here including Brownian motion, the Riemann zeta function, and the Kolmogorov-Smirnov test.The post Brownian motion and Riemann zeta first appeared on John D. Cook.

Suppose you have data on the closing prices of two stocks over 1,000 days and you want to look at the correlation between the two asset prices over time in rolling 30 day windows. It seems that the rolling correlation is periodic. peaking about every 50 days. But this is an artifact of the rolling [...]The post Rolling correlation first appeared on John D. Cook.

The area of a triangle can be computed directly from the lengths of its sides via Heron's formula. Heres is the semiperimeter,s = (a +b +c)/2. Is there an analogous formula for spherical triangles? It's not obvious there should be, but there is a formula by Simon Antoine Jean L'Huilier (1750-1840). Here we denote area [...]The post Analog of Heron's formula on a sphere first appeared on John D. Cook.

There's increasing talk of gigawatt data centers. Currently the largest data center, Switch's Citadel Campus in Nevada, uses 850 megawatts of power. OpenAI's Stargate data center, under construction, is supposed to use 1.2 gigawatts. Gigawatt An average French nuclear reactor produces about a gigawatt of power. If the US were allowed build nuclear reactors, we [...]The post How much is a gigawatt? first appeared on John D. Cook.

Here's an interesting theorem that leads to some aesthetically pleasing images. It's known as the Japanese cyclic polygon theorem. For all triangulations of a cyclic polygon, the sum of inradii of the triangles is constant. Conversely, if the sum of inradii is independent of the triangulation, then the polygon is cyclic. The image above shows [...]The post Japanese polygon theorem first appeared on John D. Cook.

A tetrahedron has four triangular faces. Suppose three of those faces come together like the corner of a cube, each perpendicular to the other. Let A1, A2, and A3 be the areas of the three triangles that meet at this corner and let A0 be the area of remaining face, the one opposite the right [...]The post Tetrahedral analog of the Pythagorean theorem first appeared on John D. Cook.

As I've written about several times lately, the Smith chart is the image of a rectangular grid in the right half-plane under the function f(z) = (z- 1)/(z+ 1). What would the image of a grid in the left half-plane look like? For starters, sincef maps the right half-plane to the interior of the unit [...]The post The anti-Smith chart first appeared on John D. Cook.

A few days ago I wrote two posts about how to create a Smith chart, a graphical device used for impedance calculations. Then someone emailed me to point out the connection between the Smith chart and triangular numbers. The Smith chart is the image of a rectangular grid in the right half-plane under the function [...]The post Impedance and Triangular Numbers first appeared on John D. Cook.

The cross ratio of four pointsA,B,C,D is defined by whereXY denotes the length of the line segment fromX toY. The idea of a cross ratio goes back at least as far as Pappus of Alexandria (c.290 - c.350 AD). Numerous theorems from geometry are stated in terms of the cross ratio. For example, the cross [...]The post Cross ratio first appeared on John D. Cook.

Let's make a QR code out of a sentence two ways: mixed case and upper case. We'll use Python with the qrcode library. >>> import qrcode >>> s = "The quick brown fox jumps over the lazy dog." >>> qrcode.make(s).save("mixed.png") >>> qrcode.make(s.upper()).save("upper.png") Here are the mixed case and upper case QR codes. The QR code [...]The post Text case changes the size of QR codes first appeared on John D. Cook.

Apollonius of Perga (c. 262 BC - c. 190 BC) discovered a theorem that generalizes the Pythagorean theorem but isn't nearly as well known. Let ABC be a general triangle, and let D be the midpoint of the segment AB. Leta be the length of the side opposite A andb the length of the side [...]The post An ancient generalization of the Pythagorean theorem first appeared on John D. Cook.

The previous post required computing After writing the post, I thought about how you would mentally approximate log2 5. The most crude approximation would round 5 down to 4 and use log2 4 = 2 to approximate log2 5.That would be good enough for an order of magnitude guess, but we can do much better [...]The post Mentally compute logs base 2 first appeared on John D. Cook.

A physical key, such as a house key, is a piece of metal with cuts of differing depths. Typically there may be around 6 cuts, with five different possible depths for each cut. This allows 56 = 15,625 possible keys. Encryption keys, such as AES keys, are a string of bits, often 128 bits, for [...]The post Physical Keys and Encryption Keys first appeared on John D. Cook.

The Freshman's dream" is the statement (x+ y)p = xp + yp It's not true in general, but itis true modp if p is a prime. It's a cute result, but it's also useful in applications, such as finite field computations in cryptography. Here's a demonstration of the Freshman's dream in Python. >>> p = [...]The post Freshman's dream first appeared on John D. Cook.

Yesterday's post looked at a recently mined Bitcoin block, the 920,994th block in the blockchain, and verified that it contains the hash of the previous block. This post will look at the same block and verify its Merkle tree root. Before getting down to the bytes, we'll back up and say what a Merkle tree [...]The post Why and how Bitcoin uses Merkle trees first appeared on John D. Cook.

The high-level explanation of a blockchain says that each block contains a cryptographic hash of the previous block. That's how the blocks are chained together. That's not exactly true, and it leaves out a lot of detail. This post will look in full detail at how Bitcoin blocks are chained together by inspecting the bits [...]The post How blocks are chained in a blockchain first appeared on John D. Cook.