Timing is Everything

While contemplating the feasibility of my most recent project (the microcontroller-powered prime number generator featured in the previous entry) I began to wonder exactly how efficient the current design is. The same chip doing the math is also running a fairly complicated 9-layer multiplexed display. I toyed with the idea of utilizing two microcontrollers – one to handle the display, and another to be the mathematical powerhouse. Theoretically this would be a very efficient way to display data on an LCD, because all of that processing power required to send parallel data to the display could instead be devoted to calculation. However, the bottom line is that in order to accurately determine the best setup for my needs, I need to first determine what my needs are!

Here’s a simple question: “How many calculations will be required?” In other words, if I’m counting from 1 to 2^25 (33.5 million), dividing each number by every integer between 2 and its square root, by the time I get to the end how many calculations will I have run? If I can determine the speed at which the microcontroller calculates divisions I can multiply it by the number of required divisions and have an estimate of how long (years?) it will take to reach 2^25. Finally, a use for basic calculus! Let’s assume that no numbers are eliminated, and every test number is divided by each integer between 0 and its square root. Therefore the number of divisions for each test number (Phi, the squiggly line) is its square root. Summing up the square roots of Phi from 0 to 2^25 requires simple integration:
prime_euqtion

Alas! It appears that approximately 388 billion calculations are required. Let’s round down to 300 billion, considering that many of these numbers are not prime and will be excluded quickly. I know this is a rough estimation, but at least it’s numerical! Before I did the math, my only guess would be “a really big number”. Now, let’s guesstimate some efficiency. If my previous project (with the LCD screen) didn’t require parallel communication with the display and could concentrate just on the path, I’m guessing I could do 1,000 divisions a second. At that rate, 300 billion divisions would take 3472 days (9 and a half years). Yeah, I think that’ll keep me busy for a while. How awesome would it be to wait around for a decade and actually be there watching when it finishes! I wonder if it would accurately loop around to 0, or crash… I’ll have to try it to find out. Look me up in 10 years.