Distributed Beal Conjecture Problem

[CRGreathouse]

It just consumes all system RAM (> 2 GB with paging) and makes the system unresponsive.

[Joshua2]

Ok, it should just use a tad over 1gb. I can't really troubleshoot it. I'm working on making it more user friendly with resuming and checkpoints right now.

[Joshua2]

New bealconjecture 1.1 out! It includes changelog, but adds full threading support choice and checkpointing.

[CRGreathouse]

Originally Posted by Joshua2

Ok, it should just use a tad over 1gb. I can't really troubleshoot it. I'm working on making it more user friendly with resuming and checkpoints right now.

Version 1.1 acts the same: no CPU activity, all system memory consumed. I was using

mono BealConjecture.exe 4 1 500

for my quad core Phonom 2.

[Joshua2]

Do you know if there is something I am supposed to do different than visual studio to make mono work? I don't know why it works for win x64 but not linux /mono if its supposed to work. Maybe its a 32 bit app, in which case it wouldn't work is all I can think of. I don't suppose giving anyone the source code could help?

[lavalamp]

I'd be willing to put some CPU time on this once the LLRs I'm running finish in about 11 days. I do have a couple of questions though.

The first of which is how does your program choose which combinations of numbers and powers to output for PARI to check? I assume there is some mathemagical trickery going on to sieve out most combinations.

If the program is stopped, all progress is lost, could the program be made to carry on from where it left off with the aid of an occasional checkpoint file?

Could you extend the number of threads allowed? With up to 8 threads I could take advantage of hyperthreading, and RAM usage is not an issue for me. In my case, double the threads wouldn't double the speed, but it would surely give it a boost.

I've attached a zip containing a couple of images so you can see the iteration times. I tried to start it with 8 threads, but it only spawned 4, I manually assigned affinity to cores 1, 3, 5 and 7 to get the best speed out of it. I'm clocked at 4,158 MHz.

[Joshua2]

Originally Posted by lavalamp

The first of which is how does your program choose which combinations of numbers and powers to output for PARI to check? I assume there is some mathemagical trickery going on to sieve out most combinations.

If the program is stopped, all progress is lost, could the program be made to carry on from where it left off with the aid of an occasional checkpoint file?

Looking forward to your contributions. What cpu do you have? An overclocked i7 (I'm interested in cache sizes influence, I have a q6600)? When you are ready you can reserve a range and I will update the page. I am trying to keep most things there since I also have a group in another forum working on this (pretty small still).
So I sieve out like 99.999% of possibilities, I am going to do some more research on exactly what kind of percentages are eliminated by each thing I do, which will probably take a week or two, but I will update the webpage in a day or two with the math tests I'm running.

As of version 1.1 the program checkpoints whenever it writes to the file a result that got past its sieve. version 1.2 (no major difference) is now the latest, but keep checking the website to download the latest. On my computer a number is outputted about every 3 minute / cpu, so we probably don't want to add extra checkpointing, because it would slow things down and be hard to program :), and we already aren't losing more than 3 minutes of work . It appears that your computer really rips through that range in 1.7 hours, which I think is much faster than mine, I will have to re-time it.

Your idea of 8 threads is a good one, it will take hardly any extra memory. My code for that is pretty lousy now, I'm kind of hard coding, and only allowing 1,2 or 4, but there's probably a way to allow any number. The math is very parallizable, its the programming that's trickier. Should be fixed in 1.3 or 1.4.

[henryzz]

Originally Posted by Joshua2

Would anyone be interested in looking at the math in my code and seeing if there is any easy improvements or possibly contributing some cpu cycles to this project?

from what i can see your code probably spends quite a large amount of its time in your modpow function
if there are any improvements possible to that they would be worth doing

[Joshua2]

Probably quite a bit of time is spent doing this. I used the theory and code from wikipedia - modular exp.

However, I think most of my time is spent doing hash lookups to see if (a^x + b^y) mod n is in the hashtable. I'm using the c# default hashtable with the primes 2^32, but I do a "presieve" with primes 2^28 using a "primitive perfect" hash table. I have an array 1 - ~2^28 with a 0 or not 0 in each byte (not 0 represents where the hit is, because 2 hits must be in the same section), and I can just lookup up by index which is faster than a hash lookup.

PS, I added an edited version of this to my website.

[J.F.]

Where can the source be found?

If powmod is a bottleneck, you might wanna look at Geoff Reynolds 62-bit assembly routines.
http://www.geocities.com/g_w_reynolds/sr5sieve/

[henryzz]

Originally Posted by Joshua2

Probably quite a bit of time is spent doing this. I used the theory and code from wikipedia - modular exp.

However, I think most of my time is spent doing hash lookups to see if (a^x + b^y) mod n is in the hashtable. I'm using the c# default hashtable with the primes 2^32, but I do a "presieve" with primes 2^28 using a "primitive perfect" hash table. I have an array 1 - ~2^28 with a 0 or not 0 in each byte (not 0 represents where the hit is, because 2 hits must be in the same section), and I can just lookup up by index which is faster than a hash lookup.

aren't you wondering how i looked at your program?
i used the .net reflector http://www.red-gate.com/products/reflector/
do you have source available i can't find it?
are you using a byte array just to store 0 or 1?
surely a bitarray would use lots less memory
it might be a little slower though
i presume if you are using bytes then you are worried about memory usage as ints would be faster