mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-04-23, 04:06   #23
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

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

Last fiddled with by CRGreathouse on 2009-04-23 at 04:07
CRGreathouse is offline   Reply With Quote
Old 2009-04-23, 04:20   #24
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13×41 Posts
Default

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 is offline   Reply With Quote
Old 2009-04-23, 04:36   #25
Joshua2
 
Joshua2's Avatar
 
Sep 2004

10000101012 Posts
Default

New bealconjecture 1.1 out! It includes changelog, but adds full threading support choice and checkpointing.
Joshua2 is offline   Reply With Quote
Old 2009-04-23, 04:55   #26
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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
Code:
mono BealConjecture.exe 4 1 500
for my quad core Phonom 2.
CRGreathouse is offline   Reply With Quote
Old 2009-04-23, 05:21   #27
Joshua2
 
Joshua2's Avatar
 
Sep 2004

10258 Posts
Default

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?

Last fiddled with by Joshua2 on 2009-04-23 at 06:02
Joshua2 is offline   Reply With Quote
Old 2009-04-23, 15:20   #28
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

1,373 Posts
Default

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.
Attached Files
File Type: zip times.zip (137.4 KB, 124 views)
lavalamp is offline   Reply With Quote
Old 2009-04-23, 18:58   #29
Joshua2
 
Joshua2's Avatar
 
Sep 2004

53310 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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.

Last fiddled with by Joshua2 on 2009-04-23 at 19:07
Joshua2 is offline   Reply With Quote
Old 2009-04-24, 16:09   #30
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

37·163 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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
henryzz is offline   Reply With Quote
Old 2009-04-24, 16:45   #31
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13·41 Posts
Default

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.

Last fiddled with by Joshua2 on 2009-04-24 at 16:52
Joshua2 is offline   Reply With Quote
Old 2009-04-24, 16:53   #32
J.F.
 
J.F.'s Avatar
 
Jun 2008

23·32 Posts
Default

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/
J.F. is offline   Reply With Quote
Old 2009-04-24, 16:59   #33
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

37×163 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Beal Conjecture Proof Arxenar Miscellaneous Math 1 2013-09-07 09:59
Distributed NFS postprocessing poily Msieve 6 2012-12-05 12:45
New Beal Conjecture Search Joshua2 Open Projects 0 2009-04-20 06:58
distributed.net completes OGR-25 ixfd64 Lounge 4 2008-11-22 01:59
distributed proofreading adpowers Lounge 10 2004-11-05 01:54

All times are UTC. The time now is 01:22.


Tue Jan 31 01:22:11 UTC 2023 up 165 days, 22:50, 1 user, load averages: 0.99, 0.99, 0.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