This post has been edited by zainsiddiqui14: 11 July 2012  08:21 PM
41 Replies  7389 Views  Last Post: 12 July 2012  06:07 AM
#31
Re: is given # a perfect square?
Posted 11 July 2012  08:21 PM
#32
Re: is given # a perfect square?
Posted 11 July 2012  08:59 PM
It pains me to see those for loops. Programming is math. It is never too early to optimize. Plan first, then program.
The process for solving a problem like this requires exploration.
Define what a square number is. What makes square numbers different than the other numbers? What other operations are related to squaring a number?
Using a for loop for this is like guessing. How would this program perform if your number was really big?
zainsiddiqui14, pure genius comes from experience. Experience can come from understanding the work others have done, or doing it the hard way. We wouldn't be able to help anyone if we all had to build our own modems to use the internet...
#33
Re: is given # a perfect square?
Posted 11 July 2012  09:36 PM
Quote
this is wrong, by mosts' opinion. "premature optimization is the root of all evil", I believe Donald Knuth said that. when first writing a program, designing code with maintainability in mind is the key; premature optimization has a very nasty habit of creating less maintainable programs.
#34
Re: is given # a perfect square?
Posted 11 July 2012  09:56 PM
This post has been edited by zainsiddiqui14: 11 July 2012  10:04 PM
#35
Re: is given # a perfect square?
Posted 11 July 2012  10:19 PM
zainsiddiqui14, on 11 July 2012  09:56 PM, said:
Correction: I wouldn't be surprised if even sqrt() were a taxing function for the processor. Then again, many languages support math coprocessors.
If you took coprocessors out of the equation, the performance gap between the two algorithms would be smaller.
#36
Re: is given # a perfect square?
Posted 11 July 2012  10:52 PM
How would you solve this problem on paper?
Would you start squaring every natural number until you found or passed the number? No.
You would take the square root of the number and see if it is an integer.
Solve the problem, then program the solution.
#37
Re: is given # a perfect square?
Posted 11 July 2012  11:34 PM
jared.deckard, on 11 July 2012  10:52 PM, said:
How would you solve this problem on paper?
Would you start squaring every natural number until you found or passed the number? No.
You would take the square root of the number and see if it is an integer.
Solve the problem, then program the solution.
Okay let's try this on paper... I don't think you can get away for using loops, though:
Let the number that we want to check be 3407.
The objective is to take the square root of the number and see if it is an integer.
So we write:
______ \/ 34 07
Next we need to find biggest number such that the square is less than 34. And so:
for(int i = 9; i > 0; i) if (i * i < 34) { cout << i * i << " is the biggest number less than 34. Use " << i << endl; break; }
Oh wait! Look we just used a forloop. But let's ignore that for now because people surely have memorized the squares and can just look at an number and figure out the biggest perfect square that fits. So let's continue computing the square root.
__5___ \/ 34 07 25 ___ 9 07
Next we double 5, and try to find a number less than 907:
__5___ \/ 34 07 25 ___ (10x) 9 07
for(int i = 9; i > 0; i) { int x = 100 + i; if (x * i < 907) { cout << x * i << " is the biggest number less than 907. Use " << i << endl; break; } }
Oh look! Another for loop. Again let's ignore that, even though I doubt that people have memorize these sets of multiplicands.
__5__8 \/ 34 07 25 ___ (108) 9 07 x8 8 64 ____ 42
Okay, since we ended up with 42 instead of 0, that means that we will have decimal places in the square root that we compute This means that we don't have an integer as the square root of 3407.
Since it's not an integer, we go declare that 3407 is not a perfect square.
Notice that in the process of figuring this out we had 2 for loops which busts the idea that a good solution will not use for loops.
Okay, so you say, there is no need to reimplement computing the square root. Just use the sqrt() function as a blackbox (and forget that it probably uses loops internally) and see if the returned value is an integer.
So that would then lead to the following code, assuming we follow the "how would you do it on paper" route:
bool IsPerfectSquare(int candidate) { double square_root = sqrt((double) candidate); return !(square_root  floor(square_root) > 0); }
But this is different from:
bool IsPerfectSquare(int candidate) { int square_root = (int) sqrt((double) candidate); return square_root * square_root == candidate; }
which everyone seems to consider to be the better solution.
#38
Re: is given # a perfect square?
Posted 11 July 2012  11:51 PM
jared.deckard, on 11 July 2012  10:52 PM, said:
How would you solve this problem on paper?
Would you start squaring every natural number until you found or passed the number? No.
You would take the square root of the number and see if it is an integer.
Solve the problem, then program the solution.
If you read my earlier post, you would see that before the loop (which I devised in the first place just to simplify the logic), I had an algorithm that involved taking the sqrt of the number, converting that value to a new int, and then checking for loss of information between the two answers.
#39
Re: is given # a perfect square?
Posted 12 July 2012  05:32 AM
25
squareroot=5
5%1=0
#40
Re: is given # a perfect square?
Posted 12 July 2012  05:49 AM
Wolman, on 12 July 2012  05:32 AM, said:
25
squareroot=5
5%1=0
Are you sure? It seems to me that any number modulus 1 is 0.
Following that logic, the for loop below will show that all numbers from 0 to 24 are also perfect squares because the output is 0:
for(int i = 0; i < 25; ++i) cout << ((int) sqrt((double) i) % 1) << endl;
Or is there a special modulus operation that you are thinking of?
#41
Re: is given # a perfect square?
Posted 12 July 2012  05:57 AM
Skydiver, on 12 July 2012  05:49 AM, said:
Wolman, on 12 July 2012  05:32 AM, said:
25
squareroot=5
5%1=0
Are you sure? It seems to me that any number modulus 1 is 0.
Following that logic, the for loop below will show that all numbers from 0 to 24 are also perfect squares because the output is 0:
for(int i = 0; i < 25; ++i) cout << ((int) sqrt((double) i) % 1) << endl;
Or is there a special modulus operation that you are thinking of?
Yes all whole numbers modulus 1 will be zero. That is why you need to do the square root first. if a square root is a whole number the original number is a perfect square. If it is not a perfect square, the remainder will be the decimal part of the square root. hterefore not a perfect square
#42
Re: is given # a perfect square?
Posted 12 July 2012  06:07 AM
Wolman, on 12 July 2012  05:57 AM, said:
Skydiver, on 12 July 2012  05:49 AM, said:
Wolman, on 12 July 2012  05:32 AM, said:
25
squareroot=5
5%1=0
Are you sure? It seems to me that any number modulus 1 is 0.
Following that logic, the for loop below will show that all numbers from 0 to 24 are also perfect squares because the output is 0:
for(int i = 0; i < 25; ++i) cout << ((int) sqrt((double) i) % 1) << endl;
Or is there a special modulus operation that you are thinking of?
Yes all whole numbers modulus 1 will be zero. That is why you need to do the square root first. if a square root is a whole number the original number is a perfect square. If it is not a perfect square, the remainder will be the decimal part of the square root. hterefore not a perfect square
My apologies. My brain left me for a moment. modulus wont work
