### Thread: Help Optmizing Program (self-study C++)

1. No Profile Picture
Cod
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. 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.
3. 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.
4. 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.
5. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
891
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.
7. 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

• sizablegrin agrees : Nothing to do about that exept put him on a list of people to not hire.
8. No Profile Picture
Cod
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.
9. 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

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

Join Date
Oct 2007
Posts
44
Rep Power
27
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.