Faster LL-test Bounty Questions

[__HRB__]

I would like to know the following:

1. If the new code is 50% faster for 100M digit tests (333M bits), but only 2% faster for 10M digit tests (33M bits), would this still be considered a significant improvement?
2. What if speed-up is only achieved for a specific architecture (say for Core2s, but not for Phenoms or vice versa)?
3. How much does it count, if running the new code generates less heat and therefore would let currently overclocked systems be overclocked to higher levels (at which the current code fails)?
4. How much does it count if the new code is numerically exact, removing a possible source - however remote - of error and - unjustified as this might be - psychological uneasiness among the users?
5. Does the new code have to be - say 25% - faster today, or is evolutionary (in the order of 5%-25%) tweaking over time considered?
6. How much of a penalty is given towards implementations that must do several LL-tests (possibly very different in magnitude) in parallel to achieve maximum performance?
7. How much cash is currently in the pot?
8. Would it be part of the deal that taking the cash means even the non-GIMPS part of the code could not be published under the GPL?

[Uncwilly]

Originally Posted by __HRB__

If the new code is 50% faster for 100M digit tests (333M bits), but only 2% faster for 10M digit tests (33M bits), would this still be considered a significant improvement?

I think so, but it would not be used just yet.

What if speed-up is only achieved for a specific architecture (say for Core2s, but not for Phenoms or vice versa)?

I would think so, there are several code paths. Which machine it is running on will determine what code is used.

How much does it count, if running the new code generates less heat and therefore would let currently overclocked systems be overclocked to higher levels (at which the current code fails)?

I think little if any.

How much does it count if the new code is numerically exact, removing a possible source - however remote - of error and - unjustified as this might be - psychological uneasiness among the users?

If it can save x% of 'bad tests' then it is an improvement.

Does the new code have to be - say 25% - faster today, or is evolutionary (in the order of 5%-25%) tweaking over time considered?

Read the rules

How much of a penalty is given towards implementations that must do several LL-tests (possibly very different in magnitude) in parallel to achieve maximum performance?

Maybe none, it is through-put that counts.

How much cash is currently in the pot?

The EFF prize has to be paid first, but if cash is your only goal, look elsewhere.

Would it be part of the deal that taking the cash means even the non-GIMPS part of the code could not be published under the GPL?

I think that if the code helps to win the prize for the 100 million digit prime, then it has to be published. The license ???.

My personal thoughts. IANGW.

[__HRB__]

Originally Posted by Uncwilly

Read the rules

They're more guidelines than rules - otherwise they would have been more specific about various aspects. A sorting algorithm, for example is not an FFT, so if someone figures out a 20x faster way to square numbers based on sorting run-lengths of bits and some number-theory magic, then any lawyer could argue 'That's not an improved FFT!', but GW isn't a lawyer and his reputation is worth a good deal more than a month's pay.

Originally Posted by Uncwilly

The EFF prize has to be paid first, but if cash is your only goal, look elsewhere.

Didn't the EFF recently fork over $50,000.00 to GIMPS? Handing out prizes for the development/discovery of faster transforms discourages people from starting YAGIMPS, offering 75% of the booty and making GIMPS technically and incentive-wise obsolete.

I like challenges. For example, according to this, the Intel MKL computes single precision low accuracy logarithms in 5.9 clocks/float on a 45nm C2D. This proof-of-concept code I wrote does the same in 4.8 clocks. Admittedly, computing low accuracy logs in record time isn't the most prestigious thing, but I'm pretty certain Intel didn't hire some Dodo to write the code, and 5.9 clocks was *very* tough to beat - it took me a couple of months until I finally figured out a way to do it (without using large tables even!). Some people do crosswords, some do Sudokus, I do this sort of thing in my free time, and if someone offers cash as a perk, why not ask about the specifics?

