|
|
|
|
|
|
|
|
|
|
|
|
Search Algorithms
|
|
|
|
Suppose you have the following equation and are asked to solve it for X. You could solve it analytically by using algebra and probably is the best way for this equation. But if the equation was significantly more complicated it might not be.
|
|
|
|
But suppose you have the following equation to solve. Now it becomes more difficult to do it analytically
|
|
|
|
This X would be called the internal rate of return in finance. HIRR returns such a value assuming the half year convention. The built in IRR function returns X without assuming the half year convention.
|
|
|
|
In order to solve these types or equations a numerical technique is frequently used. It involves guessing at the answer and then seeing how wrong the answer is and guessing again until you find the right answer. There are a variety of techniques that you can use to improve the guess so that they are not just random.
|
|
|
|
One technique is called the binary search. All techniques start with a value, the solution is sometimes dependent on the starting value, but in many cases it is not. To solve Equation 1 let try a first guess that X is 1. Unless we are lucky we need to compute the error and then correct our guess and try again.
|
|
|
|
Strategy Double the last guess until we go over
|
|
|
|
Guess:
|
|
|
Guess:
|
|
|
Guess:
|
|
|
Guess:
|
|
|
|
|
X = 1
|
|
|
X = 2
|
|
|
X = 4
|
|
|
X = 8
|
|
|
|
|
|
Equation
|
|
|
=10 + 12*(1)
|
|
|
=10 + 12*(2)
|
|
|
=10 + 12*(4)
|
|
|
=10 + 12*(8)
|
|
|
|
|
=
|
|
|
|
|
Computed
|
|
|
22
|
|
|
34
|
|
|
58
|
|
|
106
|
|
|
|
|
Needed Answer
|
|
|
79
|
|
|
79
|
|
|
79
|
|
|
79
|
|
|
|
|
'We now know that answer for X lies between and 4 and 8. The average is:
|
|
|
|
Strategy guess middle until we get an acceptable solution
|
|
|
|
|
Equation
|
|
|
=10 + 12*(6)
|
|
|
|
|
=
|
|
|
|
|
Computed
|
|
|
82
|
|
|
|
|
Needed Answer
|
|
|
79
|
|
|
|
|
'We now know that answer for X lies between and 4 and 6. The average is:
|
|
|
|
'We now know that answer for X lies between and 5 and 6. The average is:
|
|
|
|
'We now know that answer for X lies between and 5.5 and 6. The average is:
|
|
|
|
|
Error = Needed - Computed
|
|
|
57
|
|
|
45
|
|
|
21
|
|
|
-27
|
|
|
6
|
|
|
Error = Needed - Computed
|
|
|
-3
|
|
|
5
|
|
|
9
|
|
|
5.5
|
|
|
3
|
|
|
5.75
|
|
|
0
|
|
|
|
|
In fact once you have the answer bracketed you can hone in very fast. Suppose you know the number you are guessing is whole and is between 1 and 128. After each guess you will be told whether you are high or low. How many guess will it take? ( Answer is only 7, or less--you might get lucky.) Why? Because 27 is 128. Your first guess should be 64. Then if you are high, guess 32 or low guess 96. Etc.
|
|
|
|
|
|
|
|
|
Spreadsheets have these routines installed. There are two versions in Excel one is called Goal Seek and the other is called Solver. Solver is much more powerful. But even with its power it won't always find an answer. Or it may not find an answer if you don't give a good place to start looking.
|
|
|
Sometimes the guess does not go quite so well. Particularly if you have a complex equation. Or the equation is peculiar. Try to find the answer to the following equation: (a value of X that makes the equation true.)
|
|
|
0 = 10X2 + 5X + 50
|
|
|
|
Good Luck
|
|
|
|
Therefore the BSVOPM and HIRR function might not always find an answer. Since it is a numerical routine and will have problems sometimes in getting an answer.
|
|
|
|