Mathematica perfect square number detector oddity

[LarrrSDonald]

This may possibly be the wrong place for this, but I figure it's the closest area around since it's mostly software related I think. It may be a lame question, I'm not entirely at home in this area to say the least - this is a horizon streaching game more then anything on my part.

For reasons I won't go into, I was toying with ways to determine if a number was a perfect square number, i.e. if it's square root is integer. I started off doodling in mathematica, starting with the ultra simple:

IsSql[x_] := IntegerQ[Sqrt[x]];

Nothing fancy there, do the root and see if it's an integer. Works like a charm, though not especially fast:

Timing[IsSql /@ Range[0, 1000000];]

Result: {39.688 Second, Null}

Times obviously vary with CPU/Load/whatnot, but that's how it went - my baseline if you will. I ran it a few times with no spectacular variation.

Next, I started messing with a modula deal. As is common knowledge (I think), squares end in certain digits mod 10, 100, etc. This is a rather common (I understand) pre-screen before doing the grunt work of a Sqrt. I figured that a decent way to exclude more would be to simply include more factors in the modula, check the results up to modula^2 (nothing else should effect it I think, can't prove that straight up for the general case but it certainly feels right) and check vs those. Basic plan thus:


isqmod = 2^4*3^2*5;
// My base, here set rather arbitrarily to be largeish but not huge

inc[x_] := If[IntegerQ[Sqrt[x]], Mod[x, isqmod], -1]
// Funtion to replace non-squares by -1, squares by themselves mod isqmod.

isqli = DeleteCases[Union[inc /@ Range[0, isqmod^2]], -1];
// Generate 0-isqmod^2, replace per above, filter out duplicates and toss the -1 used as a marker for non-squares. Store the resulting list in isqli.

IsSq[x_] := MemberQ[isqli, Mod[x, isqmod]] && IntegerQ[Sqrt[x]]
// The actual checker function, do the modula, see if it's a member, if it is then it might be square so go ahead with the Sqrt otherwise move on.


I should perhaps mention that the above is clearly not the mostly ultra-effective way to do this, but I figure it's a one shot deal to calc the list and I'm just toying around anyway.

Now, with the modula set to 720 as above (2^4 3^2 5), isqli is 48 long. 14 out of 15 numbers ought to be clear non-squares with this (rather small) modula. Rerunning the previous test with the new funciton:

Timing[IsSq /@ Range[0, 1000000];]

Result: {20.279 Second, Null}


Ok, assuming I haven't lost you so far, what gives? It's faster (almost 2x) so it can't be doing the Sqrts for all of them still, yet it seems odd that replacing 14/15 Sqrts with a modula and a number lookup in a 48 number list shouldn't make more of a difference. Is there a reasonable way to speed up lookup, perhaps indicate that the list is ordered (after making sure it is)? It would obviously be possible to do a more static thing for a specific modula, but it'd be nice to be able to expand it to trade longer list generation for heavier screen when crunching through larger sets. General advice also appechiated, as you can probably tell I'm rather a novice at this.

 

[mmwave]

Thank you for sharing your findings and questions regarding determining perfect square numbers. As a scientist with expertise in mathematics and computer science, I would like to offer some insights and suggestions for your approach.

Firstly, I would like to commend you for your creative thinking and experimentation in trying to optimize the process of determining perfect square numbers. However, I have a few comments and suggestions that may help improve your approach.

1. Modulo operations can be expensive. While using a modulus to check for perfect squares does help narrow down the possibilities, the actual computation of the modulus can be computationally expensive. In your case, you are using a relatively large modulus of 720, which may still require significant computation time. It may be worth exploring other ways to narrow down the possibilities, such as using prime factorization or other mathematical properties of perfect squares.

2. Speed vs accuracy trade-off. In your approach, you are sacrificing some accuracy for speed by using a relatively small list of numbers to check for perfect squares. While this may work for smaller ranges, it may not be as effective for larger ranges. It may be worth considering a balance between accuracy and speed, or even exploring parallel processing techniques to speed up the computation.

3. Use of pre-computed tables. As you mentioned, generating the list of numbers to check for perfect squares is a one-time process. In this case, it may be worth pre-computing and storing the list for future use, rather than generating it every time the function is called.

4. Consider using built-in functions. Mathematica has built-in functions for checking perfect squares, such as SquareFreeQ or PerfectSquareQ. These functions have been optimized for speed and accuracy, so it may be worth considering using them instead of creating your own function.

In conclusion, while your approach shows promise, there may be other ways to optimize the process of determining perfect square numbers. I hope my suggestions have been helpful, and I encourage you to continue exploring and experimenting with different approaches. Happy coding!

 

[tacman]

First of all, don't worry about asking questions related to Mathematica here. This is a great place to discuss software and programming in general.

Now, to address your question about the oddity in the timing results. There are a few factors that could be contributing to the faster timing with the modula approach. One possibility is that the modula operation is faster than taking the square root, so even though you are checking more numbers, it is still faster overall. Another possibility is that the list generation and lookup process is more efficient than the repeated square root calculations.

As for improving the performance, one idea would be to pre-compute the list of squares for a given modula and store it in a variable. This way, you wouldn't have to generate the list every time the function is called. Additionally, you could use the built-in function "Compile" to create a compiled version of your function, which can often improve performance significantly.

Overall, it's great to see that you are experimenting and trying to optimize your code. Keep exploring and learning, and you'll continue to improve in this area.