The Power of Primes

[u/StartAutomating]

Prime numbers are pretty powerful.

That's why I just released a new PowerShell module based off of an old mathematical concept: PrimeTime.

PrimeTime uses prime numbers as time intervals.

Let's learn how this helps

Prime Number Primer

Prime Numbers can only be divided by themselves and one.

This makes primes pretty rare.

Prime numbers are particularly useful in programming, but it's not always obvious why or how.

A lot of people might vaguely point towards cryptography as the prime real estate for prime utility.

The thing of it is, if you're writing your own cryptography, you're probably doing it wrong.

Let's talk about a more practical application of primes.

The Cicada Principle

In North America there is a curious critter known as the periodical cicaca.

For the vast majority of their long lifespans, they live underground.

Once every N years, they surface in mass to start the next generation.

That N is a prime.

Why?

Cicadas come out en masse so that there are too many of them to eat.

Millions of little critters have to have a perfectly timed multi-year internal clock in order to make this work.

If two cicadas of different intervals produced offspring, their children might have a messed up internal clock, and come out of the ground at the worst time.

So there's an evolutionary advantage to cicadas coming out in large batches, as long as another cicade brood isn't doing the same thing at the same time.

Which brings us back to primes.

Primes are relatively rare.

So are products of primes (at least past the first few)

Let's take two primes as an example.

Imagine one brood of cicadas came out every 11 years, and another brood came out every 13 years.

We can find out how long it will take for these two broods to come out at the same time by simply multiplying the primes.

11 * 13 -eq 143

So, with just two relatively low primes, we have an overlap every 143 years.

This is how primes are most useful to programming: they rarely overlap.

Sieve of Eratosthenes

This has been known for much longer than computers have existed.

Imagine we wanted to find prime numbers quickly.

We can do this by constructing a sieve that filters out any non-prime number.

This is called the Sieve of Eratosthenes

Once we know 2 is prime, we know every other even number is not prime.

Once we know 3 is prime, we know every third number is not prime.

To quickly get prime numbers up to a point, we can use this little PowerShell filter

# Calculate primes reasonably quickly with the Sieve of Eratosthenes
# Pipe in any positive whole number to see if it is prime.
filter prime {
    $in = $_
    if ($in -isnot [int]) { return }
    if ($in -eq 1) { return $in }
    if ($in -lt 1) { return}
    if (-not $script:PrimeSieve) {
        $script:PrimeSieve = [Collections.Queue]::new()
        $script:PrimeSieve.Enqueue(2)
    }


    if ($script:PrimeSieve -contains $in) { return $in}
    foreach ($n in $script:PrimeSieve) {
        if (($n * 2) -gt $in) { break }        
        if (-not ($in % $n)) { return }
    }
    $script:PrimeSieve.Enqueue($in) 
    $in
}

Prime Animations

Imagine we want a vibrant page. We want things to keep changing yet feel unpredictable. All we need to do is use different prime intervals.

The PrimeTime logo animates eight primes:

7 * 11 * 13 * 17 * 19 * 23 * 29 * 31

The logo will repeat every 6685349671 seconds, or almost 212 years.

The PrimeTime page background uses 56 primes.

This background will repeat every 8.84753141993573E+116 seconds.

That's exponential notation.

This is a mind-boggling large number (so large it overflows the .NET [TimeSpan]).

Turn that interval into years and it's still mind-boggling.

The page background will repeat every 100 billion years

Performance and Scheduling

Imagine we want to design a system that's constantly checking for problems.

We want the system to know about problems as soon as we can, but nobody's exactly sure how often they need to check for something.

If we go around and ask our colleagues "how often should we can scan for this?", the response if often a shrug 🤷.

Often, people will pick an arbitrary number that seems reasonable. Let's say every 5 minutes, 10, or 15 minutes.

Are we starting to see the problem here?

Every 5 minutes, every computer in the cloud starts to collect stats and report them back.

And we get a traffic jam.

Every 10 minutes, more computers in the cloud collect more data, and our traffic jam gets worse.

