# Discussion about provided solution to problem

I’m working through all the numpy practice problems at the moment and found an interesting case in the boolean indexing mission on page 9 (selecting perfect squares)

Given this array to find the perfect squares in:
`x = np.array([865, 395, 777, 912, 431, 42, 266, 989, 524, 498, 415, 941, 803, 850, 311, 992, 489, 367, 598, 914, 930, 224, 517, 143, 289, 144, 774, 98, 634, 819, 257, 932, 546, 723, 830, 617, 924, 151, 318, 102, 748, 76, 921, 871, 701, 339, 484, 574, 104, 363, 445, 324, 626, 656, 935, 210, 990, 566, 489, 454, 887, 534, 267, 64, 825, 941, 562, 938, 15, 96, 737, 861, 409, 728, 845, 804, 685, 641, 2, 627, 506, 848, 889, 342, 250, 748, 334, 721, 892, 65, 196, 940, 582, 228, 245, 823, 991, 146, 823, 557])`

I came up with this solution:
`squares = x[np.sqrt(x)%1==0]`

which is accepted as correct.

The solution however is this:
`ceil_sqrt = np.ceil(np.sqrt(x))`
`squares = x[ceil_sqrt * ceil_sqrt == x]`

Being a beginner this does look more complicated to me, however i’m sure that with my limited knowledge there’s stuff i’m not aware of.
It would be great to get some input to make me aware of what would make this a more elegant solution.

Thanks everyone!

2 Likes

I am not sure but it could be related to efficient execution time. The given solution is faster than your solution. So it may be related to the optimization of the code.

1 Like

They are just a couple of different approaches to the same problem. Yours is a slightly more clever one, and is fine for a limited set of numbers.

I say limited set of numbers because floating point calculations aren’t always reliable (because of precision issues), especially for very large numbers.

For a number like - `152415789666209426002111556165263283035677490`, your solution would result in the number being considered a perfect square, however it is not a perfect square. The official solution on the other hand works for that number as expected.

So, it’s not about having a more elegant solution. It’s about what is correct, logically and practically.

The DQ solution is quite straightforward and not at all complicated -

• You calculate the square root of the number

• You apply `np.ceil()` on it.

• This is done because the square root would be a `float`, and the square of a float is less likely to return the exact original number (because of precision issues) unless that number is a perfect square.
• You square the above output and compare to the number

• If they match, it’s a perfect square

As for @Rucha’s comment - Could you (Rucha) clarify how you concluded the given solution is faster than the one in this post? I just timed both of them and they are almost similar in execution time. Even for a much larger input array.

6 Likes

The more iterations you will run, DQ’s solution’s time varies less as compared to @luke.niklaus.

Also I got this time execution code for something else I was looking for on STO. so in case, this is not the right method, do let me know, the correct one.

Thanks.

2 Likes

You are using the same `start_time` for both of those. That won’t give you an accurate runtime of each because for Luke’s solution you are accumulating the time for both of those runs. You need to set separate `start_times` for each and compare.

For an array of 10000 items -

Pretty much comparable, I would say.

Code to test -

``````import time
x = np.random.randint(10000, size=100000)
dq_start = time.time()

ceil_sqrt = np.ceil(np.sqrt(x))
squares1 = x[ceil_sqrt * ceil_sqrt == x]

print("DQ solution: ", time.time() - dq_start)

luke_start = time.time()

squares2 = x[np.sqrt(x)%1==0]

print("Luke solution: ", time.time() - luke_start)
``````
2 Likes

Yeah I did that now, the time taken for DQ’s solution is still faster.

Yeah for less no. of data points, the difference is negligible. Only when I increase the data points the time shows a good enough difference.

2 Likes

That’s because of your `ceil_sqrt`.

np.ceil(np.sqrt(50))

You have that fixed for a square root of `50` and not one variable for the input `x`. For the same `x`, as my code above illustrates, the execution time is comparable (even for larger inputs).

But, regardless, this is detracting now from the original question, so I will let Luke ask any follow up questions

2 Likes

now the diff is of about 1 sec

2 Likes

Guys this is awesome and more than answers my question.
What i have left to do is to test out np.ceil() as at first sight it didn’t make 100% to me what it does which is probably why i perceived it as more complicated.

You make a good point though @the_doctor about using what is the most correct logically and practically.
I am working on this way of thinking that what makes sense for this example might not be the best solution universally.

Really good input guys, thanks for the discussion!

4 Likes

Hi @the_doctor,

Thanks for your explanation — it is a lot clearer to me now.

I have an extended question about `np.ceil()`. I tried the solution with a short testing array and printed it out step-by-step as below:

``````x = np.array([4, 9, 16, 20, 30])    # array for testing

print('np.sqrt(x):  ', np.sqrt(x))

ceil_sqrt = np.ceil(np.sqrt(x))
print('ceil_sqrt:  ', ceil_sqrt)

squares = x[ceil_sqrt * ceil_sqrt == x]
print('squares:  ', squares)
``````

The output is as below:

``````np.sqrt(x):   [2.         3.         4.         4.47213595 5.47722558]
ceil_sqrt:   [2. 3. 4. 5. 6.]
squares:   [ 4  9 16]
``````

From the output, it seems to me that although the output of `np.ceil()` is rounded (without any decimal numbers), but in reality, it stores the decimal numbers for future calculations. Is my interpretation correct? I just want to check if I understand it correctly.

I am not sure I understand your point. Why do you think it stores decimal numbers for future calculations?

Let’s take the last element (`30`) of `x` for example:

`np.sqrt(x)` returns 5.47722558
`ceil_sqrt` returns 6.
`squares` returns nothing

`squares` does not use `6.` (from `ceil_sqrt`), but instead use ` 5.47722558` (from `np.sqrt(x)`) , which does not return a match for perfect square. It is not a perfect square as `5.47722558 * 5.47722558` returns `30.000000054206335`.

To put it in another word, why do we use `np.ceil()` (in `ceil_sqrt`) that returns `6.` in this case?

I hope I explained my question well this time.

No. `squares` is still using `6`.

`ceil_sqrt` is `6`.

`ceil_sqrt * ceil_sqrt` is `36`.

`36` is not present in `x`. That’s why it returns nothing.

`30` is not a perfect square because `30` is not the product of some other integer multiplied by itself. That is by definition of a perfect square.

For `30` to be a perfect square it would have to be the product of an integer multiplied by itself. Which is not the case as `5.47722558` is not an integer.

That’s why we use `np.ceil()`. Because it gives us the next closest integer value and then we use that integer value to check if `30` is a perfect square or not.

2 Likes

I understood the parts that confused me earlier.
Thanks a lot! Have a good day!

1 Like