Register to reply

Mathematica perfect square number detector oddity

by LarrrSDonald
Tags: mathematica, number, oddity, perfect, square
Share this thread:
LarrrSDonald
#1
Nov11-05, 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) 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.
Phys.Org News Partner Science news on Phys.org
Apple to unveil 'iWatch' on September 9
NASA deep-space rocket, SLS, to launch in 2018
Study examines 13,000-year-old nanodiamonds from multiple locations across three continents

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