Posts: 653
Threads: 26
Joined: Aug 2010
I just had a look at the TVM solver that comes with the 34s library software. In most cases there is no closed form solution for the interest rate, so the iterative solver is used. However, the two required initial guesses are simply 100% and (at least) +1000%. While it is true that the result usually will be somewhere in this interval, I think we can do better.
Here's a first idea:
Let's assume the initial guess is i=0. In this case the TVM equation used in the 34s...
PV + FV i
( + PV) ·  + PMT := 0
(1+i)^{n}  1 k
...with k = 1 (BEG mode) or 1+i (END mode), will approach the limit
PV + FV
 + PMT
n
Also the first derivative at i=0 is not too hard to get, so that we can get a better estimate using Newton's method, leading to
FV + n·PMT + PV
i ~= 2 · 
n·(FVPV) ± (FV+PV)
This is just a first idea. I am sure there are much better ways to provide an estimate resp. an interval for the interest rate so that the solver will require just a few iterations. And that's exactly the reason for this post: What's your idea here?
BTW  the results of the 34s solver still seem to depend on the display setting. This does not match the manual's claim that the user interface is the same as on the 15C (here the results generally are as accurate as possible, regardless which display mode is currently set). Either the code or the manual should get adjusted.
Dieter
Edited to correct a formula
Edited: 27 Nov 2012, 9:17 a.m.
Posts: 4,587
Threads: 105
Joined: Jul 2005
Quote:
BTW  the results of the 34s solver still seem to depend on the display setting. This does not match the manual's claim that the user interface is the same as on the 15C (here the results generally are as accurate as possible, regardless which display mode is currently set). Either the code or the manual should get adjusted.
Dieter, provide an example, please. TIA.
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
This is just a first idea. I am sure there are much better ways to provide an estimate resp. an interval for the interest rate so that the solver will require just a few iterations. And that's exactly the reason for this post: What's your idea here?
Hi Dieter,
you want to use i1=0 as first and this i2~=... (from the Newton formulas) as second initial guess, right?
Well, IIRC the WP34s solver requires that the solution is within the 2 initial guesses, but that's not guaranteed with the Newton method, it depends on the signs of f, f' and f'' at i1 if your 2nd guess i2 (your last formula) is really at 'the other side' of the solution i (i.e. if i is within [i1,i2]).
So I doubt that these 2 initial guesses would work for all cases, you'll certainly just get an error message from the WP34s solver when the 2nd guess i2 has the same sign as i1=0.
Of course this could be avoided by using the Newton iteration in the TVMsolver, but why write an additional routine (and use extra bytes) when the integrated WP34s solver works already fine for those TVM calculations.
Franz
Posts: 653
Threads: 26
Joined: Aug 2010
Quote:
you want to use i1=0 as first and this i2~=... (from the Newton formulas) as second initial guess, right?
No. I want two better guesses (if the solver is used), or one single reasonable guess, used with a dedicated solver routine. The mentioned formula is such a first estimate that is reasonably close to the true interest rate so that it can be used for a solver routine that is based on one single initial guess (and not an interval).
With a closer look at the formula some other properties of the estimate may be discovered. For instance we can tell at least the correct sign of i. There also should be a way to tell whether the estimate is higher or lower than the actual root we're looking for.
If the 34s solver absolutely requires two guesses with opposite signs of the function result, and this is what we are looking for, we have to go one or two steps further. That's why I opened this thread. I assume there are better ideas for better guesses. ;)
Here's a simplified example. I covers the case that either PV or FV is zero, i. e. the standard annuity equation
1  (1+i)^{n}
PV = PMT * 
i
For this case there and i > 0 I use the following two guesses for i:
PMT 1
i1 =   
PV n
2 n
i2 = i1 * 
n+1
Here, i1 is exact for i => 0 and i => infinity, and values inbetween are a bit low. On the other hand, the exact solution is less than 2*i1. For n < 1 it's the other way round. And for n => infinity, i1 also approaches the true value of i.
Example:
n = 10 years
PV = 60000 EUR
PMT = 10000 EUR/yr
=> i1 = 1/6  1/10 = 1/15 = 0,066666...
=> i2 = 1/15 * 20/11 = 4/33 = 0,121212...
True i = 0,10558
I bet this can also be done for the general case with PV and FV. ;)
Dieter
Edited: 4 Dec 2012, 12:27 p.m. after one or more responses were posted
Posts: 653
Threads: 26
Joined: Aug 2010
Here's a very basic example:
001 LBL 33
002 x²
003 2
004 
005 RTN
FIX 2
1 ENTER 2 SLV 33 => 1,41(4168538134572)
FIX 4
1 ENTER 2 SLV 33 => 1,4142(13562340577)
ALL 3
1 ENTER 2 SLV 33 => 1,414213562373095
The accuracy of the result depends on the display setting.
Dieter
Posts: 3,229
Threads: 42
Joined: Jul 2006
The 34S solver doesn't require the solution to lie between the two initial guesses. It works a lot better if this is the case but it does try to expand the guess interval if the function evaluations at the ends have the same sign.
 Pauli
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
The 34S solver doesn't require the solution to lie between the two initial guesses. It works a lot better if this is the case but it does try to expand the guess interval if the function evaluations at the ends have the same sign.
Strange, then my memory betrays me. I was sure to remember that we had a similar discussion long time ago, and you've answered something like "where should the solver search then?" when there's no solution between the 2 initial guesses.
But maybe you've changed this solver behaviour any time?
Franz
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
I bet this can also be done for the general case with PV and FV. ;)
Maybe, but would you like to do these investigations for ALL cases for which the TVM equation is valid and the TVM program is working?
And there are MANY different cases, not only the single special case which you'f constructed: already PV, PMT and FV could have many different signs, and then also the interest rate 'I' can be negative (as the number of periods 'N', too).
Do you really think it would be worth the big effort to find proper initial guesses for all those different cases, and then also need different subroutines in the program for each case? I'm sure this would be even more code than the complete current TVM program, just for finding a bit 'better' initial values, although the current fixed values are working fine.
Franz
Posts: 653
Threads: 26
Joined: Aug 2010
Franz, you are talking about problems, not about solutions. :) Come on, remember John F. Kennedy: "We choose to go to the Moon in this decade and do the other things, not because they are easy, but because they are hard." And you're afraid of a simple formula.
All I want is something better than "somewhere between 100% and +1000%". I am sure we can do better. How much better depends on the effort. What about a first step: don't you think we can nail it down at least to "i>0" or "i<0" ?)
Dieter
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
Franz, you are talking about problems, not about solutions. :) Come on, remember John F. Kennedy: "We choose to go to the Moon in this decade and do the other things, not because they are easy, but because they are hard." And you're afraid of a simple formula.
Well, I'm talking about problems because I _see_ the problems in this task. And I'm sure we won't find any 'simple formula' for all possible cases.
Quote:
All I want is something better than "somewhere between 100% and +1000%". I am sure we can do better. How much better depends on the effort. What about a first step: don't you think we can nail it down at least to "i>0" or "i<0" ?)
The reason why I'm not really interested in your proposal is that I absolutely don't know _why_ we should try finding 'better' start values. The 2 values I've used will certainly work in all cases that I could imagine, and so far I've not seen any remarkable running times when solving for 'I' (ok, I can only speak about the emulator, I don't have the real calculator).
And if you've found better values, then why not search for _still_ better values? (and so on, where should we stop?)
And it's not only about the big effort to consider all possible cases (which would certainly lead to more than only one pair of initial values), it's also the additional code needed in the TVM program  and you know that RAM is quite limited in the WP34s.
In short words: I don't see any advantage which would justify this additional work. ;)
Franz
Edited: 28 Nov 2012, 6:20 p.m.
Posts: 653
Threads: 26
Joined: Aug 2010
Quote:
In short words: I don't see any advantage which would justify this additional work.
How sad. :)
There are two main reasons why I think the TVM solver should get an update in its interest routine. First, it's execution speed. The emulator does not matter  here virtually anything is computed instantly. The real device is slower. Much slower.
Then there are cases where the returned result should be improved. Initial guesses of 100% and +1000% do not make sure there will be a solution. The TVM equation is not always monotic, so these two guesses may not even produce results with opposite signs. Consider these two examples:
n = 10 10
PV = 50 50
PMT = 30 30
FV = 100 400
In both cases the current TVM solver returns
I = not nuMEric
Actually there are two interest rates that solve the TVM equation.
I1 = 28,44% 14,44%
I2 = 58,20% 53,17%
A Newtonsolver starting at i=0 (or the guess I suggested) would at least return one of these results.
In other words: improving the TVM solver returns results where the current implementation fails. Wouldn't this deserve some effort?
Dieter
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
The 34S solver doesn't require the solution to lie between the two initial guesses. It works a lot better if this is the case but it does try to expand the guess interval if the function evaluations at the ends have the same sign.
Pauli, a few questions about how this 'expansion' is done:
1) does it expand in both directions?
2) how much does it expand?
3) how often is this expansion tried before the solver gives up (if no solution found)?
I'm asking because I intend to make changes to the initial guesses of my TVM solver, because with this 'expansion' (I'm sure this hasn't been done in older versions!?) it seems that the solver comes to interest rate values which are not defined (less than 100%) and hence the error message for Dieters examples.
Franz
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
In other words: improving the TVM solver returns results where the current implementation fails. Wouldn't this deserve some effort?
Yes Dieter, your examples have convinced me to do something! ;)
Unfortuately I'm not yet sure what to do (or how to do it). But I definitely won't use the Newton method and include a separate solving routine in TVM, just look at the 1st derivative of the TVM expression and you could guess how many steps this Newton method would require  and then we still can't be sure that it will find a solution.
Now after Pauli said that the WP34s solver automatically extends the initial interval when no solution is found (I'm quite sure this has not always been so), I think I'll try it with the following method:
You can enter a start value i0 for the interest rate (to the variable 'I' just like for all other TVM variables), and the initial guesses used are i05 and i0+5 (i.e. we have a 10% interval around this initial value).
Well, that's just a first trial as long as I don't have any better ideas ...
Franz
Edited: 1 Dec 2012, 5:41 a.m.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Quote: 1) does it expand in both directions?
2) how much does it expand?
3) how often is this expansion tried before the solver gives up (if no solution found)?
1) Yes.
2) I don't remember  by a scale factor I think.
3) Variable depending if the function appears constant or just one signed.
The source is in trunk/xrom/solve.wp34s from memory.
 Pauli
Posts: 3,229
Threads: 42
Joined: Jul 2006
Quote: I'm quite sure this has not always been so
It has always been so :)
 Pauli
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
The source is in trunk/xrom/solve.wp34s from memory.
I was already afraid that you would point me to the sources. ;)
You know how hard it is to analyze (and understand!) the code of someone else, especially the WP34s solver is quite complicated.
But ok, I'll try it ...
Franz
Edited: 1 Dec 2012, 5:47 a.m.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Unfortunately, it is too long since I wrote the code for me to remember details like this. I know it expands the search in a fairly naïve manner when the first three function evaluations are all constant. It is a bit smarter when they are unequal bu same signed.
It can be hard to understand the code despite having written it  keystroke programs are write only much of the time.
At least there are some comments present....
 Pauli
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
It has always been so :)
But then I don't understand your answer "where should the solver search then, if there's no solution between the 2 initial guesses?" in a discussion we already had about the solver long time ago.
And I'm sure you've said something like this, I'm not hallucinating. ;)
Franz
Posts: 3,229
Threads: 42
Joined: Jul 2006
You aren't hallucinating, I seem to recollect that that was in response to a complaint that the solver was less than perfect. All solvers are provable imperfect and must make mistakes.
The 34S solver is rather dumb when the initial guesses don't bracket the solution but it still makes a token effort. I'm still will to accept suggestions and improvements to this part of the algorithm.
 Pauli
