MathGroup Archive 2007

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

Search the Archive

Re: Self-teaching snag

  • To: mathgroup at smc.vnet.net
  • Subject: [mg74583] Re: [mg74556] Self-teaching snag
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Tue, 27 Mar 2007 04:00:53 -0500 (EST)
  • References: <200703260704.CAA11373@smc.vnet.net>

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[0]=1.0 (* 100% *);
> charge[day_]:=(charge[day-1]-(0.05*charge[day-1]));
> charge[20]
> 
> 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[35], 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?
> 
> 
> Additionally,
> 
> When I try the following:
> 
> In[145]:=
> 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[54]:= charge0[0] = 1;

In[55]:= charge0[day_] := charge0[day] = 19/20*charge0[day-1]

Note the computation is virtually instantaneous.

In[56]:= InputForm[Timing[charge0[35]]]
Out[56]//InputForm=
{0., 570658162108627174778971075491512021856922699/
   3435973836800000000000000000000000000000000000}

I'll redo this but without memoization.

In[58]:= charge1[0] = 1;

In[59]:= charge1[day_] := 19/20*charge1[day-1]

In[60]:= InputForm[Timing[charge1[35]]]
Out[60]//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[69]:= InputForm[charge2[day-1] - 1/20*charge2[day-1]]
Out[69]//InputForm= (19*charge2[-1 + day])/20

Now let's actually define the function.

In[70]:= charge2[0] = 1;

In[71]:= 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[15].

In[72]:= InputForm[Timing[charge2[15]]]
Out[72]//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[73]:= ??charge2
Global`charge2

charge2[0] = 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[74]:= charge3[0] = 1;

In[75]:= charge3[day_] := charge3[day] = charge3[day-1] - 
1/20*charge3[day-1]

In[76]:= InputForm[Timing[charge3[35]]]
Out[76]//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[77]:= InputForm[chargefunc = ch[d] /.
            RSolve[{ch[d]==19/20*ch[d-1],ch[1]==1}, ch[d], d]]
Out[77]//InputForm= {(20/19)^(1 - d)}

In[79]:= InputForm[soln = d /. Solve[chargefunc[[1]]==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[79]//InputForm= {(Log[20/19] + Log[20/3])/Log[20/19]}

Turns out to be around 38 days.

In[81]:= N[soln[[1]]]
Out[81]= 37.9857

Adequate for most uses, I should think, short of say FOBP ("Floods of 
Biblical Proportions").


Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: Self-teaching snag
  • Next by Date: Re: Definite Integration in Mathematica
  • Previous by thread: Re: Re: Self-teaching snag
  • Next by thread: Re: Re: Self-teaching snag