Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Changing Pure Function in Module

• To: mathgroup at smc.vnet.net
• Subject: [mg29861] Re: [mg29822] Changing Pure Function in Module
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Sat, 14 Jul 2001 01:36:51 -0400 (EDT)
• References: <200107120652.CAA28184@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Flip at 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


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

• References:
  • Changing Pure Function in Module
    • From: Flip@safebunch.com