Re: Fast way of checking for perfect squares?
- To: mathgroup at smc.vnet.net
- Subject: [mg83452] Re: Fast way of checking for perfect squares?
- From: Januk <ggroup at sarj.ca>
- Date: Wed, 21 Nov 2007 02:41:51 -0500 (EST)
- References: <fhu6m6$6pd$1@smc.vnet.net>
Try doing it with machine precision: nSquareQ = (IntegerPart[Sqrt[N[#]]]^2 == #) & It seems to give me an answer in about 6% of the time that the original version takes. On Nov 20, 3:42 am, michael.p.crouc... at googlemail.com wrote: > Hi > > Lets say I have a lot of large integers and I want to check to see > which ones are perfect squares - eg > > data = Table[RandomInteger[10000000000], {100000}]; > > I create a function that takes the square root of each one and checks > to see if the result is an integer > > slowSquareQ := IntegerQ[Sqrt[#1]] & > > This works fine: > > Select[data, slowSquareQ] // Timing > > {11.39, {6292614276, 2077627561}} > > but I am wondering if I can make it faster as my actual application > has a LOT more numbers to test than this. This was a question posed a > few years ago in this very newsgroup and the suggestion was to use a > test of the form MoebiusMu[#]==0. > > Well the MoeboisMu function is new to me so I experimented a little > and sure enough when you apply the MoebiusMu function to a perfect > square number the result is zero. > > MoebiusMu[4] = 0 > > The problem is that lots of other numbers have this property as well - > eg > > MoebiusMu[8] =0 > > despite this minor problem I determined that applying the test > MoebiusMu[#]==0 on a list of integers is fater than my slowSquareQ: > > mobSquareQ := If[MoebiusMu[#1] == 0, True, False] & > Select[data, mobSquareQ]; // Timing > > gives a result of 8.156 seconds compared to 11.39 for slowSquareQ. On > my test data I had around 39,000 integers that passed this test which > is a shame but at least I have eliminated the other 61,000 or so. So > I thought that maybe I can use the faster MoebiusMu test as a filter: > > SquareQ := If[MoebiusMu[#1] == 0, slowSquareQ[#1], False] & > Select[data, SquareQ] // Timing > {11.312, {6292614276, 2077627561}} > > So after all that I have saved just a few tenths of a second. Not > very impressive. Can anyone out there do any better? > Please forgive me if I have made any stupid mistakes but I have a cold > at the moment. > > Best regards, > Mike