| |||||||||
![]() |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Display Modes |
|
#1
|
|||
|
|||
|
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;
}
}
}
}
}
}
}
}
|
|
#2
|
|||
|
|||
|
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 |
|
#3
|
|||
|
|||
|
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... |
|
#4
|
|||
|
|||
|
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?
|
![]() |
| Viewing: Dev Articles Community Forums > Programming > C/C++ Help > Mersenne Primes |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
|
|