Server Fault is a question and answer site for system and network administrators. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If I had access to potentially large number of CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped compute instances would perform efficient checks against the number in question with an assigned range of divisors (e.g. Instance 1: checks divisors 2-1000, Instance 2: checks divisors 1001-2000, ... etc.).


quickly means checking a single divisor against the 100 million digit number within 30-60 minutes.

efficient division means only checking the odd numbers up to the square root. Lower divisors would be only the known prime numbers to speed up computation.

1 CPU is the equivalent CPU capacity of a 1.0-1.2 GHz 2007 Opteron or 2007 Xeon processor.

Yes, I know there are better algorithms like AKS but I need to be able to divide the work among the mapped instances.

The better question to ask would probably be: what is the mathematical relationship between the number of CPUs and the amount of time it takes to verify a number of a given magnitude of digits?

I'm asking this because I am trying to figure out the number of Map_Reduce instances I would need to buy on Amazon AWS to make the computation feasible (a couple months/less than a year).

share|improve this question
Is it 100 numbers, each number with a million digits, or is it numbers with 100 million digits? Zypher's answer is still correct, but it might help to clarify. – Mark Henderson Jul 22 '11 at 22:12
Additionally, using a serial divisor strategy like this is hopelessly inefficient. I'm not a mathematician, but surely there are other methods of verifying prime numbers that can still be used with reduce? – Mark Henderson Jul 22 '11 at 22:28
@Mark; I'm sure he was just giving those ranges as a simple example. You only need to check the primes less than sqrt(n) as possible divisors. – Chris S Jul 23 '11 at 3:32
up vote 3 down vote accepted

There is no mathematical relationship. It entirely depends on your software, the architecture of the machine you are getting. What kind of RAM, Disk, exact CPU specs things like L2/3 cache can have a big impact on performance. Basically you'll need to do a reasonably scaled down benchmark, then crunch the numbers.

share|improve this answer

I totally agree with @Zypher but here is another idea for you. If you want to make this task cost effective you may consider using GPUs for it via CUDA, OpenCL and alike. Even though initial investment may be substantial it will be way cheaper in a long run then using Amazon.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.