The following equation, known as the BBP formula [1], will let you compute the nth digit of π directly without having to compute the previous digits.

I’ve seen this claim many times, but I’ve never seen it explained in much detail how this formula lets you extract digits of π.

First of all, this formula lets you calculate the digits of π, not in base 10, but in base 16, i.e. in hexadecimal.

It looks like the BBP formula might let you extract hexadecimal digits. After all, the hexadecimal expansion of π is the set of coefficients a_n such that

where each a_n is an integer between 0 and 15. But the term multiplying 16⁻ⁿ in the BBP formula is not an integer, so it’s not that easy. Fortunately, it’s not that hard either.

Warmup

As a warmup, let’s think how we would find the nth digit of π in base 10. We’d multiply by 10ⁿ, throw away the factional part, and look at the last digit. That is, we would calculate

Another approach would be to multiply by 10ⁿ⁻¹, shifting the digit that we’re after to the first digit after the decimal point, then take the integer part of 10 times the fraction part.

Here {x} denotes the fractional part of x. This is a little more complicated, but now all the calculation is inside the floor operator.

For example, suppose we wanted to find the 4th digit of π. Multiplying by 10³ gives 3141.592… with fractional part 0.592…. Multiplying by 10 gives 5.92… and taking the floor gives us 5.

100th hex digit

Now to find the nth hexadecimal digit we’d do the analogous procedure, replacing 10 with 16. To make things concrete, let’s calculate the 100th hexadecimal digit. We need to calculate

We can replace the infinite sum with a sum up to 99 because the remaining terms sum to an amount too small to change our answer. Note that we’re being sloppy here, but this step is justified in this particular example.

Here’s the trick that makes this computation practical: when calculating the fractional part, we can carry out the calculation of the first term mod (8n + 1), and the second part mod (8n + 4), etc. We can use fast modular exponentiation, the same trick that makes, for example, a lot of encryption calculations practical.

Here’s code that evaluates the Nth hexadecimal digit of π by evaluating the expression above.

def hexdigit(N):
    s = 0
    for n in range(N):
        s += 4*pow(16, N-n-1, 8*n + 1) / (8*n + 1)
        s -= 2*pow(16, N-n-1, 8*n + 4) / (8*n + 4)
        s -=   pow(16, N-n-1, 8*n + 5) / (8*n + 5)
        s -=   pow(16, N-n-1, 8*n + 6) / (8*n + 6)
    frac = s - floor(s)
    return floor(16*frac)

Here the three-argument version of pow, introduced into Python a few years ago, carries out modular exponentiation efficiently. That is, pow(b, x, m) calculates b^x mod m.

This code correctly calculates that the 100th hex digit of π is C. Note that we did not need 100 hex digits (400 bits) of precision to calculate the 100th hex digit of π. We used standard precision, which is between 15 and 16 bits.

Improved code

We can improve the code above by adding an estimate of the infinite series we ignored.

A more subtle improvement is reducing the sum accumulator variable s mod 1. We only need the fractional part of s, and so by routinely cutting off the integer part we keep s from getting large. This improves accuracy by devoting all the bits in the machine representation of s to the fractional part.

epsilon = np.finfo(float).eps

def term(N, n):
     return 16**(N-1-n) * (4/(8*n + 1) - 2/(8*n+4) - 1/(8*n+5) - 1/(8*n + 6))

def hexdigit(N):
    s = 0
    for n in range(N):
        s += 4*pow(16, N-n-1, 8*n + 1) / (8*n + 1)
        s -= 2*pow(16, N-n-1, 8*n + 4) / (8*n + 4)
        s -=   pow(16, N-n-1, 8*n + 5) / (8*n + 5)
        s -=   pow(16, N-n-1, 8*n + 6) / (8*n + 6)
        s = s%1

    n = N + 1    
    while True:
        t = term(N, n)
        s += t
        n += 1
        if abs(t) < epsilon:
            break
        
    frac = s - floor(s)
    return floor(16*frac)

I checked the output of this code with [1] for N = 10⁶, 10⁷, 10⁸, and 10⁹. The code will fail due to rounding error for some very large N. We could refine the code to push this value of N a little further out, but eventually machine precision will be the limiting factor.

[1] Named after the initials of the authors. Bailey, David H.; Borwein, Peter B.; Plouffe, Simon (1997). On the Rapid Computation of Various Polylogarithmic Constants. Mathematics of Computation. 66 (218) 903–913.

