Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Why is y a local variable here?

• To: mathgroup at smc.vnet.net
• Subject: [mg63217] Re: Why is y a local variable here?
• From: "Steven T. Hatton" <hattons at globalsymmetry.com>
• Date: Mon, 19 Dec 2005 07:01:13 -0500 (EST)
• References: <200512130841.DAA08255@smc.vnet.net> <976C0928-EE8E-4FE2-824E-FE1F2C3636EF@omegaconsultinggroup.com> <dnv444$oas$1@smc.vnet.net> <do0ll8$43k$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Peter Pein wrote:

>> SDP[0, x_] := x
>> SDP[n_Integer?Positive, x_] := Module[{sd, srp = Sqrt[Prime[n]]},
>>     sd[y_] = SDP[n - 1, y];
>>     Expand[sd[x + srp] sd[x - srp]]]
>> 
>> SDP[5, x]
>> 
>> Maeder makes in interesting observation at the bottom of page 221 in
>> _Programming in Mathematica_.
>> 
>> Steven
>> 
> Hi Steven,
> 
>   if you want to save evaluation time with the sd[]-construct, this will
>   fail,
> because sd[] will be redefined with evevery call of SDP[]. In that case
> you should follow the standard procedure:
> SDP[0,x_]=x; SDP[n_,x_}:=SDP[n,x]=...

Here's the original code:

(* :Copyright: 1989-1996 by Roman E. Maeder *)
(* :Sources: Roman E. Maeder. Programming in Mathematica, 3rd ed.
Addison-Wesley, 1996.*)
(* :Discussion: See Sections 4.7 and 5.5 of "Programming in Mathematica"*)

BeginPackage["ProgrammingInMathematica`SwinnertonDyer`"]

SwinnertonDyerP::usage = "SwinnertonDyerP[n, var] gives the minimal
polynomial of the sum of the square roots of the first n primes."

Begin["`Private`"]
SwinnertonDyerP[ 0, x_ ] := x
SwinnertonDyerP[ n_Integer?Positive, x_ ] :=
    Module[{sd, srp = Sqrt[Prime[n]]},
        sd[y_] = SwinnertonDyerP[n-1, y];
        Expand[ sd[x + srp] sd[x - srp] ] ]
End[]
EndPackage[]

Each evaluation of SwinnertonDyerP[ n_Integer?Positive, x_ ] /; n>1 will
assign the value of SwinnertonDyerP[n-1, y] to its local sd.  Notice that
Expand[ sd[x + srp] sd[x - srp] ] will only be evaluated after sd[y_] =
SwinnertonDyerP[n-1, y] has completed.  That means the local sd[] will
never hold an unevaluated SwinnertonDyerP[n-1, y].  The
SwinnertonDyerP[n-1, y] will have been replaced by simple expressions
involving only times and y$ (or x from the top of the stack).

This means the stack is only constructed once, and all Expand[ sd[x + srp]
sd[x - srp] ] ] are simple evaluations as the stack is popped.  The sd[]
are never, as far as I can see, redefined.  If I use a global sd, the
algorithm works, and the local variables are not created.  The time of
evaluation is, however, not affected.

The majority of the time seems to be spent on the Expand[] evaluations.
Removing it entirely from the algorithm, and simply returning the product
sd[x + srp] sd[x - srp] increases the execution time considerably.  But
evaluating Expand[%] on the result takes far longer than doing it within
the algorithm.

-- 
The Mathematica Wiki: http://www.mathematica-users.org/
Math for Comp Sci http://www.ifi.unizh.ch/math/bmwcs/master.html
Math for the WWW: http://www.w3.org/Math/

• Follow-Ups:
  • Re: Re: Why is y a local variable here?
    • From: Daniel Lichtblau <danl@wolfram.com>

• References:
  • Why is y a local variable here?
    • From: "Steven T. Hatton" <hattons@globalsymmetry.com>