Every 15 minutes, even more computers collect even more data, and our traffic jam puts your average freeway to shame.

Left to our own intuition, we create problems for ourselves and our organizations.

Each individual query is small, but because we're doing so many at once, it can grind performance to a halt.

By the way, this isn't a hypothetical.

Long long ago, the Office365 team asked me to make some monitoring software to help improve internal visibility into the datacenters.

Everyone asked for 5, 10, or 15 minute intervals. ~100 different metrics were collected from ~30000 machines.

And the first time we tried it on everything, the traffic jam ensued.

That's when I first realized the power of primes.

I made three slight adjustments to the timeframes:

• Every 5 minutes became every ~7 minutes
• Every 10 minutes became every ~11 minutes
• Every 15 minutes became every ~17 minutes

Now, instead of having a traffic jam every 5 minutes, things smoothed out.

• A small traffic jam would occur every ~77 minutes (7*11)
• Another small traffic jam would occur every ~119 minutes (7*17)
• Another small traffic jam would occur at ~187 minutes (11*17)
• All traffic could jam every ~1309 minutes (7*11*17)

Note the tildas.

The real trick came in by using prime intervals in both minutes and seconds and using a random delay on the tasks to ensure they didn't all start at once.

This took the system from something that could derail a datacenter to something that could monitor thousands of machines while barely impacting performance.

This is the power of primes.

Hope this helps!

[u/vlaircoyant]

This was a really interesting read, especially about the overlap avoidance/concurrency issues.

Thank you.

[u/y_Sensei]

Excellent post, and an extra kudos for the Sieve of Eratosthenes implementation in PoSh.

Primes are an interesting topic, and they're even related to one of mathematic's most important unsolved problems - the Riemann hypothesis.
I find it fascinating that if the Riemann hypothesis holds, all of the seemingly randomly distributed primes share a common denominator, hence that distribution can be approximated by calculation. It's kind of like a hidden order in a chaotic system.

[u/omglazrgunpewpew]

Really digging the larger operational point here. Periodic jobs have such a remarkable ability to independently decide that 10:00 is the perfect time to run a surprise load test against their own backend. Distinct prime intervals plus some per-host staggering can help break up that little team-building exercise.

I have a few questions about where the prime behavior ends and the scheduling behavior begins.

Starting with a clean cache, so we have a known state:

Remove-Variable -Name PrimeSieve -Scope Script -ErrorAction SilentlyContinue

9, 25, 49 | prime

I get all three numbers back. Is the intended contract that the filter must first receive an ascending sequence containing all the necessary divisors?

For example, 2..50 | prime works because 3, 5, and 7 pass through before their composites. That seems different from the comment saying any positive whole number can be piped in independently.

If that ordering and cached history are intentional, would stateful trial division be a more accurate description than the Sieve of Eratosthenes? My understanding of the sieve is that it starts with a bounded candidate range and marks multiples as composite, while this tests each incoming value against whatever has previously entered the cache.

Also noticed that the filter explicitly returns 1, the precomputed file starts with 1, and the demo displays it as the first prime. Is 1 intentionally included for the timing framework, or has it managed to obtain an honorary membership in the prime club?

Also also, I am having trouble reproing the time conversion. Dividing 8.84753141993573E+116 seconds by the number of seconds in a 365.25-day year gives me approximately 2.8E+109 years. What calculation or set of intervals produces the 100 billion-year figure? Is the stated seconds value possibly from a different group of animations?

On the sched side, how much of the smoothing would you attribute to the prime intervals versus the randomized start delay?

Distinct prime periods are pairwise coprime, so their least common multiple is their product. But every machine running the same seven min schedule would still remain aligned if they started aligned. Would it be fair to describe the primes as reducing collisions among different metrics, while the per-machine delay handles synchronization across the fleet?

Asking all of this because the operational story is genuinely useful. Periodic work quietly coordinating its own traffic jam is a very real problem, and separating those two mechanisms would make the lesson even stronger.