As you can see from the way my website is maintained, I'm not very likely to start YAGIMPS or something, since this would require real work, but if someone starts YAGIMPS ... I can't see what's so special about this place - it certainly isn't the devotion to tolerance and the freedom of expression - that would keep people from switching.

[Uncwilly]

Originally Posted by __HRB__

Didn't the EFF recently fork over $50,000.00 to GIMPS?

Nope, read their site:
http://www.eff.org/awards/coop
http://w2.eff.org/awards/20000406_coopaward_pr.html
It didn't go to GIMPS and the award for the 10,000,000 digit hasn't been announced.

[__HRB__]

Originally Posted by Uncwilly

Nope, read their site:
http://www.eff.org/awards/coop
http://w2.eff.org/awards/20000406_coopaward_pr.html
It didn't go to GIMPS and the award for the 10,000,000 digit hasn't been announced.

Huh? Did I miss something? This press release (http://mersenne.org/primes/m45and46.htm) appeared a year ago. At 4% interest p.a. that's $4000...strange.

I also found this: http://prime.haugk.co.uk/prize.asp (http://www.mersenne.org/prize.htm is 404), stating:

George Woltman will be the sole determiner of whether a suggested breakthrough will be implemented, how it affects throughput, and the dollar amount to be awarded.

Which is why I had asked the questions about some finer details in this post. It is obvious to George that beating his floating point FFT implementation with a floating point FFT is pretty hopeless, so the question is how he would honor the feat of beating an FFT that uses specialized 64-bit double precision instructions with a something that uses plain 16-bit multiplies, even if it is only by 15%.

Originally Posted by lfm

Its not clear here what code you are talking about. Is this something you are working on yourself or is this just hypothetical questions?

There is another thread I had started a long time ago with many suggestions by people of how one might 'reasonably deviate from the beaten track' to see what could do the trick. The key insight is: for an all-integer transform using SSE2 to be competitive, one must avoid 64-bit arithmetic (which also rules out the pmuludq instruction, which delivers 64-bit results and requires a lot of shuffling that blocks execution units for arithmetic).

Originally Posted by lfm

It would be nice of course but most speedups actually make the machine work harder and generate more heat so it would be rather surprising also.

Not really. A floating point multiply generates much more heat, than a logical shift. Split-radix floating point FFTs (with complex multiplies coded as 4/2, see e.g. http://cnx.org/content/m12031/1.5/) do one mulpd every other cycle, whereas the Schoenhage-Strassen algorithm doesn't need any at all! The horse I'm currently betting on, would ideally issue three 16-bit multiplies every 4 cycles, each of which has the complexity of ~1/3rd of a 53-bit floating point multiply.

Originally Posted by lfm

I'm not sure I understand this question. Multi-core machines are still subjects of much investigation for many scenarios.

Not so sure I did either!

The idea was that, because optimizing for power-of-two transforms is easy, one could try to fill up the 'free' bits with different tests and compute the squares mod(p1*p2*....*p3)...

Originally Posted by lfm

I don't think the prize money has anything to do with the GPL.

The prize money might not, but IFAIK the current FFT code is open source but not free as in freedom, so George might insist on attaching strings, which some people might find objectionable enough to tell him to 'go climb a tree'.

[Prime95]

Originally Posted by __HRB__

Huh? Did I miss something? This press release (http://mersenne.org/primes/m45and46.htm) appeared a year ago. At 4% interest p.a. that's $4000...strange.

Two major hurdles had to be cleared. One, we had to incorporate as a 501c3 charitable corporation. If we hadn't the $100000 would have ended up on my tax return - no thanks. Two, EFF requires an article published in an refereed academic journal. Turn-around time on this can be a little slow. The good news is both steps have been completed. Could we have done it faster? Yes, I probably procrastinated a good 3 months before writing the Journal article. Sorry.

I also found this: http://prime.haugk.co.uk/prize.asp (http://www.mersenne.org/prize.htm is 404), stating:

Sometime last year the $10K award for algorithmic improvements was discontinued. See http://web.archive.org/web/200805141....org/prize.htm.

Even if it hadn't been discontinued, your ideas would be too late to be eligible for part of the $100K award (as you pointed out M45 was found a year ago).

It is obvious to George that beating his floating point FFT implementation with a floating point FFT is pretty hopeless, so the question is how he would honor the feat of beating an FFT that uses specialized 64-bit double precision instructions with a something that uses plain 16-bit multiplies, even if it is only by 15%.

I do think my floating point FFT code can be beaten. I'm working on several ideas right now. Nothing radical, small improvements add up.

If you can beat prime95, you will earn everyone's respect. I'm sure many would switch to your program. You could either form YAGIMPS and attack the $150,000 EFF prize or you could negotiate with the GIMPS, Inc. board of directors for compensation in return for using your code.

... many suggestions by people of how one might 'reasonably deviate from the beaten track' to see what could do the trick. The key insight is: for an all-integer transform using SSE2 to be competitive, one must avoid 64-bit arithmetic (which also rules out the pmuludq instruction, which delivers 64-bit results and requires a lot of shuffling that blocks execution units for arithmetic).

These are interesting ideas that deserve to be explored. They could have applications to fields other than prime hunting. Alas, I cannot recommend doing further work if your sole goal is monetary gain from prime hunting. If I pocketed the entire $100,000 EFF award, considering the 12+ years of work the hourly wage would be quite low.

but IFAIK the current FFT code is open source but not free as in freedom, so George might insist on attaching strings, which some people might find objectionable enough to tell him to 'go climb a tree'.

The only real restriction on the code is if you use it to find a Mersenne prime, you have to obey the GIMPS prize rules. I'm no lawyer, but I felt that a GPL license could allow an unscrupulous prime finder to claim the entire EFF award. I also dislike the GPL for other reasons, but that's a different matter.

[__HRB__]

Originally Posted by Prime95

I do think my floating point FFT code can be beaten. I'm working on several ideas right now. Nothing radical, small improvements add up.

You're right, I totally ignored the newly discovered 'Tangent FFT'-trick, since it didn't knock off enough multiplies to turn around dominated code. If split-radix in GF(p^2) is slow, then the 'Tangent FFT' equivalent will not be much faster.

Originally Posted by Prime95

If you can beat prime95, you will earn everyone's respect. I'm sure many would switch to your program. You could either form YAGIMPS and attack the $150,000 EFF prize or you could negotiate with the GIMPS, Inc. board of directors for compensation in return for using your code.

Should I succeed, I wanna T-shirt. And a poster. And a membership in the country club. And $10.000.000 in government funding, because it's healthy:

Diet-Prime95 - now 99.9% floating-point free!!
Diet-Prime95 - only 2 fmuls per iteration!

One major problem would be that any new code would also need to be maintained and pampered with the same love prime95 is currently receiving, which is much less fun than razzing a 12-consecutive-year record holder and moving on.

Originally Posted by Prime95

The only real restriction on the code is if you use it to find a Mersenne prime, you have to obey the GIMPS prize rules. I'm no lawyer, but I felt that a GPL license could allow an unscrupulous prime finder to claim the entire EFF award. I also dislike the GPL for other reasons, but that's a different matter.

IFAICS, the current rules don't prevent anyone from running prime95 and doing a second computation with glucas on a 20x faster machine, should prime95 score a hit. If this anyone uses TOR network to get exponents, you'd also have a hard time proving that the same exponent was not coincidently handed out to some anonymous computer a couple of months before, even if manual assignment wasn't possible.

I think these restrictions are unnecessary, as prime95 users are probably more decent than the average person, so keeping the overall status secret and mandating a public-key cryptosystem - complete with key-signing parties and penalties for making untested exponents public, in order to be sure which exponents were handed out to whom - would drive away a lot of computing power, because of the implicit assumption that every user is a potential crook.