optimise algorithm

This is a discussion on optimise algorithm within the C++ Programming forums, part of the General Programming Boards category; I have written a program which tests for prime numbers. Please could someone review my code and tell me if ...

  1. #1
    Registered User cyberCLoWn's Avatar
    Join Date
    Dec 2003
    Location
    South Africa
    Posts
    124

    optimise algorithm

    I have written a program which tests for prime numbers. Please could someone review my code and tell me if there is any way to optimise it as once you start hitting large numbers it takes that much longer to break the loop and return a result.

    Code:
    int prime( long unsigned int &number )
    {
       int factor = 0;
       
       for( int i = 1; i <= number; i++ )
          if( number % i == 0 )// if there is no remainder - i is a factor of number
             factor++; 
       
       if( number == 1 )
          return 1;
       else if( factor == 2 ) // number is prime if only 2 factors are found
          return 1;
       else // more than two factors found, number is not prime
          return 0;      
    } // end function prime

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    How about a lookup table? Search the forum for prime numbers, there are tons of posts on the topic.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    The code below is a very obvious optimization, there are definitely more things that could be optimized if you need more speed.
    Code:
    #include <math.h>
    
    int prime( long unsigned int &number )
    {
    	if (number % 2 == 0)
    	{
    		cout << "Number is not prime\n";
    		return 0;
    	}
    	for (int i = 3; i <= sqrt(number); i=i+2)
    	{
    		if (number % i == 0)// if there is no remainder - i is a factor of number
    		{
    			cout << "Number is not prime\n";
    			return 0;
    		}
    	}
    	cout << "Number is prime\n";
    	return 0;
    }
    If your interested in making a faster test then read this...
    http://mathworld.wolfram.com/FermatsLittleTheorem.html

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,847
    > for (int i = 3; i <= sqrt(number); i=i+2)
    Which is even worse than the original - now you're doing square root on every iteration of the loop.

    Code:
    int limit = sqrt(number);
    for (int i = 3; i <= limit; i=i+2)
    Also, you can do better that +2 each time.
    3 5 7 9 11 13 15 17
    You only need check numbers which are known to be prime already - it's a waste of time checking 9 and 15, because these are already a multiple of 3, so any multiple of 9 will by definition also be a multiple of 3, and therefore always composite.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    The first point about the sqrt is important, however, dividing by only primes is harder then one might think. If you use an array to mark out multiples then you are limited to numbers in the int region, because too much larger then 2^32 and you won't have the RAM. Anyways, computers are fast enough these days that checking primality on a number as small as an int is very fast on even unoptimized code, which makes dividing by primes even less attractive.

  6. #6
    Registered User cyberCLoWn's Avatar
    Join Date
    Dec 2003
    Location
    South Africa
    Posts
    124
    Right, I'll definitely look into the above mentioned optimizations. Thanks so much.

    What did you mean by this though?
    Also, you can do better that +2 each time.
    What do the -O1 through to -O3 optimizations actually do? What is the difference behind them and which one do you pick? I use the Dev-C++ compiler.
    Last edited by cyberCLoWn; 01-18-2005 at 11:20 AM.

  7. #7
    Registered User Scribbler's Avatar
    Join Date
    Sep 2004
    Location
    Aurora CO
    Posts
    266
    Quote Originally Posted by Salem
    > for (int i = 3; i <= sqrt(number); i=i+2)
    Which is even worse than the original - now you're doing square root on every iteration of the loop.
    Actually, using (int i = 3; i <= sqrt(number); i=i+2) is much more efficient.

    As a comparison (this is a typical learning project) checking for all primes in the range 1 - 10,000, using the formula n/2 results in 1,415,016 calculations, whereas using sqrt[n] results in 55,958 calculations.

    Since the OP has already done the footwork for the project, I'll attach the code I used as a comparison...

    [EDIT] ne'r mind...I just realized you were saying to get the square root before entering the loop each time. Still on my first cup o java
    Attached Files Attached Files
    Last edited by Scribbler; 01-18-2005 at 01:25 PM.

  8. #8
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    That wasn't Salem's point. Note the difference between the code he posted and yours:
    Quote Originally Posted by MadCow257
    Code:
    for (int i = 3; i <= sqrt(number); i=i+2)
    Quote Originally Posted by Salem
    Code:
    int limit = sqrt(number);
    for (int i = 3; i <= limit; i=i+2)
    You don't want to recalculate that square root every iteration through the loop. It's expensive and wasteful.
    [edit] Heh, nevermind. You got it.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  9. #9
    Registered User cyberCLoWn's Avatar
    Join Date
    Dec 2003
    Location
    South Africa
    Posts
    124
    Right, I agree about the sqrt() being done once outside the loop. Still, why is int i in the for loop incremented by 2 each loop?

  10. #10
    Registered User Scribbler's Avatar
    Join Date
    Sep 2004
    Location
    Aurora CO
    Posts
    266
    Quote Originally Posted by cyberCLoWn
    Still, why is int i in the for loop incremented by 2 each loop?
    Because other than the number 2, there are no even numbers that will be prime, so incrementing by 2 will keep you limited to odd numbers.

  11. #11
    Registered User cyberCLoWn's Avatar
    Join Date
    Dec 2003
    Location
    South Africa
    Posts
    124
    I never even thought about that scribbler. Thanks for the clarification.

    So, what do I do about the optimization flags? (-01, etc)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

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