RSS 2.0
2010.10.24. 20:43
Blog Weekend - Mind experiment with a javascript prime checker and distributed computing
The most basic way of checking if a number is a prime number is to divide the number with all the numbers starting from 2 to the square-root. If there is no remainder, the number is a prime.
function checkIfPrime(n){ for(var i = 2; i <= Math.sqrt(n); i++) if(n % i == 0) return false; return true;}
where % is the modulo. a % b gives the remainder of 'a div b', where div is the integer division. 6 % 5 gives 1.
Javascript's number is a double precision floating-point format, which has an approximately 16 decimal digit integer precision 1.
After some tests, we can state, that in javascript 15 digit integers can be used without a problem. Therefore we take this limit to play with, our first attempt will be to calculate all the prime numbers up to 15 digits.
Looking the prime checker code above, we can immediately make some optimizations.
function checkIfPrime(n){ if(n <= 1) return false; if(n == 2) return true; if(n % 2 == 0) return false; var a = Math.sqrt(n); for(i = 3; i <= a; i+=2) { if(n % i == 0) return false; } return true;}
Changes:
1. store the square-root in a variable instead of the loop condition
2. not to calculate at all if the number is
a. equal to or smaller than 1 (primes start with number 2), return false
b. equal to 2, return true
c. even, return false
3. loop goes from 3 and jumps with a unit of 2 (odd numbers)
Okay. Let's check this function for the highest 15 digit number.
Note: to find this, we've put a loop together, starting at the highest 15 digit number (999.999.999.999.999), and started to step back on the numbers. This way we found that the highest 15 digit prime number is 999.999.999.999.989.
Now, how much time do we need to validate this number? On my computer (an average/low class computer), testing with Google Chrome (6.0.x), I got these results:
3498, 3405, 3375, 3531, 3609, 3547, 3509, 3532, 3483 ms.
The mean of this is 3498.78 ms, standard deviation is 67.57 ms. So it takes about 3 and a half seconds (*) to calculate. Interesting, that in Mozilla Firefox (3.6.x) it takes 1 second(!) less. Internet Explorer (8.0.x) asked me if I want to stop running the code as it can slow down my computer.
(* think about this result. 3.5 seconds for a 15 digit prime. not bad, not bad at all!)
We will use the 3498.78 +/- 67.57 ms value as an upper bound for one calculation. If we say, that for every number this time is needed, then we can tell the maximum time needed to check all the numbers in the set, if we multiply this time with the amount of numbers.
We have to know how many odd numbers do we have between 3 and the last 15 digit number. The serie is an arithmetic progression, it is widely known how to handle this. The first element is 3, the last one is the last 15 digit odd number, the difference is 2. Therefore:
a(n) = a(1) + (n - 1) * d,
where a(n) is the n-th element of the serie, a(1) is the first one, n is the number of elements (the index of a(n)), d is the difference. So we get the formula:
n = {a(n) - a(1)} / d + 1.
Putting the exact values into this forumla we get:
n = {(999.999.999.999.999 - 3) / 2} - 1 = 499.999.999.999.997, as the amount of numbers to check.
This is a nice amount. We have to check all of these numbers. Now we can calculate the total time.
T = n * t, where T is the total time, n is the n above, t is the time to check one number. Using the values:
T = 499.999.999.999.997 * 3498.78 = 1.749.389.999.999.989.503,66 ms
= 1.749.389.999.999.989,5 seconds
= 29.156.499.999.999,83 minutes
= 485.941.666.666,66 hours
= 20.247.569.444,44 days
= 55.472.792,9 years.
We used '1 day = 24 hours' and '1 year = 365 days' instead of the solar time precision (and also we didn't take leap-years).
This is good, but what does this mean? This means, that if we use the function above, it takes about 55 and a half million years to calculate the prime numbers up to 15 digits. Note that this time equals the time of the Jurassic Period of the Mesozoic Era 2 (you probably remember the dinosaurs). Even though this is an upper bound, we somehow feel, that this is not so good.
Of course these calculations are HIGHLY theoretical and used to represent a huge set.
1.) We gave the upper bound of the calculation time
2.) AND we also said, we want to calculate the primes up to 15 digits (huge amount).
3.) with javascript.
Since this is a Blog Weekend post, we can give some tips on how to reduce the time needed.
Today the obvious way of such an impossible calculation is using the power of distributed computing. Basically you get a bunch of computers and divide the whole task to smaller parts. Each unit connected to this network calculates its own - smaller - task. Since this article is about javascript, why not to imagine to put this function on a website? Remember that this is a mind-experiment, we do not advise you to do such a network in real life. Why not? Because for the case above, to reach a human-related time, you would need a 100 webpages with 1 million visitors on each. This way you could reduce the time needed to 0,55 years = 200,75 days.
But still, you can see that even such a fairly impossible task can be done. Even using javascript. Thinking in such a massive set is not realistic, but the point is that it is solvable in a finite time. The solution for the impossible is not so far away.
The example above is not likely useful, but points on the options of hobby-distributed-computing. Change the task, change the numbers and you will get a more efficient result for your own project.
Other thoughts:
1.)
Since this article is not about hacking or codebreaking, even though it is highly connected to this topic, we write these notes here:
a.) If you embed such a code into your application always make sure you let the user choose to use it.
b.) Do not hide codes in your application which are not related to the purpose it was written for. Only the most necessary functions must be used.
c.) "Only the most necessary functions must be used" does not involve code optimization, when the programmer does not fully optimize the script.
It's not very ethical (nor nice), if your user goes to your 'picture gallery' and in the title gets a message "Congratulations! You calculated the 1596-th Prime number for us!". People don't really want to join distributed processes without knowing about them.
2.)
The idea is not without precedents. They say, that to get into Edison's lab (a barn) was really hard. Even young fellows could hardly open the door to meet the Master. But the secret was brilliant: opening the door launched a machine, which pulled 5-10 buckets of water up from a well. Edison used the work of visitors to water the animals.
3.)
This distributed computing area via the browser is an even more complex question. Today if you go to a popular site, for sure your browser will load tons of ads. This is good, sites have to earn money and give it to the poor. But anyways, you browser always loads "more", than you wanted your browser to download and display: these are ads, they are already there. What if - in your mind - you change the ads to scientifical calculations working in a grid? Yes, you can see the land of Utopia now, but who knows. Maybe every second advertisement could be a scientific calculation. Your computer overworks anyways. These calculators could find the next solution to the next 'World-Equation'.
4.)
Or similar to "Donate for Us", why not to use a "Calculate for Us" button? Clicking on this button you would lend your computer for a calculation while reading the news on the web.
Further pages and sources:
1.)
You can play with the calculator written for this article. There are other functions as well: list primes smaller than a number, or get list of first n primes, get list of primes with n digits. It uses javascript (client-side calculations). Experimental version.
2.)
Prime numbers on Wikipedia: http://en.wikipedia.org/wiki/Prime_numbers
3.)
The Prime Pages by Chris K. Caldwell, The University of Tennessee at Martin: http://primes.utm.edu/
A really good website about prime numbers. Check the page http://primes.utm.edu/notes/conjectures/ for 'Prime Conjectures and Open Questions'.
4.)
Illegal primes on Wikipedia: http://en.wikipedia.org/wiki/Illegal_prime
An interesting side of prime numbers.
Sources:
