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)
(https://app.dataquest.io/m/1027/numpy-boolean-masks-practice-problems/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

Hi @luke.niklaus

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

image

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.

image

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 :slight_smile:

2 Likes

oh yeah my bad. :woman_facepalming:

now the diff is of about 1 sec
image

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! :slight_smile: Have a good day!

1 Like