Posts: 653
Threads: 26
Joined: Aug 2010
Quote:
Unfortuately I'm not yet sure what to do (or how to do it).
It's not trivial, but maybe easier than you think. To make things clear, let's first assume END mode, i >=1 and n >= 1, and take a closer look at the TVM equation.
PV + FV
t(n, i, PV, PMT, FV) = ( + PV) * i + PMT
(1+i)^{n}1
This equation has some relevant properties:
 At i=1 the value of t is FV + PMT
 At i=1 the slope of t is FV
 As i approaches infinity, the slope of t approaches PV
 The value of PMT only shifts the graph of t up or down
This means that we predict how the graph of t will look like:
 If FV and PV have opposite signs, t is a monotonic function. The graph will cross the iaxis (i.e. there is a solution) if sign(FV+PMT) * sign(PV) = 1.
In this case t is convex if abs(FV) < abs(PV), resp. concave if it's the other way round. This means we can easily tell whether a Newton estimate is slightly high or low.
 If FV and PV have the same sign, the function graph will have a local minimum or maximum. In this case there are either two values for i where t becomes zero (maybe one double root), or there is no solution at all.
This is the case in my two last examples: FV and PV have the same sign and so t has two roots.
 If FV or PV = 0 the graph starts or ends in a horizontal line with t = PMT. It may or may not cross the iaxis, depending on the value of PMT.
I still think a Newtonstyle solver is the best idea here.
Dieter
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
It's not trivial, but maybe easier than you think.
And OTOH maybe harder than you think.
I've tried your 2 examples above with ALL financial HP calculators/emulators (HP12c/10bII+/17bII+/30b and also the TVMsolver of the HP50g), and NONE of them returned any solution. So my TVM program for the WP34s is at least in good company. ;)
The main problem of the WP34s TVMprogram is that the implemented solver expands the initial interval for 'i' if the 2 guesses have the same sign, and with this expansion 'i' gets values that are just too small (maybe even <1) and so the program stops with an error message. Unfortunately I can't restrict the internal solver in any way, i.e. I can't tell him to not use too small negative 'i'values.
What I've tried so far is that you can manually enter a startvalue I0 when TVM returns an error: you enter this value for 'I' and then start the solving process for 'I' again. In this case (i.e. if I=I0<>0) the solver is called again with the interval [I05,I0+5]. When also this interval doesn't return a solution, I0 is automatically set to I0+10, so you simply have to repeat solving for 'I' (just 2 keypresses [A][B] in my 2nd TVM version). You can repeat this until you reach an interval with a solution in it.
This method is quite comfortable, and such problems occur only under very special and unrealistic conditions (as your examples).
I'm still thinking about to automate this process, i.e. maybe the program should automatically scan the interval [0%,100%] for 'I' in 10%steps (and eventually also for negative 'I') until it finds an interval with changing signs, so that the WP34s solver would definitely find the solution.
Your description above is really impressing, but there are 2 problems that I see:
First VERY much code would be necessary to make all those tests to differentiate between all those different cases, and then I still don't see any concrete value where a Newton method should start (for all those different cases) and would guarantee that a solution will be found. Just think of all those cases where the tangent is nearly horizontal, this would put the next iteration point VERY far away (probably giving any error messages again because of over/underflows etc.).
I (and maybe you, too) understand now why all TVM solvers of financial calculators fail under such special conditions.
Franz
Edited: 2 Dec 2012, 5:58 p.m.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Would it be possible to return a fake large value instead of failing when the solver goes out of range?
Save the machine state, set flag D and check using NaN?, [infinite]? or SPEC?
 Pauli
Posts: 1,216
Threads: 75
Joined: Jun 2011
Quote:
Would it be possible to return a fake large value instead of failing when the solver goes out of range?
Maybe, but it's not so easy because the error can happen on different places. At most it is at ln(1+x), but when I change the TVM equation a bit (or with other PV/PMT/FV values) it's just a division by zero.
It's a pity that we don't have something like 'ON ERROR' or 'Try...Else...EndTry' as in some other languages, but I guess that would be too highlevel for a calculator language. ;)
Quote:
Save the machine state, set flag D and check using NaN?, [infinite]? or SPEC?
Ooops, that's something I've not yet tried (or needed)  must check the manual before I could say if this may be of any use!?
Franz
Edited: 2 Dec 2012, 6:57 p.m.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Checking for Nan/infinity is as close to the ON ERROR as we get.
 Pauli
Posts: 653
Threads: 26
Joined: Aug 2010
Quote:
I've tried your 2 examples above with ALL financial HP calculators/emulators (HP12c/10bII+/17bII+/30b and also the TVMsolver of the HP50g), and NONE of them returned any solution. So my TVM program for the WP34s is at least in good company. ;)
If it returns wrong results, it's definitely no reference for the 34s project. There are two valid interest rates for either case, and if machine X or Y claims there is no solution, it simply returns a wrong result.
I did a first draft of a program that should handle most cases correctly, at least for n>1 and END mode. All in all, the new interest routine has more than 100 lines of 34s code. It essentially works like this:
 Test if FV * PV < 0. In this case there is a solution. Use 100 and +1000% or two better estimates for the solver.
 If PV = 0, test if (PMT+FV) * PMT > 0. In this case there is no solution. Otherwise PMT/FV is a lower bound for the interest rate.
 If FV = 0, test if PV * PMT > 0. In this case there is no solution. Otherwise PMT/PV is an upper bound for the interest rate.
 Finally, if FV * PV > 0 there are two solutions (maybe one double root) or none. At this point we only can say that if PMT has the same sign as FV or PV, there definitely is no solution.
Now we have to look closer at the first derivative of the TVM equation. The solver can be used to find its root, i.e. the point where the function has its minimum or maximum i_m. If the TVM function at this point has the same sign as FV+PMT, there is no solution. Otherwise the solver is called again to find the first root between 100% and i_m, and finally the second root between i_m and, say, +1000%.
So yes, it can be done. My current quick and dirty implementation returns the correct solution (or two of them, if they exist), and it also throws an error message if there is no interest rate that solves the TVM equation.
Yes, it's not trivial. No, it's not that hard.
Dieter
Edited: 4 Dec 2012, 12:32 p.m.
