C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 
Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old September 22nd, 2005, 03:25 PM
spiderman45144 spiderman45144 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Sep 2005
Posts: 9 spiderman45144 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 57 m 8 sec
Reputation Power: 0
Mersenne Primes

I have been working on a program for my school science fair and it is supposed to find Mersenne primes. So far I have edited the code quite a bit from what it started out as and I tried to add whitepsace to make it readable. The program unfortunately only guesses about 10 million times every 10 seconds. This is not nearly fast enough, before anyone suggests dividing by only other primes I have tried to integrate it and it seemed to have slowed down my program more. Maybe someone can help me make a table to store primes in? I will put the other code containing dividing by primes, which is a lot harder to read below my code that I am using now. I have also got some suggestions about using pointers, I know what they are, but where could I possibly use them in my program? I have also already used the optimization switch /O2. Thanks for any help in advance!

Present code
Code:
#include <windows.h>
#include <fstream> 
#include <iostream> 
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <gmp.h>
using namespace std;
int main(int argc, char* argv[])
    {
      int color;
              color = atoi(argv[1]);
              HANDLE console;
              console = GetStdHandle(STD_OUTPUT_HANDLE);
      int input_low;
      int input_high;
      SetConsoleTextAttribute(console, 3);
          cout<<"Program Created By Devon Taylor in 2005 \n";
      SetConsoleTextAttribute(console, 6);
          cout<<"Enter an odd # > 3 and < ten mill to start calc. at: ";
      SetConsoleTextAttribute(console, 2);
          cin>>input_low;                                       //Prompt for lower boundry
      SetConsoleTextAttribute(console, 6);
          cout<<"Enter an odd # > 3 and < ten mill to stop calc. at: ";
      SetConsoleTextAttribute(console, 2);
          cin>>input_high;                                     //Prompt for high boundry
      SetConsoleTextAttribute(console, 8);
          cout<<"Calculating.........";
      int cvd_prm;                                            //Create Integer Variables
      int is_prime;
      int end;
      int divisible;
      cvd_prm=3;
      FILE *fp;                                               
      mpz_t prime_exp;                                        //Set high precision variables
      mpz_t test2;
      mpz_t test1;
      mpz_t limit;
      mpz_t mprime;
      mpz_t base;
      mpz_init_set_si(prime_exp,input_low);                   //Initiate high precision variables
      mpz_init_set_si(base,2);
      mpz_init(mprime);
      mpz_init(limit);
      while (cvd_prm<input_high)                            //While prime_exp is less than higher input
      {
         mpz_add_ui(prime_exp,prime_exp,2);                 //Add 2 to prime_exp and test again
                       end=0;                               //Set exit variable back to 0
         mpz_init_set_si(test1,3);                          //Set testing variable back to 3
         mpz_sqrt(limit,prime_exp);                         //Find square root of prime_exp and store in limit
         while(end==0)                                      //While exit variable is not set to 1
            {
                        is_prime=mpz_cmp(limit,test1);      //See if testing variable is greater tha the limit
                        divisible=mpz_divisible_p(prime_exp,test1);   //See if prime_exp is divisible by test1
               mpz_add_ui(test1,test1,2);                             //Add 2 to test if the # isn't divisible
                  if (divisible>0)                                    //If prime_exp is ever divisible then exit
                  {
                     end=1;                                           //Set exit variable to true
                  } 
                  if(is_prime<0)                                      //If the number isn't divisible then continue on
                  {
                     SetConsoleTextAttribute(console, 5);             
                     cout<<"testing ";                                
                     gmp_printf("%Zd",prime_exp);                     //Print what # is being tested
                     cout<<", ";
                     mpz_init_set_si(test2,3);                        //Set test2's value to 3
                     cvd_prm =mpz_get_si(prime_exp);                  //Convert prime_exp to integer
                     mpz_pow_ui(mprime,base,cvd_prm);                 //Take base and put it to the converted integers power
                     mpz_sub_ui(mprime,mprime,1);                     //subtract 1 to complete formula: 2^p-1=p
                     mpz_sqrt(limit,mprime);                          //Set top boundry from square root of the answer to the above
                     is_prime=mpz_cmp(test2,limit);                   //Compare test2 to the limit
                        while(end==0)                                 //While exit statement is set to 0
                        {
                                   is_prime=mpz_cmp(limit,test2);     //Compare limit to test2
                                   divisible=mpz_divisible_p(mprime,test2);     //Check divisibility of mprime
                           mpz_add_ui(test2,test2,2);                           //Add 2 to test2
                           if(divisible>0)                                      //if mprime is ever divisible, exit
                           {
                              end=1;                                            //Set exit variable to true
                           } 
                           if(is_prime<0)                                       //If the number isn't divisible continue
                           {
                              SetConsoleTextAttribute(console, 7);              
                              gmp_printf("%Zd",prime_exp);
                              cout<<" is a prime with P=";
                              gmp_printf("%Zd",mprime);
                              cout<<", ";
                              ofstream a_file ( "Mprimes.txt", ios::app );      //Open file and write primes to it
                              fp = fopen("Mprimes.txt", "a");                   //
                              mpz_out_str(fp,0,mprime);                         //
                              a_file<<" & ";                                    //   
                              a_file<<cvd_prm;
                              a_file<<", ";
                              fclose(fp);
                              end=1;     
                           }        
                        }
                     }
               }
         }           
    }
 


