Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematica perfect square number detector oddity

  1. Nov 11, 2005 #1
    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.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted