MathGroup Archive 2007

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

Search the Archive

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

  • To: mathgroup at smc.vnet.net
  • Subject: [mg83593] Re: [mg83578] Re: Fast way of checking for perfect squares?
  • From: DrMajorBob <drmajorbob at bigfoot.com>
  • Date: Sat, 24 Nov 2007 04:08:42 -0500 (EST)
  • References: <200711200842.DAA06940@smc.vnet.net> <1008536.1195647042989.JavaMail.root@m35> <19518911.1195819385796.JavaMail.root@m35>
  • Reply-to: drmajorbob at bigfoot.com

Very nice!

originalQ = IntegerQ@Sqrt@# &;
treatQ = intSqrt[#]^2 == # &;
simon = Round[Sqrt[N[#]]]^2 == # &;
lichtblau[ee_] :=
  Module[{prec = Log[10., ee], sqrt},
   sqrt = Sqrt[N[ee, prec + $MachinePrecision]];
   sqrt == Round[sqrt]]
maximRytin[x_] :=
  Pick[x, Unitize@FractionalPart@Sqrt@N[x, 1 + Ceiling@Log[10, Max@x]],
    0]

k = 60;
data = Flatten@
    Table[{#^2, #^2 + 1, #^2 - 1} &@
      RandomInteger[{10^k, 10^(k + 1)}], {10^4}];
Timing[s1 = Select[data, originalQ];]
Timing[s2 = Select[data, treatQ];]
Timing[s4 = Select[data, lichtblau];]
Timing[s6 = maximRytin@data;]
s1 == s2 == s4 == s6
Length /@ {s1, s2, s4, s6}

{52.516, Null}

{2.015, Null}

{1.141, Null}

{0.234, Null}

True

{10000, 10000, 10000, 10000}

Bobby

On Fri, 23 Nov 2007 04:36:01 -0600, <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 che=
cks
>> >> 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 applicatio=
n
>> >> has a LOT more numbers to test than this.  This was a question pos=
ed  =

>> 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 littl=
e
>> >> 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 we=
ll  =

>> -
>> >> 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 slowSqu=
areQ:
>>
>> >> 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 wh=
ich
>> >> 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 filt=
er:
>>
>> >> 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
>
>
>



-- =

DrMajorBob at bigfoot.com


  • Prev by Date: Re: Database like "left join" or SAS like Merge function
  • Next by Date: Re: Re: Fast way of checking for perfect squares?
  • Previous by thread: Re: Re: Fast way of checking for perfect squares?
  • Next by thread: Re: Fast way of checking for perfect squares?