August 6th, 2007, 05:21 PM

Help Optmizing Program (selfstudy 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 primeness
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.
August 6th, 2007, 06:38 PM

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.
August 7th, 2007, 09:11 AM

It is called a loopinvariant; a value or expression that is the same for all iterations of the loop. Loopinvariants should always be precalculated before the loop.
August 7th, 2007, 11:38 AM

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 nonprime values. Primes will take the longest to check, because they must run through every iteration.
August 8th, 2007, 02:22 AM

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.
August 8th, 2007, 08:27 AM

Shame on you for adding nothing useful to this thread.
August 8th, 2007, 07:14 PM

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 stepbystep 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
October 21st, 2007, 03:36 PM

Thanks for the help. Sorry that y'all think its "homework" that I'm doing. I'm actually just a selflearner 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.
October 21st, 2007, 04:08 PM

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 nontrivial 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/Loopinvariant_code_motion
Clifford
Comments on this post
October 21st, 2007, 04:10 PM

Originally Posted by Cod
Thanks for the help. Sorry that y'all think its "homework" that I'm doing. I'm actually just a selflearner 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.