[zainsiddiqui14]

Haha, thanks. A question to the other posters: how are you guys so smart? My original algorithm was to take the sqrt of the argument, typecast the double's value to a new int, and check to see if there was a difference between the value of the double sqrt answer and the int sqrt answer, and then I see an infinitely more simple way to do it from you guys. Is this just experience, or pure genius?

This post has been edited by zainsiddiqui14: 11 July 2012 - 08:21 PM

[jared.deckard]

Sorry I put the full solution on homework help. There was no mention of that when I posted.
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...

[ishkabible]

Quote

It is never too early to optimize.

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.

[zainsiddiqui14]

By the way, the for loop is faster than you think. Not as fast as sqrt (I would be surprised if even sqrt is a function that takes a good bit of processor time), perhaps, but still fast. I just bashed into the keyboard a ridiculously large double and it quite immediately gave me an answer. The sequence f(n) = n^2 grows rather quickly, so the loop doesn't need to check that many numbers. I'm sorry my loop "pains you".

This post has been edited by zainsiddiqui14: 11 July 2012 - 10:04 PM

[zainsiddiqui14]

zainsiddiqui14, on 11 July 2012 - 09:56 PM, said:

By the way, the for loop is faster than you think. Not as fast as sqrt (I would be surprised if even sqrt is a function that takes a good bit of processor time), perhaps, but still fast. I just bashed into the keyboard a ridiculously large double and it quite immediately gave me an answer. The sequence f(n) = n^2 grows rather quickly, so the loop doesn't need to check that many numbers. I'm sorry my loop "pains you".

Correction: I wouldn't be surprised if even sqrt() were a taxing function for the processor. Then again, many languages support math co-processors.
If you took co-processors out of the equation, the performance gap between the two algorithms would be smaller.

[jared.deckard]

Ok, optimization is not always the best idea.

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.

[Skydiver]

jared.deckard, on 11 July 2012 - 10:52 PM, said:

Ok, optimization is not always the best idea.

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 for-loop. 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 re-implement 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.

[zainsiddiqui14]

jared.deckard, on 11 July 2012 - 10:52 PM, said:

Ok, optimization is not always the best idea.

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.

[Wolman]

Modulus. The squareroot of a perfect square modulus 1 will be 0.

25
squareroot=5
5%1=0

[Skydiver]

Wolman, on 12 July 2012 - 05:32 AM, said:

Modulus. The squareroot of a perfect square modulus 1 will be 0.

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?

[Wolman]

Skydiver, on 12 July 2012 - 05:49 AM, said:

Wolman, on 12 July 2012 - 05:32 AM, said:

Modulus. The squareroot of a perfect square modulus 1 will be 0.

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

[Wolman]

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:

Modulus. The squareroot of a perfect square modulus 1 will be 0.

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