??? Any Suggestions for Speeding This Up ???

This is a discussion on ??? Any Suggestions for Speeding This Up ??? within the C++ Programming forums, part of the General Programming Boards category; I recently made a program that looks for quadratic equations (ax+bx+c = N) that, when incremented values of x are ...

  1. #1
    brian0918
    Guest

    Question ??? Any Suggestions for Speeding This Up ???

    I recently made a program that looks for quadratic equations (ax+bx+c = N) that, when incremented values of x are inputted, generate a lot of prime numbers. The problem is, when going for 10000 or 100000 different values for x, it has to check each result N for primality, which is slow. Plus, it checks for all combinations of a, b, and c, over a range, which REALLY slows it down.

    Any suggestions for speeding up this program at all? Even a little bit will speed it up, because this is on the order of millions or billions of math calculations and loops.

    Thanks.



    Code:
    #include <iostream>
    #include <string>
    #include <cstdlib>
    #include <stdio.h>
    #include <math.h>
    #include <ctype.h>
    
    using namespace std;
    
    void main(){
    	
    	
    	short amin;
    	short amax;
    	short bmin;
    	short bmax;
    	short cmin;
    	short cmax;
    	short iterations;
    	float pmin;
    	float pmax;
    
    
    	cout << "ax^2 + bx + c" << endl;
    	cout << " " << endl;
    
    	//RANGE FOR A
    	cout << "Range for a? (integers -32,768 to 32,767)" << endl;
    	cout << " " << endl;
    	cout << "min? ";
    	cin >> amin;
    	cout << " " << endl;
    	cout << "max? ";
    	cin >> amax;
    	cout << " " << endl;
    	cout << " " << endl;
    
    	//RANGE FOR B
    	cout << "Range for b? (integers -32,768 to 32,767)" << endl;
    	cout << " " << endl;
    	cout << "min? ";
    	cin >> bmin;
    	cout << " " << endl;
    	cout << "max? ";
    	cin >> bmax;
    	cout << " " << endl;
    	cout << " " << endl;
    	
    	//RANGE FOR C 
    	cout << "Range for c? (integers -32,768 to 32,767)" << endl;
    	cout << " " << endl;
    	cout << "min? ";
    	cin >> cmin;
    	cout << " " << endl;
    	cout << "max? ";
    	cin >> cmax;
    	cout << " " << endl;
    	cout << " " << endl;
    
    
    	//ITERATIONS
    
    	cout << "How many iterations? (no more than 65,535)" << endl;
    	cin >> iterations;
    	cout << " " << endl;
    	cout << " " << endl;
    
      	
    	//PERCENTAGE PRIME
    
    	cout << "What percentage should be Prime? (integer 0 to 100)" << endl;
    	cout << " " << endl;
    	cout << "min? ";
    	cin >> pmin;
    	cout << " " << endl;
    	cout << "max? ";
    	cin >> pmax;
    	cout << " " << endl;
    	cout << " " << endl;
    
    	cout << "Wait..." << endl;
    	cout << " " << endl;
    	cout << " " << endl;
    
    	float percentmin = pmin/100;
    	float percentmax = pmax/100;
    	
    
    	//START
    
    	//Values for A
    	for (short a = amin; a <= amax; a++)
    	{
    		
    		if(a==0)	//skips the linears
    		{
    		}
    		
    		
    		else
    		{
    			//Values for B
    			for (short b = bmin; b <= bmax; b++)	//CHANGE BACK TO b++
    			{
    			
    				//Values for C
    				for (short c = cmin; c <= cmax; c++)	//CHANGE BACK TO c++
    				{		
    				
    					//keeps track of how many primes result for this quadratic
    					unsigned short primes = 0;	
    
    					//keeps track of the total iterations for this quadratic
    					unsigned short total = 0;	
    				
    					//START of test for increasing values of i
    					for(short i=0;i<iterations;i++)
    					{
    			
    
    						short flag = 0;
    
    						__int64 n = ((a*i*i) + (b*i) + c);
    		
    						if(n>1)
    						{
    							if((n%2)==0)	//checks against 2
    							{		
    
    								flag = 1;
    							}
    			
    							else
    							{
    
    								// checks odds from 3 up to sqrt(n)
    								for(long m = 3;m<=((long)(sqrt(n)));m+=2)	
    								{	
    				
    									if((n%m)==0)
    									{	 
    					
    										flag = 1;
    										break;
    			
    									}
    
    								}
    
    							}
    		
    		
    							if(flag==0)
    							{
    
    								primes = primes + 1;
    
    							}
    
    							total++;
    
    						}
    
    						else
    						{
    							/*cout << " " << endl;
    							cout << "---------------------------------------" << endl;
    							cout << n << " was tossed out for being <= 1..." << endl;
    							cout << "---------------------------------------" << endl;
    							cout << " " << endl;*/
    						}
    
    		
    					}
    
    					double primepercent =  ((double) primes) /(iterations);
    
    					if((primepercent >= percentmin) && (primepercent <= percentmax))
    					{
    					
    
    						cout << " " << endl;
    						cout << a << "x^2 + " << b << "x + " << c << endl;
    						cout << primes << " out of " << total << " were prime." << endl;
    					
    	
    						//cout << primes << endl;
    					
    					}
    
    				}
    
    			}
    		
    		}
    
    	}
    	
    }

  2. #2
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    in the C board a few weeks back was posted some quicker prime number methods
    hello, internet!

  3. #3
    Registered User
    Join Date
    Aug 2002
    Posts
    5
    Quicker how? I think my method is as fast as it gets. It checks 2, then all of the odds up to sqrt(N).... The only thing that might be faster would be to have an array of predetermined numbers (all the primes from 2 up to a really large number), and have it check them against N (only going up to sqrt(N))... But, I have no clue how to make anything like that. My professor was horrible :(

    If anyone could provide the code for this array setup I've described above, or any other way for the program to go faster (even a little bit), i would appreciate it. :D

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,451
    First thing I would do would look at the formatting, and consider moving some of the code into another function to make it easier to see what is going on.

    A single function with getting on for 200 lines, and what seems like 10 nested levels is not nice to look at.

    But for now, I would replace this
    &nbsp;&nbsp;&nbsp;&nbsp;for(long m = 3;m<=((long)(sqrt(n)));m+=2)
    with this
    &nbsp;&nbsp;&nbsp;&nbsp;long limit=(long)sqrt(n);
    &nbsp;&nbsp;&nbsp;&nbsp;for(long m = 3;m<=limit;m+=2)

    Oh, and main returns an int, not void
    int main ( ) {
    &nbsp;&nbsp;&nbsp;&nbsp;// your code
    &nbsp;&nbsp;&nbsp;&nbsp;return 0;
    }

  5. #5
    brian0918
    Guest

    Smile

    Thanks for your suggestions. I tested the first one, limit = (long)sqrt(N), versus the original, and it cut 10 seconds off (16 instead of 26). woohoo

    I don't know why the second suggestion (making main an int instead of a void) would speed it up... oh well

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I don't know why the second suggestion (making main an int instead of a void) would speed it up
    It wouldn't effect the speed at all, but it would make your code more correct.

    -Prelude
    My best code is written with the delete key.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,451
    Well so long as your values don't grow too large, then create a table with a search facility

    Code:
    #include <cmath>
    #include <cstdlib>
    #include <iostream>
    #include <iomanip>
    using namespace std;
    
    // See prime number theorem at
    // http://www.utm.edu/research/primes/howmany.shtml
    // this tells you how big your table may grow
    // depending on how many you want to store
    const int MAX_NUM = 100;
    const int MAX_PRIMES = 50;
    
    int primes[MAX_PRIMES];
    int num_primes = 0;
    
    void generate_table ( void ) {
        int i,j;
    
        num_primes = 0;
        primes[num_primes++] = 2;
        for ( i = 3 ; i < MAX_NUM ; i++ ) {
            int lim = (int)sqrt((double)i);
            bool composite = false;
            for ( j = 2 ; j <= lim && !composite ; j++ ) {
                composite = i % j == 0;
            }
            if ( !composite ) {
                primes[num_primes++] = i;
            }
            if ( num_primes == MAX_PRIMES ) {
                cout << "Table Full" << endl;
                return;
            }
        }
    }
    
    void print_table ( void ) {
        int i;
        for ( i = 0 ; i < num_primes ; i++ ) {
            cout << primes[i] << endl;
        }
        cout << "Expected number of primes is "
             << (int)(MAX_NUM/log((double)MAX_NUM))
             << endl;
        cout << "Actual   number of primes is "
             << num_primes
             << endl;
    }
    
    // a pair of functions to conduct a binary search of
    // the table of primes created previously
    int compare ( const void *key, const void *data ) {
        const int *key_ptr = (const int*)key;
        const int *data_ptr = (const int*)data;
        if ( *key_ptr < *data_ptr ) return -1;
        if ( *key_ptr > *data_ptr ) return +1;
        return 0;
    }
    bool search_table ( int test_val ) {
        return bsearch( &test_val, primes, num_primes, sizeof(primes[0]), compare ) != NULL;
    }
    
    int main ( ) {
        generate_table();
        print_table();
        for ( int i = 1 ; i < MAX_NUM ; i++ ) {
            if ( search_table(i) ) {
                cout << i << " is prime" << endl;
            }
        }   
        return 0;
    }
    Experiment a little - store the first 10000 primes in this table, and run your search loop thereafter

    Something like
    Code:
    if ( x <= primes[num_primes-1] ) {
        // its in the table, use search_table(x)
    } else {
        // x is too big to be in the table, start the search loop
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Suggestions and question about bool pointers
    By Akkernight in forum C++ Programming
    Replies: 15
    Last Post: 03-22-2009, 12:27 PM
  2. Suggestions?!
    By liljp617 in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 10-20-2008, 11:12 AM
  3. Free Book Suggestions!
    By valaris in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 10-08-2008, 10:25 AM
  4. Math Book Suggestions
    By curlious in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 10-09-2003, 10:43 AM
  5. Learning C for OSX, tutorial suggestions please
    By Nexum in forum C Programming
    Replies: 2
    Last Post: 02-17-2003, 03:57 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21