### Humble Pie

## >> Friday, January 6, 2012

A few weeks ago, I had a great idea: write OpenCL code to test prime numbers and execute it on Amazon's GPGPU platform, which provides high-performance computing at low cost. Once I found the first prime with 100,000 digits, I'd win the EFF computing award and all the trappings of victory.

Rather than search for Mersenne primes with the Lucas-Lehmer test, I planned to test regular numbers with the new AKS method. I'd start with 10^{100000}+1 and continue on from there.

But as I read more about testing primes, I became interested in the underlying theory. I wanted to understand topics like congruence relations and the Prime Number Theorem. And why not? I loved writing the chapters on matrix operations and the FFT. How hard could number theory be?

Very hard, it turns out. I've spent days squinting at proofs of the Prime Number Theorem, and I'm still baffled. I could hold this book upside-down and understand the material just as well. There's nothing elegant or intuitive about number theory, especially when it involves integration on the complex plane.

So I'm giving up. I'm going back to evaluating NURBS with OpenCL-OpenGL interoperability. I don't want to read about zeta functions or Dirichlet series or the Abel summation formula ever again.

To those interested in implementing the AKS algorithm, here's a word of warning. At its theoretical best, the AKS algorithm requires O(log^{3}n) operations. If your system executes 1 TFLOPs/s, you can test a 100k-digit number in 1000 seconds, or about seventeen minutes. Not bad.

The problem is that, according to the Prime Number Theorem, the density of prime numbers near N is about ln(N). For N = 10^{100000}, you can expect to find one prime per 230,258 numbers. Taking away even values, a 1 TFLOPs/s system will require about *four years*.

Personally, I have better things to do with my time.

## 1 comments:

You were off by 3 orders of magnitude. Those are not 100k digit numbers they want, but 100M digit numbers!

Post a Comment