Code divding by primes
Code:
#include <windows.h>
#include <fstream> 
#include <iostream> 
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <gmp.h>
using namespace std;
int main(int argc, char* argv[]){
int color;
        color = atoi(argv[1]);
        HANDLE console;
        console = GetStdHandle(STD_OUTPUT_HANDLE);
int input_low;
int input_high;
SetConsoleTextAttribute(console, 3);
cout<<"Program Created By Devon Taylor in 2005 \n";
SetConsoleTextAttribute(console, 6);
cout<<"Enter an odd # > 3 and < ten mill to start calc. at: ";
SetConsoleTextAttribute(console, 2);
cin>>input_low;
SetConsoleTextAttribute(console, 6);
cout<<"Enter an odd # > 3 and < ten mill to stop calc. at: ";
SetConsoleTextAttribute(console, 2);
cin>>input_high;
SetConsoleTextAttribute(console, 8);
cout<<"Calculating.........";
int pie;
mpz_t d;
mpz_t bound;
mpz_t x;
mpz_t i;
mpz_t n;
mpz_t r;
mpz_t w;
mpz_t b;
FILE *fp;
signed int l;
int m;
int h;
int t;
mpz_t c;
mpz_t y;
mpz_t k;
mpz_t v;
mpz_t a;
int z;
mpz_init_set_si(d,input_low);
mpz_init_set_si(k,2);
mpz_init_set_si(v,1);
mpz_init_set_si(a,3);
mpz_init(r);
int ans;
mpz_init(y);
mpz_init(bound);
mpz_init(c);
mpz_init(w);
while (input_low<input_high){
mpz_add_ui(d,d,2);
t=0;
mpz_init_set_si(b,3);
mpz_fdiv_q(c,d,a);
while(t==0){
z=mpz_divisible_p(d,b);
mpz_add_ui(b,b,2);

m=mpz_cmp(c,b);
if (z>0){
t=1;
break;
} 
if(m<0){
SetConsoleTextAttribute(console, 5);
cout<<"testing ";
gmp_printf("%Zd",d);
cout<<", ";
mpz_init_set_si(x,3);
l =mpz_get_si(d);
mpz_pow_ui(y,k,l);
mpz_sub_ui(y,y,1);
mpz_sqrt(c,y);
int end;
t=0;
while(t==0){
end=0;
mpz_add_ui(x,x,2);
mpz_init_set_si(i,3);
mpz_sqrt(bound,x);
while(end==0){             
z=mpz_divisible_p(x,i);
mpz_add_ui(i,i,2);

int dud=mpz_cmp(bound,i);

if (z>0){
end=1;
}
if(dud<0){      

z=mpz_divisible_p(y,x);
h=mpz_cmp(c,x);
if(z>0){
end=1;
t=1;
} 
if(h<0){
SetConsoleTextAttribute(console, 7);
gmp_printf("%Zd",d);
cout<<" is a prime with P=";
gmp_printf("%Zd",y);
cout<<", ";
ofstream a_file ( "Mprimes.txt", ios::app );
fp = fopen("Mprimes.txt", "a");
mpz_out_str(fp,0,y);
a_file<<" & ";
a_file<<l;
a_file<<", ";
fclose(fp);
end=1;
t=1;
}
else
{
end=1;
}
}         
}     
}
}
}
}           

}

Reply With Quote
  #2  
Old September 22nd, 2005, 03:33 PM
spiderman45144 spiderman45144 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Sep 2005
Posts: 9 spiderman45144 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 57 m 8 sec
Reputation Power: 0
Mersenne Primes

In case somebody doesn't know what a Mersenne Prime is. It's a number in the equation 2^p-1=p. Where 2 to the power of a prime minus 1, is a prime number.
For example:

2^3-1=7 <<Mersenne Prime

2^23-1=8388607 <<Is not prime, therefore, is not a Mersenne Prime



Hopefully that was kind of clear
Comments on this post
MichaelSoft agrees: Thanks! Did not know that

Reply With Quote
  #3  
Old September 23rd, 2005, 06:21 AM
MichaelSoft MichaelSoft is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Aug 2005
Location: The Netherlands
Posts: 121 MichaelSoft User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 17 h 20 sec
Reputation Power: 4
Spidey,

I have no experience with the mpz-functions. If they cause any performance problems then you're screwed. In first glance your program flow seems good enough.

Two advices though:

1. keep the output to the screen to a minimum. This slows down everything! Do a test with all output removed. Only a "calculating ..." at the beginning, and a dump of the file at the end.

2. you're opening and closing the file for every found value. It should be quicker to open the file at the beginning and leaving it open until the end. Otherwise you have to wait for the HD to open the file, find the end and close it again. The caching will not be optimal there. When leaving the file open, the cache will keep the values in memory.
Only downside is that when the program is cancelled or PC is rebooted, the file is lost...

Reply With Quote
  #4  
Old September 23rd, 2005, 09:12 AM
spiderman45144 spiderman45144 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Sep 2005
Posts: 9 spiderman45144 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 57 m 8 sec
Reputation Power: 0
File Opening

I realize that opening the file will slow my program, but, considering that it will only output to the file maybe 40 times at the maximum and thats over a 5 month period I don't think it will matter to much. About MPZ function, they seem to quite fast, faster than my own function would be I believe atleast. GMP is customized for your computer on installation so I'm sure its running at optimum performance. I guess there just isn't to much more I can do besides getting a new processor and overclocking it. Thanks for the suggestions! I also find on my other program, which finds primes itself, about ever 200 million it finds my virtual memory seems to run out, is there any way to prevent this?

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > Mersenne Primes


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump


Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 





© 2003-2008 by Developer Shed. All rights reserved. DS Cluster 6 hosted by Hostway
Stay green...Green IT