82000: Episode III - Revenge of the Nerd

This is the third post in a little series about the sequence

2, 3, 4, 82000, ….

My first post explains what the definition of the sequence is. My second post introduces the code I wrote to try and find the next integer in the sequence. Here’s a link to the code again for reference.

This post is going to talk a bit more about the code details, and how it does what it does. It’s important to look at my second post before continuing here.

Program scaling

Since the numbers I’m checking are currently around 14 million digits long, we need to utilize the GNU Multiple Precision Arithmetic Library. Furthermore, I have parallelized the code using OpenMP, and the code is running on my desktop with 20 threads. Unfortunately, I still need my computer for actual research, so I’m running the code with a nice value 19, which means that the operating system will give my executable essentially the lowest priority compared to all the other tasks I’m running.

Nevertheless, for most of the uptime, I’m actually using 20 threads so I have nice timing information. One diagnostic I print is the number of digits in base 10 that I’m currently looking at, as well as the amount of time the executable has been running in seconds. Here’s the plot:

This is an interesting function. I want to be clear that the vertical axis shows the number of digits in the numbers being checked, so it’s actually $\log_{10}$ of the actual value of the digits.

I can fit a simple function to this data, and it looks like this:

Ignoring the coefficients, the function scales as:

$$n(t) \propto \sqrt{t}$$

and it seems to fit ok, especially at later times. The residuals are probably large, but the late time behavior is decent. What we care about in programming is how things scale in the late time behavior anyway. What I am interested in is, giving a number with $n$ digits, how long does it take to check the number? Taking the time derivative gives me:

$$\frac{dn}{dt}(t) \propto \frac{1}{\sqrt{t}}$$

If I convert this to a function of the number of digits, I get a nice result:

$$\frac{dn}{dt}(n) \propto \frac{1}{n}$$

This means that the problem scales linearly with the number of digits, or the rate of checking all the guesses at a certain number of digits goes inversely as the number of digits, as expected.

There are two factors at work here. One is noting that to check every digit of one guess, even for every base, should be a linear operation. The other is looking at how many numbers we have to check for a given number of digits. Considering 3 digit numbers, we see there are 900 of them, ranging from 100 to 999. 4 digit numbers range from 1000 to 9999, so there are 9000 of them. We see that there are 10 times as many numbers to go through when we increase the number of digits by 1!

Why doesn’t this affect the scaling? The important trick is that we employ a number skipping algorithm, discussed in post two, where once a guess fails in a given base, we choose the next largest number that satisfies the check in that base as our next guess. The way we choose our next guess skips a number of numbers that is proportional to the size of the number! (The last sentence is a mouthful, but it’s important to the analysis)

For slightly more math, in base 6, if the digits are random, we have a probability $P = 2/3$ of terminating on a given digit, since we found a digit we aren’t allowed to see (2,3,4,5 instead of 0,1). So what’s the expected number of digits we check if the number had an extremely large number of digits?

$$<n> = \sum_{i=1}^{\infty} nP^n = 6$$

This means that even for large numbers, we expect to only check 6 digits in base $6$. In other words, we don’t check $n-6$ digits, and our skip size must be larger than $6^{n-6}$. Finally, comparing the size of the number we check ($6^n$) to the skip size, we get:

$6^n / 6^{n-6} = 6^6$.

Therefore the skip size is proportional to the number we’re checking for large numbers. This explains why the scaling is unaffected

Threading

So how about the threading? First we start with some number of digits for a guess, and store it in $n_{current}$. Every thread will grab a range of numbers, ranging from $n_{current}$ to $n_{current} + n_{check range}$, then increment $n_{current}$. The thread will check all the guesses in that range, then grab a new range of numbers to check. This strategy is quick if $n_{check range}$ is large enough that:

1. Threads aren’t constantly in the thread critical section where $n_{current}$ is updated
2. Threads will eventually guess a number which is outside their range of number of digits, in which case we ignore the guess and grab a new range of digits

In my code, I have set $n_{check range}$ to 1000 binary bits, or about 300 decimal digits. Is this choice large enough? Further, is this algorithm going to stay stable, such that the number of guesses within the $n_{check range}$ digits stays constant?

Above is a plot showing the size of the number on the vertical axis (in number of base 10 digits $n_{current}$), against the number of checked guesses in that range of numbers. What we’re seeing is that the number of guesses we’re checking is constant with the size of the numbers we’re checking! This is consistent with the fact we established that the skip size is proportional to the value of the number being checked. Further, we see that we’re checking around 1000 guesses on each thread before grabbing a new set of numbers. This should be sufficiently large that we’re not spending all our time in thread critical sections.

This shows that the threading algorithm is stable, and everything is going as expected!

How I check digits

As for how I actually check each digit, I use a temporary integer that is essentially a mask. For an example to help illustrate what’s going on, let’s consider the number 48 in base 10, or 120 in base 6. We first want to check the largest digit in base 6 to make sure it is a 0 or 1. My mask starts at 100 in base 6 (but is stored as simply 36 in base 10. Whenever the mask is larger than the guess, we know that digit of the guess is a 0, and we move the mask to the next smaller digit (more to come later).

When the mask is smaller than or equal to the guess, we know that digit of the guess is a 1 or larger, so we do $guess = guess - mask$. In this example, guess is now $120 - 100 = 20$ in base 6. At this point, we compare mask to guess again, and if the mask is still larger, we know that the guess’s digit was a 2 or larger! Otherwise, as is the case here, the digit was a 1 exactly.

Now we must move the mask one digit smaller. We do this by dividing the mask by the base. In base 10, the mask was 36, now it is 6 (which is 10 in base 6). This integer division can be performed very quickly with the proper GMP function call, since we know the division is exact.

Let’s continue the example. Compare the guess to the mask, and find that it’s larger. Subtract off the mask so the guess is now $20 - 10 = 10$ in base 6. Compare again, and the mask is still smaller than or equal to the guess, meaning the digit was a 2 or larger! Now we can stop and generate a new guess.

This prescription is decently fast since we do not actually convert any part of the number into the base, it stays in base 10. Since we don’t do the conversion, we must use this mask technique which uses fast division, subtraction, and comparisons.

That’s it

By the time I finished the post, I’m currently at around 15 million digits. If I get too bored or I find the next number, I’ll report back here! If you have, thanks for making it this far!

---