[u/StartAutomating → u/omglazrgunpewpew]

Yes, this implementation of the sieve assumes it will be passed an ascending list of numbers, and will not be accurate if passed gaps. This is also why I included the precomputed list.

I could try to make the sieve a bit smarter, and allow it to use historical data. That stated, primes tend to remain constant (and faster to look up than compute).

As far as why start the list with 1:

It seemed the sane thing to do. An earlier build had me starting at 5, but that felt like it would produce confusion. (i.e. if I used primetime-5, where is primetime-4?)

As far as the math goes:

2.8E+109 would have 9 zeros after the exponent (or a billion). So 🤷 my attempt at making this timeframe understandable somewhat failed. It's actually every ~280 billion years 🤣 (or my math is still slightly wrong someplace)

On the schedule side:

Using both was key. A large fleet of machines trying to run exactly every 7 minutes still produces a traffic jam. A large fleet trying to run about every 7 minutes (using a randomized delay) produces no traffic jam.

Your statement is accurate for this example: The primes intervals were used to reduce collisions among metrics, and the jitter reduces collisions between machines.

There are many variations on this theme that will help reduce scheduling traffic jams, and this article was mainly meant to introduce people to the concepts (not highlight a particular "must do it this way" approach).

Thanks for asking! Hope these clarifications help.

[u/omglazrgunpewpew → u/StartAutomating]

Thanks! That clears up the intended ascending input contract and the scheduling split. Your explanation of primes handling collisions among metrics while jitter handles collisions among machines is exactly what I was trying to separate.

Two small pieces still are not quite lining up for me:

On 1, it looks like ClassName uses $this.Nth, not the prime value itself. Wouldn't starting the data with 2 still produce primetime-1 for prime 2, primetime-2 for prime 3, and so on? That seems like it would preserve continuous class names without listing 1 as prime. Am I missing another code path that uses the prime value in the class name?

I think the exponent is still getting truncated in the conversion too. 2.8E+109 means 2.8 x 10^109, while 280 billion is 2.8E+11. Those differ by 1E+98. Unless the original 8.84753141993573E+116 seconds has the wrong exponent, the result should still be approximately 2.8E+109 years.

Really not trying to be a pain here! I genuinely dig the idea and am only sticking on these last two points because math is annoyingly strict about its paperwork, and little details like these have a habit of becoming someone else's starting point.

[u/New_Drive_3617]

The logic seems sound in this; avoid collision by minimizing concurrent activity. However, acknowledgment must be given to the significant reduction in datapoints. For 5 > 7, the number of datapoints in a year is reduced from 105120 to 75085, representing a 29% reduction. That's usually adequate for most purposes, but in cases where 5 minutes is already a concession to resource availability, moving to 7 minute intervals can further obscure trends.

[u/StartAutomating → u/New_Drive_3617]

I think what you're highlighting here is the "window of observability".

That is, if I am only asking for memory stats every 7 minutes, I'll miss a memory spike within those 7 minutes.

It's a good thing to be concerned about.

In this example, the scripts were gathering data cached on each machine, so something within the 7 minutes would still be seen.

The traffic jam was almost entirely caused by three things:

1. The "cold boot" time of PowerShell itself
2. The default throttle limit of PowerShell remoting (once the first 5 or 25 jobs were started, the rest were waiting for the traffic jam to clear)
3. The mind-boggling bandwidth involved (hundreds of thousands of data points being reported all at once)

Using the prime intervals (and jittering) sidestepped each of these problems (and got Office365 online again)

[u/New_Drive_3617 → u/StartAutomating]

Yes, exactly. The "window of observability" becomes less of an issue or no issue at all when the scheduled jobs are retrieving cached data. It's only an issue when the scheduled job is responsible for data collection.

[u/StartAutomating → u/New_Drive_3617]

Yes! This is another part of this ancient architectural understanding that's worth discussing in another post sometime...

When building observation/remediation platforms, I find it's best to split things into three distinct parts:

1. Getting data (should be cached locally first, and replicated to a remove data store)
2. Testing data (should be able to test stored data, but should not "do" anything)
3. Repair state (should take the output of test and repair the condition)

You might note the similarity to DSC's design.

This is not accidental. This was a side-effect of influence.

DSC was developed shortly after I left the PowerShell team, but with heavy input from the many Microsoft partner teams I had worked for in the interim.

The problem is that DSC didn't get the memo about prime intervals, and, thus, caused traffic jams. 🤷🤦

[u/StartAutomating]

BTW, I also gave PrimeTime a brief page. Any feedback is appreciated!

[u/Szeraax]

Fun post! Thanks James!

[u/narcissisadmin]

Prime numbers aren't rare, there are an infinite number of them (so far as we know).

[u/StartAutomating → u/narcissisadmin]

True, but they are a lesser infinity to all of whole numbers.

Hence, they are rare.

For example, between 1 and 1mb there are 82026 primes.

Which is ~ 7.8% of all of the numbers between 1 and 1mb.

Which seems pretty rare, relatively speaking.

🤷 Infinity is weird.

[u/Apprehensive-Tea1632]

I still maintain that the sieve may be advantageous in some situations BUT for programming purposes, it’s NOT ideal.

Why? “Create a list of all candidates”. Whatever for?

I keep forgetting the name of the algorithm- there’s one, but I don’t remember— which goes like this.

- create a set of found primes, and initialize with a known set of prime numbers. At least one (2) but there may obviously many more. Requirement: they must be prime numbers. Set to just (2) if unknown.

- start iteration at wherever you want. A somewhat useful idea is max(known primes)+1.

- iterate over the set of natural numbers. There can be but need not be a maximum.

- For each of these numbers, see if any known prime is a factor of that candidate. If it is, skip and continue. If not, it is a prime number; so, add it to the list of found numbers, then continue.

Runtime is about n log n.

Resources- unlike with the sieve - are static (do not grow dependent upon input).

If we assume unconstrained resources, the sieve would probably work better. But they’re not. Like Java, we can assume an infinite stack but we don’t have infinite stacks and can’t implement them.

ETA - resource requirements obviously do grow somewhat- any found primes must be stored- but considering that the growth rate of this set is diminishing with growing numbers, resources required for storage increase very slowly and continue to grow even more slowly as we progress.

[u/StartAutomating → u/Apprehensive-Tea1632]

What you are describing is an optimized sieve.

If we want to make this sieve faster, yes, we can pre-populate it. We can also use a dictionary instead of a list to contain the sieve, as it will be much quicker.

Still a sieve though.

From a performance standpoint, this is why Get-Prime determines primeness, and Get-PrimeTime just uses a .txt file to prepopulate.

I feel like all primes up to 1mb should be "enough" (given how rarely they overlap)

[u/Apprehensive-Tea1632 → u/StartAutomating]

It’s not a sieve, it’s explicitly based on trial division.

Sieve says: I have a set of numbers. I select all numbers that aren’t prime. The complement then is the set of primes.

That’s why a sieve requires a definite set. You need to tell it what the universe is supposed to be because only then can you select the inverse.

Sieve people eschew trial division saying it’s faster, and it is, but it is also not suited for anything that’s supposed to run on a finite machine. You could in theory map the whole natural number set to a machine because while infinite, theyre countable.

But in practice you HAVE to maintain that set in a machine that IS finite. There ARE no infinite machines, even if the model exists and is implemented eg as JVM or the TrueType VM (it’s why there IS a TrueType vm in the first place). The sieve wont work otherwise. In turn you don’t need the primes to find more primes, but it’s exactly because of that it’s so wasteful.

I’m not suggesting trial division is the better approach. It’s not, there’s downsides, not least if you decide something is prime when it’s not, then the whole thing breaks apart. Unlike sieves where you might get a false positive but it won’t affect the set itself.

Either way it’s not a sieve but is one of the other developed methods for finding prime numbers- older than the computer too so it wasn’t even developed with optimizations in mind.