When I’m in the mood to write, you can often follow a chain of though in my posts. Recently, a post on LLM tokenization lead to a post on how Unicode characters are tokenized, which led to a post on Unicode surrogates. The latter ended by touching on Unicode’s PUA (Private Use Area), which of course leads to J.R.R. Tolkien and privacy, as we shall see.

To back up a bit, Unicode started as an attempt to one alphabet to rule them all, a coding system large enough to contain all the world’s writing systems. Initially it was thought that 2¹⁶ = 65,536 symbols would be enough, but that didn’t last long. The Unicode standard now contains nearly 100,000 Chinese characters alone [1], along with myriad other symbols such as graphical drawing elements, mathematical symbols, and emoji.

Private Use Area

Although Unicode is vast, it doesn’t have room to include every symbol anyone might use. Unicode anticipated that contingency and reserved some areas for private use. The most well known example is probably Apple’s use of U+F8FF for their logo . The private use area is also being used for ancient and medieval scripts, as well as for fictional writing systems such as Tolkein’s Tengwar and Cirth.

Because anyone can use the private use area as they wish, there could be conflicts. For example, Apple intends U+F8FF to display their logo, but the code point is also used for a Klingon symbol. We’ll see another example of a conflict at the end of this post.

Privacy

Here’s the chain of thought that leads to privacy. When I started thinking about this post, I thought about creating an image of Tengwar writing, and that made me think about font fingerprinting. Browsers let web servers know what fonts you have installed, which serves a benign purpose: a site may want to send you text formatted in a particular font if its available but will fall back to a more common font if necessary.

However, the collection of fonts installed on a particular computer may be unique, or at least used in combination with other browser information to uniquely identify a user. Before installing a Tengwar font I thought about how it would be sure to increase the uniqueness of my font fingerprint.

Tolkein’s Tengwar

J. R. R. Tolkein’s Tengwar writing system has been mapped to Unicode range E000 to E07F.

Here’s a sample. No telling what it looks like in your browser:

      

When I view the same text in Tecendil online transcriber I see this:

But then I open the text in Emacs I see this:

Both are legitimate renderings because nobody owns the private use areas. The characters that Tecendil uses for Tengwar, apparently some font on my laptop uses to display Chinese characters.

I’m especially curious about the last character, U+E000. Tecendil interprets it as the Tengwar symbol tinco but something on my laptop interprets it as the Mozilla mascot.

[1] It wasn’t so naive to think 16 bits would do, even including Chinese. There may be 100,000 Chinese characters, but a few thousand characters account for nearly all Chinese writing. More on that here. But if you’re going to break the 16-bit barrier anyway, you might as well try to include even the most rare characters.

When my children were little, I read the Little House on the Prairie books aloud to them and I naturally saw the books through the eyes of a child. Last night I started reading the books by myself for the first time and saw them very differently.

Laura Ingalls Wilder wrote the Little House books later in life, looking back at her childhood an early adult years. The events in the books took place in the last quarter of the nineteenth century.

At first glance the books tell the story of the Ingalls family living off the land, which to a large extent they did. The first chapter of the first book describes the family salting and smoking meat in order to have food for the winter when it would be hard to hunt game. Without adequate preparation they would starve, which they nearly do in one of the latter books.

The initial chapter also describes the father greasing his traps. He didn’t smelt iron to make his traps; he had bought the traps somewhere and brought them with him. There no sense in the books that the family was trying to avoid contemporary technology. They gladly used the technology available to them, such as it was.

In addition to hardware such as bear traps, the family also had consumables they could not produce themselves. Where did they get the salt to preserve their meat? They didn’t drive their SUV down to Costco, but neither did they mine salt. And as I wrote about years ago, the books mention coffee, something that doesn’t grow in the continental United States.

Obtaining supplies was difficult, not something they would do lightly or frequently, but there’s no sense that they saw buying supplies as a failing. They were trying to settle new land, but they weren’t trying to get away from contemporary amenities. They did without amenities out of necessity, not out of conviction.

The previous post was an AI-generated podcast that I friend made by crawling my web site. I decided to create an actual podcast for posting occasional audio files. I expect to post very sporadically. I’ve posted two audio files, and I have one more in mind to post some day. Maybe that’ll be the end of it, or maybe I’ll post more.

The first file I posted was the one from the previous post. The second was an interview I did with the late Sir Michael Atiyah.

Here’s the RSS feed for the podcast. You can also find the podcast via my Substack newsletter.