In this lesson, we will find whether a given number is a perfect square or not.

We will implement several implementations of this problem and step-by-step move towards better implementations. Keep in mind we are about to dive into looking at the following perspective: how do we write a program efficiently? Hence can we improve our implementation? So let’s start!

Perfect square number

Write and run a program that takes inputs until the user enters -1 and tells whether the input number is a perfect square or not.

Sample input

25 16 23 -1

Sample output

25 is a perfect square
16 is a perfect square
23 is not a perfect square

A perfect square is a number that can be expressed as the product of an integer (let us call that number a verifier) by itself or as the second exponent of an integer. For example, 9 is a perfect square because 3×3=32=93 \times 3 = 3^2 = 9

How do we find out whether a given number is a perfect square? Just think about the following question:

For a perfect square SS, is it possible that the verifier vv is bigger then SS so that v×v=Sv \times v=S?

No vv cannot exceed SS. This means one naive idea could be to just iterate through all the possible values of v lower than or equal to SS and check if the square of vv is equal to SS.

Your task is to implement a function that checks whether the entered number is a perfect square or not. Let’s call this function isPerfectSquare(), which returns true if the parameter received is a perfect square and otherwise returns false. For example, isPerfectSquare(25) should return true and isPerfectSquare(50) should return false.

Playground for your implementation

Write down your code in the following playground:

#include <iostream>
using namespace std;
bool isPerfectSquare(int num)
{

    // Write your code here:
       
}

int main()
{
    int num=0;
    cout << "Number to know is a perfect square : ";
    cin>>num;
    for(int cnt=0;num!=-1;cnt++)
    {
        if(isPerfectSquare(num))
        {
            cout<<" The number is a perfect square. \n";
        }
        else
        {
            cout<<" The number is not a perfect square. \n";
        }
    cout << "Number to know is a perfect square : ";
    cin>>num;
    }
    return 0;
}
Playground to write your own code

Implementations

Let us discuss several implementations.

Implementation 1: Naive version

Let’s look at perhaps the most naive idea.

Suppose we have the input number num (e.g. 25) for testing to be a perfect square. We start the loop from 0 to num, i.e. 25 for our example.

In each iteration, we will multiply each iteration value by itself and test if the square yields the given number, if it is so, we will set the test variable to true (which was set in the initialization as false). After the loop ends, we will return the test variable (which will be holding whether a verifier was found or not).

So, our isPerfectSquare() function looks like this:

Press + to interact
bool isPerfectSquare(int num)
{
    bool test=false;
    for(int s=0;s<num;s++)
    {
        if(s*s==num)   // test will only be updated if there exists an s such that s*s = num
          test=true;
    }
    return test;
}

The main part should have a loop that takes numbers, one by one, in num from the stream, Then in each iteration, we pass num to an isPerfectSquare() fucntion that checks num is a perfect square or not, and displays the message accordingly.

Instruction: You can copy the isPerfectSquare() function and click Run in the above playground.

Identifying inefficiency.

Question

Have you noticed a slight flaw naivety with bool isPerfectSquare(int num)? The above function completes an iteration of the for loop, even though it has found that num is a perfect square. Look at these lines:

if(s*s==num) 
    test=true;

During the loop iteration, if the condition s*s==num is true, it will execute test=true. Hence, it has found that num is a perfect square. Should we continue executing or should we stop?

Show Answer

Implementation 2: Using break statement

Let us take advantage of the break statement to stop the loop when we have found a perfect square. So our isPerfectSquare() function will look like this:

bool isPerfectSquare(int num)
{
    bool test=false;
    for(int s=0;s<num;s++)
    {
      if(s*s==num)
      {
          test=true;
          break;
      }  
    }
    return test;
}
The isPerfectSquare() function (using break statement)

The program will return true when it gets a perfect square. Not only this, but it also stops the loop immediately when it passes the perfect square test. This can be easily done by using the immediate return statement as well, Which can be seen in the second code (in tab).

Perfect square

Question

What if a given number num is not a perfect square? For example, if we pass 26 as an argument,how many times will the loop be executed?

Show Answer

Let us have a quiz regarding the above two implementations. We recommend pausing for a moment and rethinking what the code of isPerfectSquare() is doing in the both above implementations.

1

If num is 100, how many iterations will the isPerfectSquare() function take in implementation 1?

A)

100

B)

10

Question 1 of 40 attempted

Implementation 3: Reducing the range

For a large value of num, running the iteration num time. For example, is too much e.g., if the num has a value close to ≈230\approx 2^{30}, and the num is not a perfect square, then the loop will execute ≈230\approx 2^{30} times. How can we reduce these iterations?

If the number is very large, let us say any number greater than 4, then we do not need to check for a perfect square above num/2. For example, for num=101, any value v>=50v>=50,v2v^2 will always be bigger than 101. Similarly, you may take any value of num ≥4\ge 4. Hence, we can shrink the search space by half.

So our isPerfectSquare() function is as follows:

Press + to interact
bool isPerfectSquare(int num)
{
    for(int s=0;s<num/2;s++)
    {
          if(s*s==num)
          {
            return true; // function will return true when it gets the perfect square
          }  
    }
    return false; // it will return false after num/2 iteration of loop
}

