MathGroup Archive 2001

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

Search the Archive

Re: Changing Pure Function in Module


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


  • Prev by Date: 1) Numerical precision, 2) Bug in Plot?
  • Next by Date: Re: Integration by substitution
  • Previous by thread: Changing Pure Function in Module
  • Next by thread: Re: Changing Pure Function in Module