The prime-crunching on dedicated hardware FAQ

[Prime95]

Originally Posted by jasong

Would this forum like to challenge me to write a number-testing program for graphics cards?

Yes. Tell us how long your program takes to test a 10 million digit number. It shouldn't take you long to write, say two or three months. And please make source code available. Enjoy.

[Uncwilly]

I am willing to throw in a few bones.

[Xyzzy]

The snake can arrange admittance to the "David Hasselhoff" forum if he succeeds.

Certainly a privilege of this magnitude trumps anything anyone here can hope to offer.

Snake1: The terms of the wager are the ones listed by Paul.

[jasong]

Originally Posted by Mini-Geek

I'd be happy to donate, say, $10-$20 (US) to the genius programmer.

I didn't quote this for the money promise, I don't care about that, but I wanted the quote to make sense without me having to add words.

Anyway, I'd just like to say up front that one of the reasons I feel the need to complain about this is because it DOESN'T take a genius programmer to make better LLR code on a graphics card. My friend made the code himself(he's suffered a hardware crash since then, so I'm on my own) and I believe simply porting the FFT algorithm to a graphics card is enough to prove the potential for number proving. (1) Because graphics cards have the ability to transfer an insane amount of data, and (2) because of the nature of the problem, you're basically doing the same task millions and millions of time. It's like the difference between line-dancing and being told they're going to pick a totally random song and you have to come up with something that's worthy of a well-rehearsed professional. Graphics cards are made for shuffling data and basically dealing with pure math, while cpus are made under the assumption that there's no way of predicting what they're going to be asked to do, so they're made as general purpose as possible. The fact that graphics cards can do FFTs this well is either a coincidence(yes, I do intend to prove that my suggested coincidence actually exists) or indicative of some profound truth about the universe.

