WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Fast way of checking for perfect squares?

This will also work with Mathematica 5.1 and 5.2 (which do not have  
Unitize but have Pick) with only a slight change:

Pick[data,
    Thread[
     FractionalPart@Sqrt@N[data, 1 + Ceiling@Log[10, Max@data]] == 0.]]


Andrzej Kozlowski


On 23 Nov 2007, at 19:36, m.r at inbox.ru wrote:

> This can be sped up slightly by using listability:
>
> In[1]:= data = RandomInteger[{10^50, 10^60}, 10^5];
>  data = Join[data^2, data^2 + 1];
>
> In[3]:= Timing[Pick[data,
>  Unitize@ FractionalPart@ Sqrt@
>   N[data, 1 + Ceiling@ Log[10, Max@ data]],
>  0] == Take[data, 10^5]]
>
> Out[3]= {1.453, True}
>
> Maxim Rytin
> m.r at inbox.ru
>
> On Nov 22, 4:03 am, DrMajorBob <drmajor... at bigfoot.com> wrote:
>> And that's the new speed champion for this problem!
>>
>> It fails for squares of 15-digit and bigger integers, however...  
>> and my
>> earlier "fasterSquareQ" fails for squares of 32-digit and bigger  
>> integers.
>>
>> Of the three reliable methods, Daniel Lichtblau's is slightly  
>> faster than
>> my intSqrt method, and the OP's "slowSquareQ" is fastest for perfect
>> squares, but slowest for non-squares (which are far more common).
>>
>> Bobby
>>
>>
>>
>> On Wed, 21 Nov 2007 05:00:19 -0600, Fred Simons  
>> <f.h.sim... at tue.nl> wrote:
>>> Since your integers are not too large, the following works fine  
>>> and fast:
>>
>>> Select[data, Round[Sqrt[N[#]]]^2 == # &]
>>
>>> Fred Simons
>>> Eindhoven University of Technology
>>
>>> 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
>>
>> --
>>
>> DrMajor... at bigfoot.com
>
>
  • Prev by Date: Re: Re: Fast way of checking for perfect squares?
  • Next by Date: Mathematica 6 Automated Compatibility Tools
  • Previous by thread: Re: Fast way of checking for perfect squares?
  • Next by thread: Re: Re: Fast way of checking for perfect squares?