Page 1 of 2 12 LastLast
Results 1 to 40 of 55

Thread: Distributed Emirp Project

  1. #1

    Distributed Emirp Project

    I would just like to tell you that the Beta 0.2.2 Emirp Client has been
    released.

    The Distributed Emirp Project is an effort to find Emirps through the use of Distributed Computing (also known as Grid Computing).

    An Emirp is a special kind of prime number. An Emirp is a number when its digits are reversed. For example, 13 is a prime number. When its digits are reversed, it becomes 31, which is also a prime number. The number 13 is an Emirp, and so is 31.

    It may be found here:

    http://www.tong-web.com/emirp/download.php

    The client is offered in various 'distributions', for those that are bandwidth limited (like me). The client is for Windows only, and has only been tested on Windows 2000 (although it should work fine for 9x and XP). The client has buffering and proxy support.

    Uses standard HTTP/1.1 for firewall support. Minimizes to system tray, friendly towards other applications that need CPU time. It is modem friendly. Data recieved from server is generally under 20 KB. Outgoing data is not likely to be more than 50KB tops, usually ranging from 5KB - 10KB.

    There have been several networking bugs identified already, and have been reported on the forums. If you encounter errors, please check the bug forum. If the bug is listed, please add any additional comments/information. If it is not listed, please list it!


    Thanks.
    -Zach Tong
    http://www.tong-web.com/emirp/

  2. #2
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    And this advances science how?

    Sounds remarkably like computing for the sake of keeping the computers warm.

  3. #3
    How does GIMPS further science? How does generalized Fermat prime help? Or how about Golomb rulers? Sierpinski numbers?

    I'll be the first to admit that it is not as advanced as GIMPS, nor as rare. But there is a reason for that. This project is not about the result. Its about displaying the potential of Distributed Computing? Why try and prove this? Its my High School science fair topic.

    Emirps were chosen because they are simple to compute, and easy to distribute. Because its a science fair project.

    So at the end of the day the only thing accomplished is a large group of trivial, yet somewhat interesting, primes. But GIMPS is merely for mathematical pursuit as well.

    Thankyou for considering the project.

  4. #4
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    How does generalized Fermat prime help? Or how about Golomb rulers? Sierpinski numbers?
    These are all very valid mathematical pursuits and have ramifications in cryptography and other areas. Being able to prove the Sierpinski conjecture, or not, has some consequences to prime number theory as a whole.
    I'll be the first to admit that it is not as advanced as GIMPS, nor as rare. But there is a reason for that. This project is not about the result. Its about displaying the potential of Distributed Computing? Why try and prove this? Its my High School science fair topic.
    Ahh - with that last sentence you have proven that your project DOES have some validitiy. Obviously research into the potential of distributed computing is valid science, too. Most of us would probably be glad to help out, but my first impression was that the project involved "crunching just for the sake of crunching", something that I'm not willing to waste the $200 per month that I spend on electricity doing. Deliberately wasting CPU cycles is something that most DC'ers have an extreme dislike for.... But, are cycles expended to research DC really wasted cycles? Maybe not....

    Can you tell us (me) anything more about what you're attempting to show or prove? What kind of resources are you attempting to have people allocate, and for how long a period? And, now that you've got my curiosity going, did you write the client/server stuff yourself? Put together the web pages? How much participation would be too much? Can you handle 100 people? 1,000? Could you survive being slashdotted? (can run between 1 and 10 million hits within the first 1/2 hour after the story is posted ) Would it be better for you to have 1,000 people with 1 Ghz computers participate, or 10 people with 100 Ghz worth of crunching power?
    Last edited by rsbriggs; 09-21-2003 at 04:15 PM.
    FreeDC Mercenary


  5. #5
    I was not aware that the Sierpinski had an important mathematical purpose, or the others for that matter.

    As to the crunching for crunching's sake, sorry if it came off that way. I understand greatly about wasting idle time...thats why I enjoy DC so much (and disklike my friends wasting their idle time)

    What Im trying to prove...The power of DC. I was going to give the judges the amount of work that the project collected and the time it took, then tell them how long it would have taken my single box to do the same. There are many great examples of this (Seti@home, etc), but showing them, self collected data is much better.

    Im trying to prove that DC is a competent, economic solution to traditional supercomputers. I want to show that there is a vast wealth of idle computers doing nothing more than twiddling their thumbs, all which could be tapped into for projects.

    There is not set 'ending' date for the project, although one may present itself. For instance, at some point the time per number will start to become very large. At that point, I have two options. Redesign a portion of my software to save progress on individual factorings (it only saves progress on a per number basis), or call it quits. I can stave this off for a time by introducing some optimizations up my sleeve that I have not had time to implement (something basic, such as primes cant start with 2,4,6,8. More advanced, such as switching my math module. It currently uses string math to handle large numbers, but is incredibly slow. I've been working on an alternative byte array math module that is blazing fast).

    Yes, coded the entire package. The client is coded in VB (yes, VB can do some crazy advanced things with classes and api ). The server is a set of PHP scripts running ontop of a mySQL database.

    The site is PHP powered, coded by me. All graphics were done by me as well.

    The Server scripts can theoretically handle infinite amounts of users. Anaylizing the return data (re-entering work blocks that users never submitted, general maintenace, etc) is not implemented yet, but should be able to handle it.

    I'd be quite happy with 100 people each with a 1 Ghz machine. Even 50 people would be an accomplishment. I could handle 1000, but would require nerves of steel to try and serve that many people (with bug reports, database maintenance, forum support)

    Slashdotted? Nope, not even close. I have a 5 Gb transfer cap on my website. Im looking into getting it raised, if need be. I've already seen a dramatic increase in bandwidth from people simply downloading the client. Luckily, server interaction is usually around 1KB - 10KB, maxing aroung 50KB at the extreme.

    Hope that helps to explain some more. Ask any more questions, I'd be more than happy to answer

    Thanks
    -Zach

  6. #6
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    Originally posted by excaliber
    Its my High School science fair topic.
    Why didn't you SAY so? In THAT case... Let the emirps flow!! Have a couple of GHz!

    (Soon as I can get these durn computers turned around. WHOA, boy! )

    Where're you located, Zack?

  7. #7
    Lol.

    Actually, I had gotten advice from someone else that if I broadcasted the fact it was a science fair project, I would get attention from those who would like an easy project to cheat on (because of lack of security methods, etc). It would make an easier target to crack than say, D.Net

    Too late for that now

    I live in Southern Ohio, Cincinatti area.

    One machine from your farm would be great. You dont have to drop your projects for this one, else your stats in the other's will fall alot.

    Thanks again.

  8. #8
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    With a couple of minor bumps in the road, we're running.

    (hint: You only have to check numbers ending in 1, 3, 7, & 9.)

  9. #9
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    Same observation here - it's a little hard to get launched. (Start - don't have a block, attempt to fetch a block, couldn't because I didn't need to, try to start, couldn't....) Got it running now it seems....

    Oh and as Paratima said - you might want to make this 50% more efficient by not attempting to do prime factoring on even numbers. Ahh - I'm guessing that's what you meant about not doing numbers that start with 2,4,6,8 - the reverse would be an even number. A number that either starts OR ends with 2,4,6,8 or that ends with 0 isn't a cantidate here. A simple optimization that saves a lot...

    Can't guarantee how long I'll run it, but I will try to get through at least a complete block - looks like that will take more than just a few hours.

    You may find the following link interesting. This one, from Duke University, has links to Bill Rankins masters thesis about Golumbs rulers. He originally solved the G20 using a "distributed approach to collaboration" via the internet in 1993. It was close to being the first, if not the very first, distributed computing effort via the internet. You might find it interesting that his masters thesis, which was at least partly about "collaborative distributed computing", was pretty closely related to your current project.

    http://www.ee.duke.edu/~wrankin/golomb/golomb.html

    Of course todays efforts are to solve OGR24 and OGR25. In 10 years we've only managed to solve a couple more of the rulers. Why solve them? Because they are mathematically "interesting" problems that lend themselves to parallel processing, so they distribute well. And, well, because they are there to be solved. There may be "deeper" science involved, but that is as far as I ever investigated them...

    Last edited by rsbriggs; 09-21-2003 at 08:44 PM.
    FreeDC Mercenary


  10. #10
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    And of course the good Mr. rsbriggs meant (well, obviously) to include numbers ending in 0 or 5 or beginning with 5, as well.

    You did mean that, didn't you, rs?

    Just as I meant to say ending or beginning. *coff coff*

  11. #11
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    Didn't want to make it TOOOO complicated. We could throw in sum of the digits equals 9 , too ... And, actually, I did add "numbers ending in 0" to my original post last time I edited it (and before your post ), but spaced out numbers ending in 5 (therefore, numbers starting with 5.) Complete credit to paratima there.

    Sigh, that, of course, means that the entire block I'm processing, 583xxx are SEMORDNILAPs (or whatever the heck the term is for the reversals) of numbers of the form xxx385, which not only means there can't be any emirps, there can't be any primes in this block at all.

    Last edited by rsbriggs; 09-21-2003 at 09:12 PM.
    FreeDC Mercenary


  12. #12
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    This is me, being thankful for the ability to edit our posts!

    I feel your pain. Now working on block 518xxx, myself.

    But hey, so he learns from this one & goes on to develop the next BIG DC project and he'll already have half (or better) of the mistakes behind him.

  13. #13
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    Heh - maybe he'll go right from the science project to doing a masters thesis on OGR 26 or 27... Seems like a pretty bang up job so far on the infrastructure, but he's going to have to add some STATS so I (and everyone else) can actually SEE that I'm outproducing paratima...

    Something to note for your project, young excaliber - don't discount the role of competition in a DC project. It's the entire motivation behind what some of us crunch for....

    Must... Have.... Stats.....

    There are also social factors, for example the "stat race": competing with other people using daily statistics about the amount of work done. This has been found so important that virtually all distributed computing projects offer on-line statistics updated at least daily, if not realtime.

    http://www.wikipedia.org/wiki/Distributed_computing


    Last edited by rsbriggs; 09-21-2003 at 10:17 PM.
    FreeDC Mercenary


  14. #14
    Stats God in Training Darkness Productions's Avatar
    Join Date
    Dec 2001
    Location
    The land of dp!
    Posts
    4,164
    This project definitely looks interesting. I'm quite impressed by the level of the project, especially when you consider it was one person (in high school, no less), compared with some of the other major projects. Something I would personally like to see (if the author is up to it, otherwise, no worries), is some sort of progress meter, or, something that says "testing number against <blah>" so that we could gauge how much is left to finish.

    But, as I said before, I'm very impressed! Congrats, and good luck with the science fair.

  15. #15
    Target Butt IronBits's Avatar
    Join Date
    Dec 2001
    Location
    Morrisville, NC
    Posts
    8,619
    We put a boxen on it yesterday afternoon. Keep up the good work!

  16. #16
    rsbriggs: What troubles were you having starting? Did it try and tell you that you did have a block, even though you didnt? I'll check it out.

    Thanks for the link, I'll check it out.

    Yes, I really need to add that optimization in. So, I only need to check numbers that begin and end with 1,3,7 or 9. What was that about the sum of digits?

    Sorry bout the bad block range you got. My box got the same. I'll throw in those optimizations as soon as possible. It will somewhat throw stats, because you will still 'process' the block, it might only take a few minutes. Lucky individual that gets a 5xxxxx block, or any other such block.

    Yes, the project has stats. I currently have individual and server stats, working on team stats inbetween optimizations and bug fixes.

    http://www.tong-web.com/emirp/stats.php

    If you can think of more things to include on the on the stats (other than team stats) let me know.

    Darkness Productions: Do you mean the progress on an individual number? So there would be two progressbars, one for total progress and one for progress on the current number? Good idea, That should be fairly easy to implement.

    That, and its taking too LONG to factor the numberes! 40 seconds to factor a 6 digit number is too long. The string math module is just toooo slow. Im working on a byte array math module, which is much faster. Unfortunately, the division is the bottleneck and slows it down a ton. Im reworking the division to get it faster.

    Thanks all for the input.

  17. #17
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    I don't remember the exact sequence of things when I first started up. As I recall, I tried to hit start, and was told that I needed to get a block first. So, I hit fetch, and it said something about not needing to.

    I really didn't pay enough attention to the sequence to provide you with a useful description of the problem, I guess - I just kept "hitting buttons"until it appeared to start working - didn't keep track of what all went on...

    Don't worry about the sum of the digits thing - I would assume that the first factor that you are going to eliminate is '3' anyway. (That is, if you are seiving these with primes up through the square root. Hmmm - exactly how are you checking for primeness, anyway?).

    It's just one of a number of little mind tricks people have noticed - Sum of the digits equals 9 refers to the fact that if you add up the digits of a number, and they add up to nine, the number is divisible by 9. ( 9*6=54 --> 5+4=9 or another example 11*9=99 --> 9+9=18 -->1+8=9) Just a mental shortcut, not suitable for actual inclusion in a primeness test. Just get rid of those 2s, 4s, 6es, 8s, and 5s!

    You must have a faster box than the 2.8Ghz box of mine - it was taking somehwere around 157 seconds per number last time I noticed.
    FreeDC Mercenary


  18. #18
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    But, as I said before, I'm very impressed! Congrats, and good luck with the science fair.
    Did some more looking around on the emirps site. This kid is a PHP guru - it's simple, but mind boggling...
    FreeDC Mercenary


  19. #19
    Administrator PCZ's Avatar
    Join Date
    Jun 2003
    Location
    Chertsey Surrey UK
    Posts
    2,428
    excaliber

    Can you create some teams?

  20. #20
    rsbriggs: Thanks for the compliment I really like PHP. Its very easy to work with. The stuff im doing really isnt that advanced or difficult, just alot of database manipulation.

    Im using Fermat's Little Theorem to solve primality. Its faster than just straight factoring, but alot slower than other alternatives (like a quadratic sieve). Although, I should factor some low numbers first. I think this is the flow I should include in the next version.

    Server weeds out all ranges starting with 0,2,4,5,6 and 8
    Sent to client
    Client begins looping through numbers to solve
    If number ends in 0,2,4,5,6 or 8, drop and move on.
    If number is divisible by low common factors (3, etc) drop.
    begin Fermat's Little Theorem loop

    No, actually my box is 1.7 Ghz. I just got a lower number than yours. Mine are around 300,xxx, while yours are in the 500xxx range.

    That right there is why I need to optimize my math routines.


    PCZ: Working on it! Im going to work on the optimizations and a few minor/major bugfixes, then start cracking on the teams (and in between all that go to school and play soccer )

    Thanks again everyone

  21. #21
    Senior Member
    Join Date
    Feb 2003
    Location
    wigan, uk
    Posts
    200

    Question

    when i try to click on either of the links provided i get a "cannot find server" error.

    Has anyone else got this (i tried last night and tonight).

    Will try from another pc tomorrow

    All other sites seem to be working

  22. #22
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    Ever investigated the Miller-Rabin test for primeness?

    http://www.swiss.ai.mit.edu/cgi-bin/info2www?(slib)The%20Miller-Rabin%20Test

    The emirps links all work for me... Just tried the stats link, came up no problem.
    FreeDC Mercenary


  23. #23
    Boinc'ing away
    Join Date
    Aug 2002
    Location
    London, UK
    Posts
    982
    done a bit of Eprim'ing but getting times of 90-140secs (P4 2.8 and XP2200+, 49xxx and 51xxx ranges respectively) seems a bit off-putting for (what seems) a relatively easy process...will look into it when the optimisations start coming out...

    good work though

  24. #24
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    Had no trouble getting to the site...

  25. #25
    Originally posted by pfb
    done a bit of Eprim'ing but getting times of 90-140secs (P4 2.8 and XP2200+, 49xxx and 51xxx ranges respectively) seems a bit off-putting for (what seems) a relatively easy process...will look into it when the optimisations start coming out...
    Yes, it is quite irritating. Im not sure if its Fermat's Little Theorem or my math routines. Probably both.

    Im working on getting it faster. that much time per number is unacceptable.

  26. #26
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    Especially given that both those ranges aren't any good

    Might I suggest

    1.) not having the server give out the 2, 4, 5, 6, 8 ranges - if one comes up, immediately discard it / mark it as complete, and

    2.) before launching into Fs Little T, do a quick test division of the first few small primes 3, 7, 11, 13, ... up to some reasonable number, Oh - and don't test even numbers in the range, either...

    3.) Optionally, you could do one iteration of the Miller-Rabin test and discard the number if it indicates that it is composite. This will eliminate 3/4 of the numbers that you might otherwise test. It is 100% correct if it indicates that the number is composite, but has a 25% chance of passing a false positive.

    4.) Lose the string math - your times are going to increase exponentially with the number of digits in the string being tested. Couple more digits, and the tests will be taking hours-per-number. You're going to have to "bite the bullet" and either write or find some long-math numeric manipulation routines.
    FreeDC Mercenary


  27. #27
    I was just discussing this very 'flow' over at my forums with the same general idea. The server will drop anything starting in the 'bad range', while the client checks for those ending in the bad range. Then do a quick trial division with small numbers.

    The extra M-R test is a good idea.

    Someone at Ars mentioned using a precompiled math DLL. I am considering this idea for several reasons.

    1. It will make times alot better
    2. the project is not about the math, but the DC end. This will let me focus more tim on DC (server and bug and features)


    Yea, String math is slow as hell. I've developed a Byte Array math module, but it actuall performs worse (i believe that the bottleneck is the division). It is blazing fast, except for division (im using repeated subtraction instead of long division).

    What are your thoughts? Continue to improve my math module or go with a math library?

    I've checked...not one math module out there for large numbers, other than the string math module i found.

  28. #28
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    precompiled math DLL.

    The question is, can you FIND one? There are lots of people doing prime number stuff - it doesn't seem likely that they all write everything from scratch. Hmm. Here is a link.....

    A bunch of n-digit C++ integer math routines. At first glance it looks like it will do up to 18,000 digits:

    http://www.planet-source-code.com/vb...d=211&lngWId=3
    FreeDC Mercenary


  29. #29
    excaliber---
    Could the overflow error I'm getting be caused because i didn't install the VB 6 libraries? Would the client run at all w/o them? I just got to wondering, because I have no idea if those libraries are preasent on my server

  30. #30
    Senior Member
    Join Date
    Jan 2003
    Location
    North Carolina
    Posts
    184
    Originally posted by excaliber
    ... Then do a quick trial division with small numbers.
    There is a trick that lets you do a test division by several small numbers at once. If one number is divided by another, and both those numbers have a common factor, then the remainder will also have that factor (or will be zero, if the numbers divide evenly). For example, divide some big number by 51051 (which is 3*7*11*13*17). Now test the remainder to see if it's divisible by 3, 7, 11, 13, or 17. Those tests are ordinary operations using small integers, and thus go very fast. If the remainder contains one of those factors, then the original big number does as well.

    I agree with those who advise you to use a big-numbers library. People have put a lot of effort and cleverness into making those libraries run as fast as possible. I've used the MIRACL library myself.

  31. #31
    Originally posted by rshepard
    excaliber---
    Could the overflow error I'm getting be caused because i didn't install the VB 6 libraries? Would the client run at all w/o them? I just got to wondering, because I have no idea if those libraries are preasent on my server
    Good idea, but no. You would have to have the libraires installed to run the application to begin with. Otherwise it would blow up on you.

    You could, if you wanted, install the VB Runtimes just to make sure. I dont believe it would help, but it certainly cant hurt!

    Actually, now that I think about it, you may have an older version of the runtimes. Thanks

    Guess I'll start looking into a math library. I'll check out MIRACL too.

    Nice mod trick, i'll keep that in mind.

    Thanks again.

  32. #32
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    I think something's happened to our buddy, excaliber. Or at least to his web site. Been trying to get over there, but it ain't happenin'.

  33. #33
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    Works fine from here.
    FreeDC Mercenary


  34. #34
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    Hmmmmm. I get "tong-web not found". What IP does it resolve to on your end?

  35. #35
    try 207.44.180.27


    <edit>
    well, maybe not- but that's what comes back from a ping.....


  36. #36
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    But, if you go to www.tong-web.com you don't get anything like the website you might be expecting....

    G:\Documents and Settings\Bob>ping www.tong-web.com

    Pinging www.tong-web.com [207.44.180.27] with 32 bytes o

    Reply from 207.44.180.27: bytes=32 time=134ms TTL=40
    Reply from 207.44.180.27: bytes=32 time=133ms TTL=40
    Reply from 207.44.180.27: bytes=32 time=134ms TTL=40
    Reply from 207.44.180.27: bytes=32 time=134ms TTL=40

    Ping statistics for 207.44.180.27:
    Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
    Approximate round trip times in milli-seconds:
    Minimum = 133ms, Maximum = 134ms, Average = 133ms
    FreeDC Mercenary


  37. #37
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    If I try www.tong-web.com, I get a dns error.

    If I try browsing direct to that IP, I get "domain name mismatch - possible name hijacking".

    Sumthin's fscked up!

    Guess it'll wait till tomorrow.

  38. #38
    Not here rsbriggs's Avatar
    Join Date
    Dec 2002
    Location
    Utah
    Posts
    1,400
    It still all works fine from here. No problem getting there if I use the URL or the IP. Sounds like your DNS server is having a problem.....
    FreeDC Mercenary


  39. #39
    Ancient Programmer Paratima's Avatar
    Join Date
    Dec 2001
    Location
    West Central Florida
    Posts
    3,296
    Yup. Think the DNS got hacked sometime yesterday.

    It's all OK this morning!

  40. #40
    Must be your DNS...I've never had that problem.

    Yes, tong-web.com is the 'family' website, kind of a table of contents. Its really old, made by my dad.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •