       Re: Re: Self-teaching snag

• To: mathgroup at smc.vnet.net
• Subject: [mg74618] Re: [mg74583] Re: [mg74556] Self-teaching snag
• From: "Chris Chiasson" <chris at chiasson.name>
• Date: Wed, 28 Mar 2007 01:46:30 -0500 (EST)
• References: <200703260704.CAA11373@smc.vnet.net>

```Some of us ended up with 37 days and some with 38 days. This is bad.

On 3/27/07, Daniel Lichtblau <danl at wolfram.com> wrote:
> Todd Allen wrote:
> > Hi All,
> >
> >    I am trying to refresh my skills in basic problem
> > solving using Mathematica, but am running into some
> > difficulties which are beginning to make me suspicious
> > of Mathematica itself.  (I probably should be
> > suspicious of my own brain...but you know how that is
> > :-)
> >
> > Here is the scenario:  I have written a basic function
> > to tell me what percentage of battery power will
> > remain in a battery after x number of days, provided
> > that we start with a full charge and lose 5% of that
> > charge per day.
> >
> > If you execute the following code in Mathematica
> > (V5.1):
> >
> > charge=1.0 (* 100% *);
> > charge[day_]:=(charge[day-1]-(0.05*charge[day-1]));
> > charge
> >
> > I receive an output of 0.358486 for my query at the 20
> > day mark.....so, no problem so far.
> >
> > However, when I try to ask for the output at
> > charge, mathematica seems to enter an endless
> > calculation.  I've let the computer run for as long as
> > 5 minutes without getting an answer.  Is there
> > something wrong with my function, my version of
> > Mathematica or something else I haven't considered?
> >
> >
> >
> > When I try the following:
> >
> > In:=
> > Solve[charge[day]==0.15,day];
> >
> > Mathematica gives me the error:
> > "\$RecursionLimit::reclim: Recursion depth of 256
> > exceeded."
> >
> > I am trying to ask Mathematica to tell my how many
> > days it takes to reduce the battery power to 15
> > percent, but I must be messing something up??
> >
> > If anyone has any pointers, I'd certainly appreciate
> > it, because I am a little stuck right now.
> >
> > Best regards,
> > Todd Allen
>
> I expect you will receive several reasonable responses to this. I wanted
> to address what I think is a subtlety. I apologize in advance if this
> drawn out explanation bores anyone beyond the usual level of tears.
>
> First let me cover some of the basics. I will use exact arithmetic
> because in some steps it may make sense to avoid approximations. I
> define the recursive computation as below. I use a common caching
> technique many others will likely also mention, memoization (also called
> "memorization"), so as to avoid recomputations.
>
> In:= charge0 = 1;
>
> In:= charge0[day_] := charge0[day] = 19/20*charge0[day-1]
>
> Note the computation is virtually instantaneous.
>
> In:= InputForm[Timing[charge0]]
> Out//InputForm=
> {0., 570658162108627174778971075491512021856922699/
>    3435973836800000000000000000000000000000000000}
>
> I'll redo this but without memoization.
>
> In:= charge1 = 1;
>
> In:= charge1[day_] := 19/20*charge1[day-1]
>
> In:= InputForm[Timing[charge1]]
> Out//InputForm=
> {0., 570658162108627174778971075491512021856922699/
>    3435973836800000000000000000000000000000000000}
>
> Well, that too was quite fast. Now let's look at your definition
> (changed to use exact arithmetic, but not altered in any way that makes
> an essential difference). First I show a red herring.
>
> In:= InputForm[charge2[day-1] - 1/20*charge2[day-1]]
> Out//InputForm= (19*charge2[-1 + day])/20
>
> Now let's actually define the function.
>
> In:= charge2 = 1;
>
> In:= charge2[day_] := charge2[day-1] - 1/20*charge2[day-1]
>
> Is this different from charge1 above? Yes, considerably. First check the
> speed of evaluating charge2.
>
> In:= InputForm[Timing[charge2]]
> Out//InputForm=
> {0.21201399999999962, 15181127029874798299/32768000000000000000}
>
> So how is this different from charge1? And why was charge1 fast to
> compute, just like charge0? We look at how charge2 is actually stored.
> Since we use SetDelayed (the "colon-equal" assignment), it is not
> actually evalauted as in "red herring" above.
>
> In:= ??charge2
> Global`charge2
>
> charge2 = 1
>
> charge2[day_] := charge2[day - 1] - (1*charge2[day - 1])/20
>
> We see the terms are not combined. So a tremendous amount of
> reevaluation will take place. How to cure this? Again, we can use
> memoization.
>
> In:= charge3 = 1;
>
> In:= charge3[day_] := charge3[day] = charge3[day-1] -
> 1/20*charge3[day-1]
>
> In:= InputForm[Timing[charge3]]
> Out//InputForm=
> {3.2578106878844437*^-15, 570658162108627174778971075491512021856922699/
>    3435973836800000000000000000000000000000000000}
>
> Why was charge1, which did not use memoization, so fast? Because it was
> written in a way that is tail recursive, hence avoids massive
> recomputation. Since it is not always easy to write arbitrary recursions
> as tail recursive, I'd recommend the memoization approach as a general
> tactic (but then be aware of things like \$RecursionLimit).
>
> To address your second question one can use RSolve to get a closed form
> of the recurrence solution, then use Solve to find where we hit the 15%
> mark.
>
> In:= InputForm[chargefunc = ch[d] /.
>             RSolve[{ch[d]==19/20*ch[d-1],ch==1}, ch[d], d]]
> Out//InputForm= {(20/19)^(1 - d)}
>
> In:= InputForm[soln = d /. Solve[chargefunc[]==3/20, d]]
> Solve::ifun: Inverse functions are being used by Solve, so some
> solutions may
>       not be found; use Reduce for complete solution information.
> Out//InputForm= {(Log[20/19] + Log[20/3])/Log[20/19]}
>
> Turns out to be around 38 days.
>
> In:= N[soln[]]
> Out= 37.9857
>
> Adequate for most uses, I should think, short of say FOBP ("Floods of
> Biblical Proportions").
>
>
> Daniel Lichtblau
> Wolfram Research
>
>

--
http://chris.chiasson.name/

```

• Prev by Date: Re: Re: Self-teaching snag
• Next by Date: Re: Re: Self-teaching snag
• Previous by thread: Re: Self-teaching snag
• Next by thread: Re: Self-teaching snag