#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Location
    RAF Lakenheath, United Kingdom
    Posts
    5
    Rep Power
    0

    Help Optmizing Program (self-study C++)


    The idea of the program is simple and decides whether or not an entered number is prime or not prime. Here's what I came up with so far with a little help from the book (matches book answer):

    Code:
    // prime1.cpp : Defines the entry point for the console application.
    //
    
    #include <stdafx.h>
    #include <iostream>
    #include <math.h>
    
    using namespace std;
    
    int main()
    {
    	int n; // Number to test for prime-ness
    	int i; // Loop counter
    	int is_prime; // Boolean flag
    
    	is_prime = true;
    
    	cout << "Enter a number and press ENTER: ";
    	cin >> n;
    
    	i = 2;
    	while (i<= sqrt(static_cast<double>(n))) {
    		if (n % i == 0)
    
    			is_prime = false;
    		i++;
    	}
    
    	// Print Results
    
    	if (is_prime)
    		cout << "Number is prime.";
    	else
    		cout << "Number is not prime.";
    
    	return 0;
    }
    The exercise in the book reads like this: Exercise 2.4.1 Optimize the program further by calculating the square root of "n" just once rather than over and over as was done previously. To perform this optimization, you'll need to declare another variable and set it to the square root of "n". This type should be double. You can then use this variable in the for loop condition. Write a complete program that includes this optimization.

    I've tried a few different things, but can't seem to figure out exactly what I'm trying to do. So I'm looking for any sort of help.

    Please remember that I'm a beginning program, so please nothing beyond a beginner level. Any help is greatly appreciated.
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,417
    Rep Power
    1871
    It simply means replace

    while (i<= sqrt(static_cast<double>(n)))

    With

    limit = sqrt(static_cast<double>(n));
    while (i<= limit)


    Declare limit as your assignment requires.
    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
  4. #3
  5. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    It is called a loop-invariant; a value or expression that is the same for all iterations of the loop. Loop-invariants should always be pre-calculated before the loop.
  6. #4
  7. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2006
    Location
    Albuquerque, NM
    Posts
    120
    Rep Power
    28
    Even better would be:
    Code:
    limit = sqrt(static_cast<double>(n));
    while (i<= limit && is_prime)
    This breaks out of the loop as soon as you find out it is not a prime. Can save a lot of time for large non-prime values. Primes will take the longest to check, because they must run through every iteration.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Shame on you guys for doing Cod's homework for him.

    This was a trivial problem to solve and none of you have impressed anyone by posting the resolution to Cod's assignment. Better to coach and ask pointed questions than to post solutions in code form.
    I no longer wish to be associated with this site.
  10. #6
  11. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2006
    Location
    Albuquerque, NM
    Posts
    120
    Rep Power
    28
    Shame on you for adding nothing useful to this thread.
  12. #7
  13. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    Originally Posted by jwdonahue
    Shame on you guys for doing Cod's homework for him.
    Indeed, there was probably no reason to jump straight in with a solution. Frankly I think the book told him the answer. The part that says:

    "To perform this optimization, you'll need to declare another variable and set it to the square root of "n". This type should be double. You can then use this variable in the for loop condition."

    is pretty much a step-by-step solution. I am not sure how much more helpful coaching anyone could give other than to just tell him to read the question and do what it says!

    If he doesn't get it when it is on a plate like that, some people keen to 'help' are going to resort to spoon feeding. At some point he'll still end up hungry or have to learn to feed himself.

    Clifford

    Comments on this post

    • sizablegrin agrees : Nothing to do about that exept put him on a list of people to not hire.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Location
    RAF Lakenheath, United Kingdom
    Posts
    5
    Rep Power
    0
    Thanks for the help. Sorry that y'all think its "homework" that I'm doing. I'm actually just a self-learner trying to get an understanding of programming since I've never even tried it before. I'm using some book I got from a friend of mine. I never knew that you could declare a limit in C++.

    Again, sorry if I offended anyone by posting that question, I just though y'all would help me out.
  16. #9
  17. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    Originally Posted by Cod
    I never knew that you could declare a limit in C++.
    You clearly misunderstand (even a month later). Its not about setting a limit. There is no such feature in C++.

    The name limit here was simply used as a variable. It could have equally been called maxval or dogcow or anything.

    The point you have missed is that in the first version, the sqrt(n) was calculated on every iteration of the loop, but its value never changed. By assigning it to a variable outside the loop, it is calculated only once, significantly reducing the number of instructions executed and therefore also execution time.

    It is an important lesson, because in non-trivial applications unnecessarily calculating a loop invariants on each iteration may be the difference between a working application and an unusably slow one.

    Did you look up "loop invariant" BTW? That was supposed to be a hint - a fishing rod rather than a fish. Try this: http://en.wikipedia.org/wiki/Loop-invariant_code_motion

    Clifford

    Comments on this post

    • sizablegrin agrees
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2007
    Posts
    44
    Rep Power
    24
    Originally Posted by Cod
    Thanks for the help. Sorry that y'all think its "homework" that I'm doing. I'm actually just a self-learner trying to get an understanding of programming since I've never even tried it before. I'm using some book I got from a friend of mine. I never knew that you could declare a limit in C++.

    Again, sorry if I offended anyone by posting that question, I just though y'all would help me out.
    hmm.... just so you don't get the wrong idea.
    the "limit" isn't any special thing, its just another variable.

IMN logo majestic logo threadwatch logo seochat tools logo