Finding logical error

Q

In implementation 3 let’s say we have num having a value 0, 1 or 4. The output should be true. However, what will be the output of the above function?

A)

false

B)

true

Exercise (fixing the logical error)

Add implementation 3 in the playground above and check for inputs 0, 1, or 4. In all three cases, it should return true. Modify the above implementation to fix the above-mentioned bug.

Is there any other way to make implementation 3 more efficient? Take time and think about it.

Yes, we can make this function more efficient. That brings us to the next implementation.

Implementation 4: Efficient implementation

The idea is that, for each iteration, we check the following,

  • If we get a perfect square , s*s==num, we return true.

  • Similarly, if we have s*s<num, then we should keep iterating and moving forward because the potential verifier could be found.

  • However, what if s*s>num then Should we move forward, in searching for a verifier? The answer is ‘no’. This is because all the other values after this s will make their square even bigger than num. Hence, we should stop and return false immediately, because there is no verifier for this number.

Let’s write a function that is more efficient in using the above idea:

Press + to interact
bool isPerfectSquare(int num)
{
    for(int s=0;s<num;s++)
    {
        if(s*s==num)
            return true; // function will return true when he gets the perfect square
        else if(s*s > num)
            return false; // function will return false if a number is not perfect square
    }
    
}

Instruction: Write the above code inside the playground and test it for a very big number like 1073741823 meaning 230−12^{30}-1 (you may verify it on a calculator).

Implementation 5: Find a logical error

Notice that in the following code, you will find an even simpler and more elegant implementation, but there is a small logical error that you need to fix.

Copy the code below and paste it into the above playground for execution.

Instruction: Executes the program step-by-step on a few inputs. For example, for 25, 26, 9, or 10.

Press + to interact
bool isPerfectSquare(int num)
{
    int s;
    for(s=0; s*s <= num; s++)
    {
      // This loop will end when s*s > num
    }
    return (s*s==num); // it will return true when s*s is equal to num
}

Exercise: Fixing the bug

On the num=25, it should have returned true. However, it is returning false.Execute the code Step by step and fix the bug.

Comparison of implementations

If we look closely, implementations 1, 2, and 3 run around n times (where n is our number), implementations 4 and 5 execute around the square root of n times.

How big of a difference is nn vs n\sqrt{n}?

If we take a number as big as 230−12^{30}-1. Implementation 4 and 5 will be around 2152^{15} times faster than the previous three implementations. This is a huge improvement. We can imagine that if implementations 4 and 5 take one second to execute for a big number, then the first three will take almost 2152^{15} Seconds This is around 9.1 hours. This is a huge improvement.

Complete implementation

Below is the complete perfect square program with all the implementations.

Press + to interact
#include <iostream>
using namespace std;
bool isPerfectSquareI1(int num)
{
    bool test=false;
    for(int s=0;s<num;s++)
    {
        if(s*s==num)   // test will only be updated if there exists an s such that s*s = num
          test=true;
    }
    return test;
}
bool isPerfectSquareI2(int num)
{
    bool test=false;
    for(int s=0;s<num;s++)
    {
      if(s*s==num)
      {
          test=true;
          break;
      }  
    }
    return test;
}
bool isPerfectSquareI3(int num)
{
    for(int s=0;s<num/2;s++)
    {
          if(s*s==num)
          {
            return true; // function will return true when it gets the perfect square
          }  
    }
    return false; // it will return false after num/2 iteration of loop
}
bool isPerfectSquareI4(int num)
{
    for(int s=0;s<num;s++)
    {
        if(s*s==num)
            return true; // function will return true when he gets the perfect square
        else if(s*s > num)
            return false; // function will return false if a number is not perfect square
    }
    
}
bool isPerfectSquareI5(int num)
{
    int s;
    for(s=0; s*s <= num; s++)
    {
      // This loop will end when s*s > num
    }
    return ((s-1)*(s-1)==num);  
}
int main()
{
    int num=0;
    cout << "Number to check for perfect square (-1 to stop): ";
    cin>>num;   // num = 1073741823 (2^30-1)
    for(int cnt=0;num!=-1;cnt++)
    {
        if(isPerfectSquareI1(num))
        //if(isPerfectSquareI2(num))
        //if(isPerfectSquareI3(num))
        //if(isPerfectSquareI4(num))
        //if(isPerfectSquareI5(num))
        {
            cout<<num<<" is a perfect square. \n";
        }
        else
        {
            cout<<num<<" is not a perfect square. \n";
        }
        cout << "Number to check for perfect square (-1 to stop): ";
        cin>>num;
    }
    return 0;
}

Enter the input below

Instruction: Enter the values you want to check for perfect squares (ending with -1) in the text box above. For example, 20 49 100 85 -1.

We hope that you’ve enjoyed this problem solving walk-through, in which we first made the preliminary version of the program and then tweaked the code to make it more efficient. This is exactly how a programmer discovers the journey of reaching an elegant approach. We will follow the same approach of incrementally improving our program in the upcoming lessons too.