Mathematica - Fast way of checking for perfect squares?

Author

Fast way of checking for perfect squares?

michael.p.croucher@googlemail.com

2007-11-20, 4:29 am

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

Januk

2007-11-21, 4:42 am

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...@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

Szabolcs Horvát

2007-11-21, 4:42 am

michael.p.croucher@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.

You could try working with floating point numbers:

In[1]:= data=Table[RandomInteger[100000000],{100
000}];

In[2]:= slowSquareQ:=IntegerQ[Sqrt[#1]]&

In[3]:= Select[data,slowSquareQ]//Timing
Out[3]=
{3. 921,{2241009,279841,32307856,1817104,860
81284,1002001,72012196,53743561,72880369
,94984516,19360000,31956409,8105409,5617
5025,55875625}}

In[4]:= Select[Sqrt@N[data],FractionalPart[#]==0
&]//Timing
Out[4]=
{0.218,{1497.,529.,5684.,1348.,9278.,1001.,8486.,7331.,8537.,9746.,4400.,5653.,2847.,7495.,7475.}}

In[5]:= Round[Last[%]^2]
Out[5]=
{2241009,279841,32307856,1817104,8608128
4,1002001,72012196,53743561,72880369,949
84516,19360000,31956409,8105409,56175025
,55875625}

In[6]:= %5 == Last[%3]
Out[6]= True

--
Szabolcs

Jean-Marc Gulliet

2007-11-21, 4:42 am

michael.p.croucher@googlemail.com wrote:

> 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.

Daniel Lichtblau's reply to the thread "Changing Pure Function in
Module" (Jul 14 2001) contains the code of a fast function that tests
for perfect squareness (see Daniel Lichtblau's squaretest2 function
below). You should read Daniel's reply for detailed explanations,
additional code, and benchmarking, at

http://groups.google.com/group/comp...b31817c4a697041

On my system, squaretest2 is about twice faster than slowSquareQ.

In[8]:= squaretest2[ee_] :=
Module[{prec = Log[10., ee], sqrt},
sqrt = Sqrt[N[ee, prec + $MachinePrecision]];
sqrt == Round[sqrt]]

data = Table[RandomInteger[10000000000], {100000}];

In[10]:= Select[data, squaretest2] // Timing

Out[10]= {6.203, {}}

In[11]:= mobSquareQ := If[MoebiusMu[#1] == 0, True, False] &
Select[data, mobSquareQ]; // Timing

Out[12]= {8.578, Null}

In[13]:= slowSquareQ := IntegerQ[Sqrt[#1]] &
Select[data, slowSquareQ] // Timing

Out[14]= {12.235, {}}

HTH,
--
Jean-Marc

DrMajorBob

2007-11-21, 8:18 am

I do have a faster method or two, using an "integer square root" function:

Clear[intSqrt, intSqrtGuess, intSqrtIterFirst, intSqrtIter]
intSqrtGuess[x_] := intSqrtIterFirst[x, IntegerPart@Sqrt@N@x]
intSqrtIterFirst[x_, y_] := y + Floor[(x - y^2)/(2 y)]
intSqrt[x_?IntegerQ] := Which[
x < 4, 1,
x < 9, 2,
x < 16, 3,
x < 25, 4,
True, FixedPoint[intSqrtIter[x], intSqrtGuess[x]]]
intSqrtIter[x_] = # + Floor[Min[0, x - #^2]/(2 #)] &;

data = Table[RandomInteger[10^10], {5*10^5}];
slowSquareQ = IntegerQ@Sqrt@# &;
squareQ = intSqrt[#]^2 == # &;
fasterSquareQ = intSqrtGuess[#]^2 == # &;
Timing[s1 = Select[data, slowSquareQ];]
Timing[s2 = Select[data, squareQ];]
Timing[s3 = Select[data, fasterSquareQ];]
s1 == s2 == s3

{48.656, Null}

{16.547, Null}

{7.312, Null}

True

Length@s2

2

I know that squareQ works and I believe fasterSquareQ is reliable as
well... but I don't have a ready proof at the moment.

All this means IntegerPart@Sqrt@N@x is MUCH faster than IntegerQ@Sqrt@x,
which is a bit surprising to me!

Bobby

On Tue, 20 Nov 2007 02:42:09 -0600, <michael.p.croucher@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
>
>
>
>
>
>
>
>
>

--

DrMajorBob@bigfoot.com

Fred Simons

2007-11-21, 8:18 am

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.croucher@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
>
>
>
>
>
>
>
>
>
>

DrMajorBob

2007-11-22, 4:40 am

My "fasterSquareQ" is still faster than Daniel's function... though I
can't imagine why!

Clear[intSqrt, intSqrtGuess, intSqrtIterFirst, intSqrtIter]
intSqrtGuess[x_] := intSqrtIterFirst[x, IntegerPart@Sqrt@N@x]
intSqrtIterFirst[x_, y_] := y + Floor[(x - y^2)/(2 y)]
intSqrt[x_?IntegerQ] := Which[
x < 4, 1,
x < 9, 2,
x < 16, 3,
x < 25, 4,
True, FixedPoint[intSqrtIter[x], intSqrtGuess[x]]]
intSqrtIter[x_] = # + Floor[Min[0, x - #^2]/(2 #)] &;

slowSquareQ = IntegerQ@Sqrt@# &;
squareQ = intSqrt[#]^2 == # &;
fasterSquareQ = intSqrtGuess[#]^2 == # &;
lichtblau[ee_] :=
Module[{prec = Log[10., ee], sqrt},
sqrt = Sqrt[N[ee, prec + $MachinePrecision]];
sqrt == Round[sqrt]]

data = Table[RandomInteger[10^10], {5*10^5}];
Timing[s1 = Select[data, slowSquareQ];]
Timing[s2 = Select[data, squareQ];]
Timing[s3 = Select[data, fasterSquareQ];]
Timing[s4 = Select[data, lichtblau];]
s1 == s2 == s3 == s4

{48.266, Null}

{16.5, Null}

{7.281, Null}

{15.937, Null}

True

Bobby

On Wed, 21 Nov 2007 01:52:27 -0600, Jean-Marc Gulliet
<jeanmarc.gulliet@gmail.com> wrote:

> michael.p.croucher@googlemail.com wrote:
>
>
> Daniel Lichtblau's reply to the thread "Changing Pure Function in
> Module" (Jul 14 2001) contains the code of a fast function that tests
> for perfect squareness (see Daniel Lichtblau's squaretest2 function
> below). You should read Daniel's reply for detailed explanations,
> additional code, and benchmarking, at
>
> http://groups.google.com/group/comp...b31817c4a697041
>
>
> On my system, squaretest2 is about twice faster than slowSquareQ.
>
> In[8]:= squaretest2[ee_] :=
> Module[{prec = Log[10., ee], sqrt},
> sqrt = Sqrt[N[ee, prec + $MachinePrecision]];
> sqrt == Round[sqrt]]
>
> data = Table[RandomInteger[10000000000], {100000}];
>
> In[10]:= Select[data, squaretest2] // Timing
>
> Out[10]= {6.203, {}}
>
> In[11]:= mobSquareQ := If[MoebiusMu[#1] == 0, True, False] &
> Select[data, mobSquareQ]; // Timing
>
> Out[12]= {8.578, Null}
>
> In[13]:= slowSquareQ := IntegerQ[Sqrt[#1]] &
> Select[data, slowSquareQ] // Timing
>
> Out[14]= {12.235, {}}
>
> HTH,

--

DrMajorBob@bigfoot.com

DrMajorBob

2007-11-22, 4:40 am

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.simons@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.croucher@googlemail.com wrote:
>
>
>

--

DrMajorBob@bigfoot.com

2007-11-22, 4:40 am

Hi Mike,

here is still another pretty fast method:

Calculate all possible squares and take the intersection with your data:

E.g.:

data=Table[RandomInteger[n=10000000000],
{100000}];

t=Range[100000]^2;//Timing

Intersection[t,data]//Timing

this produces:

{0.078,Null}

{0.266,{2876498689}}

this takes a time of approx. 0.3 sec.

hope this helöps, Daniel

michael.p.croucher@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

>

>

>

>

>

>

>

>

m.r@inbox.ru

2007-11-23, 8:16 am

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@inbox.ru

On Nov 22, 4:03 am, DrMajorBob <drmajor...@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...@tue.nl> wrote:
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> --
>
> DrMajor...@bigfoot.com

DrMajorBob

2007-11-24, 4:40 am

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@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@inbox.ru
>
> On Nov 22, 4:03 am, DrMajorBob <drmajor...@bigfoot.com> wrote:
my[color=darkred]
[color=darkred]
=
[color=darkred]
[color=darkred]
=
[color=darkred]
[color=darkred]
cks[color=darkred]
n[color=darkred]
ed =
[color=darkred]
a[color=darkred]
e[color=darkred]
[color=darkred]
ll =
[color=darkred]
areQ:[color=darkred]
=
[color=darkred]
ich[color=darkred]
So[color=darkred]
er:[color=darkred]
[color=darkred]
=
[color=darkred]
>
>
>

-- =

DrMajorBob@bigfoot.com

Andrzej Kozlowski

2007-11-24, 4:40 am

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@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@inbox.ru
>
> On Nov 22, 4:03 am, DrMajorBob <drmajor...@bigfoot.com> wrote:
>
>

giovanni resta

2007-11-29, 8:18 am

michael.p.croucher@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

I've seen that Mathematica internally uses this function:

PerfectSquareQ[n_] :=
JacobiSymbol[n, 13] =!= -1 && JacobiSymbol[n, 19] =!= -1 &&
JacobiSymbol[n, 17] =!= -1 && JacobiSymbol[n, 23] =!= -1 &&
IntegerQ[Sqrt[n]];

g.

Sponsored Links