[Date Index]
[Thread Index]
[Author Index]
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?**
| |