As Einstein(I think it's Einstein) would say,"The universe is pure math. If the basic premise behind a proposed theory is too complex to be explained to a young child, the theory is either wrong, or overly complex." Of course, this doesn't mean that the final Theory of Everything will be totally obvious, just that the basics of the theory will be simple to explain. It's like the Mandelbrot Set, the equation is incredibly simple, but the solution is simply incredible.

(Feel free to split this off into another thread, since it's obviously gone off-topic)

My plan is first to get some good Linux programming books and learn the basics of programming and compiling. Also, I need to research the specifics of the FFT algorithm. After that I'm going to need to get some of the basic code for an FFT implementation. My friend has a preference for an implementation that isn't GW's, it runs better on AMDs, and I think Intels, too, not sure about that second part. The basic skeleton of everything is something I will try really hard to keep, no reason to start totally from scratch. (If I borrow code, I guarantee the creator will get credit) My long-term goal is simply to get it running on a graphics card. (I've also heard that Ipods have pretty good graphics processors, the video ones anyway. I'm going to have to see if there's too much extra complexity to get them involved) After I've proven their potential, and I believe successfully processing a number in a way that's duplicatable and results in the same type residue(that 64-bit double-check code) than things will accelerate, because real programmers will have had it proven to them that graphics cards kick butt at performing FFTs, double-precision or not. And then, BOOM, we'll go from maybe having a 10M-digit prime at that point to having the potential for a 100M within the year(365 days) after it goes into beta.

[Mini-Geek]

So stop typing text and start learning and typing code. I really hope you're right. I just really don't think so.

[rogue]

Originally Posted by jasong

My friend has a preference for an implementation that isn't GW's, it runs better on AMDs, and I think Intels, too, not sure about that second part.

You imply that your friend has written such an implementation and that it is faster than Prime95 (regardless of whether it runs on GPUs). If it is so good, why isn't he making his software public?

Also, just because GPUs are fast doesn't make them practical for this problem. They are better for highly parallelized operations. There are limits to how much parallelization can be done with an FFT because each iteration is dependent upon the results of the previous iteration.

Of note, jasong also posted on Primegrid a long time ago that this friend had won the $100,000 prize, but hadn't submitted his prime. It sounds like Grigory Perelman. Anyways, neither jasong nor his mysterious friend ever backed up their words with any proofs or examples.

I'll leave it up to someone else to rate jasong on Bob's crank-o-meter.

[wblipp]

Originally Posted by jasong

simply getting the program to run on a graphics would take one most, if not all, the way to proving the whole double-precision theory wrong.

Originally Posted by xilman

LL-test a prime exponent in the range 30M to 40M

Originally Posted by jasong

I believe simply porting the FFT algorithm to a graphics card is enough to prove the potential for number proving.

"If the basic premise behind a proposed theory is too complex to be explained to a young child, the theory is either wrong, or overly complex."

Jason,

Perhaps your friend got a single precision FFT to work on a GPU - and perhaps you can, too. There are some interesting and useful things that could be done with that. But LLR testing of exponents in the 30M to 40M range isn't one of them. There is a simple mathematical explanation. It's been explained in this thread.

In long hand multiplication, you get columns of numbers. In long hand we do he sum and carry processes jointly. That is, we start at the right, and proceed one column at a time. We add up the column, then determine the carry and use that as part of adding up the next column. But when using FFTs, the add and carry processes happen separately. The result of the FFT is the sum of every column. After the FFT stage we calculate the carries. The problem is that we need to know the FFT output - the sum of the each column - to the exact integer.

There isn't anything magical about the base 10 used for long hand multiplication. The same process works in any base. So one of the decisions you make in FFT is what to use for the "digit size." A big digit size means fewer total digits, hence fewer rows to add up. So for small numbers you pick big digits, and things go pretty fast. But as the numbers grow, at some point the column totals are too big to exactly recover the integer. When this happens, you have to reduce the digit size. This makes more rows, but the numbers in the rows are smaller, so you can once again use the column totals. As the numbers get still bigger, you need still smaller "digit size."

But you cannot keep reducing the "digit size" for ever - it is impossible to go below 1 bit. And even at the smallest digit size, there is point where the column totals cannot be figured out exactly. When you use single precision numbers, that limit happens before you get to exponents in the range of 30M to 40M. The only way to make FFTs work in this range is to have bigger numbers to hold the column totals - hence the need for double precision.

Summary
1. Single Precision FFTs on a GPU are useful, but not for GIMPS.
2. The simple mathematical reason is that single precision cannot hold the column totals of the multiplication to sufficient precision.

[Uncwilly]

Originally Posted by jasong

My plan is first to get some good Linux programming books and learn the basics of programming and compiling.

Linux, like windows, is an operating system, not a programming language.

What language are you going to program in? UBasic, Fortran, C++, ASM, HAL/S, Logo, Cobol, Snobol, Forth, Lisp, Python, Pascal, Ada, or something else?

[xilman]

Originally Posted by Uncwilly

Linux, like windows, is an operating system, not a programming language.

What language are you going to program in? UBasic, Fortran, C++, ASM, HAL/S, Logo, Cobol, Snobol, Forth, Lisp, Python, Pascal, Ada, or something else?

Be fair to the guy. He clearly meant programming in a Linux environment.

I've seen {Linux,Windows,Mac} programming used many times by smart and literate people. It's always been clear what was meant.


Paul

[Mini-Geek]

Originally Posted by wblipp

But you cannot keep reducing the "digit size" for ever - it is impossible to go below 1 bit. And even at the smallest digit size, there is point where the column totals cannot be figured out exactly. When you use single precision numbers, that limit happens before you get to exponents in the range of 30M to 40M. The only way to make FFTs work in this range is to have bigger numbers to hold the column totals - hence the need for double precision.

Summary
1. Single Precision FFTs on a GPU are useful, but not for GIMPS.
2. The simple mathematical reason is that single precision cannot hold the column totals of the multiplication to sufficient precision.

So, if single precision reaches it before the 10M digit range, when does double precision reach its limit? Are we going to need triple or quad precision CPUs to search for primes once we get into higher numbers? When will that happen? Or am I misunderstanding something where this is wrong?
Also, if he writes something that can't run on the 10M digit GIMPS range but can run k*2^n+-1 for relatively small numbers (n needs to be larger than ~340K to place in the top 5000 list), could it be faster than LLR is for those sizes? Maybe for even smaller numbers? Anything faster at practically any range would be useful, maybe not to GIMPS, but maybe to other projects.

[retina]

Originally Posted by jasong

My friend made the code himself(he's suffered a hardware crash since then, so I'm on my own) ...

It is curious how all of your "friends" end up either ill or in general have some sort of problem that prevents them from ever actually proving their claims.