Register to reply 
Mathematica perfect square number detector oddity 
Share this thread: 
#1
Nov1105, 02:14 PM

P: 69

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) prescreen 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 nonsquares by 1, squares by themselves mod isqmod. isqli = DeleteCases[Union[inc /@ Range[0, isqmod^2]], 1]; // Generate 0isqmod^2, replace per above, filter out duplicates and toss the 1 used as a marker for nonsquares. 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 ultraeffective 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 nonsquares 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. 


Register to reply 
Related Discussions  
Perfect square  Calculus & Beyond Homework  11  
Number Thry: Divisibilty, perfect square.  Calculus & Beyond Homework  6  
Help needed in proving a number to be perfect square  General Math  12  
Perfect square  Linear & Abstract Algebra  10  
Perfect square?  Linear & Abstract Algebra  2 