31 views

Skip to first unread message

Jul 12, 2001, 3:00:34 AM7/12/01

to

Hi All,

thank you to all who continue to respond to all of my questions ... and there

are always plenty of them.

I have the following function embedded in the findD code below.

a[1] =5;

a[n_]:= a[n] = (-1)^(n+1) (Abs[a[n-1]]+2)

In[225]:=

findD[n_]:=

Module[{c=0},NestWhile[(c++;(-1)^c(Abs[#]+2))&,5,JacobiSymbol[#,n]!=-1&]]

I would like to change the pure function to use the following (cleaner) function

that requires no starting value (and starts for n = 1).

In[255]:=

a[n_]:= a[n]= (-1)^(n+1)*(2n + 3)

Also, it would be important to test n prior to calling findD. If n is a perfect

square, findD will "never" converge. Is there a simple way to test if n is

square and tell the user ... try again ... n is a perfect square.

Again thank you for all of the help ... Wilson

Jul 13, 2001, 4:25:13 AM7/13/01

to

Hi,

> I have the following function embedded in the findD code below.

>

> a[1] =5;

>

> a[n_]:= a[n] = (-1)^(n+1) (Abs[a[n-1]]+2)

>

> In[225]:=

> findD[n_]:=

> Module[{c=0},NestWhile[(c++;(-1)^c(Abs[#]+2))&,5,JacobiSymbol[#,n]!=-1&]]

>

> I would like to change the pure function to use the following (cleaner) function

> that requires no starting value (and starts for n = 1).

>

> In[255]:=

> a[n_]:= a[n]= (-1)^(n+1)*(2n + 3)

So just do it, but with

a[n_Integer]/; Positive[n]:= a[n]= (-1)^(n+1)*(2n + 3)

the code is *not* "cleaner" it is just with out the recursion.

Why not use

a[n_Integer] /; Positive[n] := a[n] = (-1)^(n + 1)*(2n + 3)

and

findD1[n_] /; Head[Sqrt[n]] =!= Integer :=

Module[{i = 1, ai},

While[True,

If[JacobiSymbol[ ai = a[i++] , n] == -1, Break[]];

];

ai

]

>

> Also, it would be important to test n prior to calling findD. If n is a perfect

> square, findD will "never" converge. Is there a simple way to test if n is

> square

PerfectSquareQ[n_Integer]:=Head[Sqrt[n]] === Integer

Regards

Jens

Jul 13, 2001, 4:35:25 AM7/13/01

to

Hi Wilson:

Now that we know exactly what you want, it is easy to write a module for FindD:

FindD[n_]:=Module[{c=1,a},If[IntegerQ[Sqrt[n]],a="n is a perfect square",

While[JacobiSymbol[(-1)^(c+1)(2c+3),n]é-1,c=c+1];

a=(-1)^(c+1)(2c+3)];

Return[a]]

FindD[1929321]

n is a perfect square

FindD[567134594567891251143216731]

-15

Regards,

Ranko

In Message 42/124 From Fl...@safebunch.com Jul 12,01 02:52:35 AM-0400

Wilson wrote:

> Hi All,

>

> thank you to all who continue to respond to all of my questions ... and there

> are always plenty of them.

>

> I have the following function embedded in the findD code below.

>

> a[1] =5;

>

> a[n_]:= a[n] = (-1)^(n+1) (Abs[a[n-1]]+2)

>

> In[225]:=

> findD[n_]:=

> Module[{c=0},NestWhile[(c++;(-1)^c(Abs[#]+2))&,5,JacobiSymbol[#,n]!=-1&]]

>

> I would like to change the pure function to use the following (cleaner) function

> that requires no starting value (and starts for n = 1).

>

> In[255]:=

> a[n_]:= a[n]= (-1)^(n+1)*(2n + 3)

>

> Also, it would be important to test n prior to calling findD. If n is a perfect

> square, findD will "never" converge. Is there a simple way to test if n is

Jul 13, 2001, 4:44:43 AM7/13/01

to

squareQ[n_Integer] := IntegerQ[Sqrt[n]]

Orestis

<Fl...@safebunch.com> wrote in message news:9ijhui$ri5$1...@smc.vnet.net...

Orestis

<Fl...@safebunch.com> wrote in message news:9ijhui$ri5$1...@smc.vnet.net...

Jul 14, 2001, 1:42:51 AM7/14/01

to

Fl...@safebunch.com wrote:

>

> [...]

> Also, it would be important to test n prior to calling findD. If n is

> a perfect square, findD will "never" converge. Is there a simple way

> to test if n is square and tell the user ... try again ... n is a

> perfect square.

>

> Again thank you for all of the help ... Wilson

>

> [...]

> Also, it would be important to test n prior to calling findD. If n is

> a perfect square, findD will "never" converge. Is there a simple way

> to test if n is square and tell the user ... try again ... n is a

> perfect square.

>

> Again thank you for all of the help ... Wilson

With regards to this, some care should be exercised when using the

proposed IntegerQ{Sqrt[n]] test. Specifically, if n is large, this can

be quite slow. A (usually) faster test involves taking a numerical

approximation to the square root and checking that it is equal to its

rounded value.

squaretest1[ee_] := IntegerQ[Sqrt[ee]]

squaretest2[ee_] := Module[{prec=Log[10.,ee], sqrt},

sqrt = Sqrt[N[ee, prec+$MachinePrecision]];

sqrt == Round[sqrt]

]

We'll try them on a random large number, its square, and the square plus

1.

aa[digits_] := Random[Integer, 10^digits-1]

int = aa[10^5];

int2 = int^2;

In[50]:= Timing[squaretest1[int]]

Out[50]= {10.14 Second, False}

In[51]:= Timing[squaretest2[int]]

Out[51]= {0.51 Second, False}

In[54]:= Timing[squaretest1[int2]]

Out[54]= {0.66 Second, True}

In[55]:= Timing[squaretest2[int2]]

Out[55]= {1.1 Second, True}

In[56]:= Timing[squaretest1[int2+1]]

Out[56]= {10.76 Second, False}

In[57]:= Timing[squaretest2[int2+1]]

Out[57]= {1.1 Second, False}

The "naive" method wins only when we actually have a perfect square.

This is because Power uses a numerical approximation itself in internal

code to find the square root, in case it is exact. But most numbers are

not squares, so the explicit numeric approximation method will be better

if inputs tend to be large and random (or at least not heavily skewed

toward perfect squares).

Daniel Lichtblau

Wolfram Research

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu