CODEWITHSUNDEEP
javascriptalgorithmmath
Bjørn Fridal
Bjørn Fridal

Reputation: 131

Optimizing my guessing algorithm

I need to find a number (my guess) that when used in a simple calculation will produce a specific sum (target). To that end I have written a calcGuess function. It works, but I would like to reduce the number of iterations needed to calculate my guess.

My approach involves adding or subtracting a modifier to the guess for reach iteration.

Any suggestions to increase the efficiency of the guessing algorithm will be greatly appreciated.

var _target = 40000;
var _cashflow = [1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1398];
var _guess = 0.0014534646484;
var _modifier = 0.01;


var correctGuess = calcGuess(_target, _cashflow, _guess, _modifier, false, false, false, 0);


function calcGuess(target, cashflow, guess, modifier, hasPrevGuess, prevGuessToHigh, prevGuessToLow, iterations) {
  // prevent an infinite loop
  if (++iterations > 100) {
    console.log('Kill switch');
    return;
  }
  
  // calculate a new target using the cashflow array and our guess
  var targetUsingGuess = 0;
  for (var n = 0; n < cashflow.length; n++) {
    targetUsingGuess += cashflow[n] / Math.pow(1 + guess, n);
  }
  
  // compare our new target to the original target 
  if (targetUsingGuess.toFixed(8) == target.toFixed(8)) {
    
    // the guess matched!
    console.log(iterations, ' Matched!: ', guess);
    return guess;
  }
  else {
    
    // the guess was too high
    if (targetUsingGuess > target) {
      
      // this where I modify my guess and
      // this is part which I think can be much efficient
      if (hasPrevGuess && prevGuessToLow) {
        modifier /= 2;
      }
      guess += modifier;
      
      console.log(iterations, ' Too high: ', guess);
      return calcGuess(target, cashflow, guess, modifier, true, true, false, iterations);
    }
    
    // the guess was too low
    if (targetUsingGuess < target) {

      // this where I modify my guess and
      // this is part which I think can be much efficient
      if (hasPrevGuess && prevGuessToHigh) {
        modifier /= 2;
      }
      guess -= modifier;
      
      console.log(iterations, ' Too low: ', guess);
      return calcGuess(target, cashflow, guess, modifier, true, false, true, iterations);
    }
  }
}

Upvotes: 0

Views: 111

Answers (1)

EvilTak
EvilTak

Reputation: 7579

Since we have the result and want to find the input to a function for which you obtain the result, the Newton-Raphson method of finding roots will be the best option.

Your required target T has to be calculated from the function t(x) = sum of C[i] / (1 + x)^i, where 0 <= i < n. C represents your cashflow array, n represents cashflow.length and x is your guess. The function can be rewritten as follows: t(x) = sum of C[i] * (1 + x)^(-i). If all C[i] are equal, the function can be reduced to a rational function using the sum of a geometric series, but since you have a cashflow array, I am going to assume that they all are different and leave t(x) as is.

Your problem now reduces to finding g (the guess) for which t(g) = T.

NOTE: For the given function, the obvious vertical asymptote is x = -1. Due to the nature of the sum, for any T > C[0] (the first element in the cashflow array), g > -1. I will use this assumption that the desired target will always be greater than the first element of the cashflow array throughout. The given method will work for T < C[0] too with a slight change in the initial guess, but will eventually cause a division by zero if T is less than or equal to the minimum of the function for odd n. f(x) is guaranteed to be monotonic for x > -1, but monotonicity in x < -1 is guaranteed only for even n.

The working algorithm for the Newton-Raphson method of finding roots is as follows:

If x(i) is the ith guess, 

x(i+1) = x(i) - f(x(i)) / f'(x(i))

Where f'(x) is the derivative of f(x).

In our case, f(x) = t(x) - T since we have to find the value of x for which t(x) = T => t(x) - T = 0 => f(x) = 0.

From our definition of f(x), f'(x) = t'(x) = sum of C[i] * (-i) * (1 + x)^(-i - 1).

The only thing remains is to find a good initial guess. The nature of the function combined with our assumption allows us to give a very easy answer to this question. Since the function is decreasing for x > -1, we simply take the smallest number greater than -1. From your code, it looks like your error tolerance (TOL) is 1e-8 (the first 8 decimal digits must be the same). Therefore, the initial guess is -1 + TOL.

You might argue that since the function is monotonic for x > -1, we can choose any x > -1 as the initial guess, but due to the discontinuous nature of the function, guesses greater than a specific value depending on the function definition will cause the next guess to be less than -1, and subsequent guesses will diverge to infinity instead of converging.

EDIT: After some testing, 1 - target / sum(cashflow) makes a much much better initial guess, converging in 10-20 iterations vs. -1 + TOL's convergence in ~500 iterations.

The algorithm must be terminated when the absolute difference between two guesses is less than TOL, but here we terminate if the absolute difference between the target and the guessed result (simply abs(f(guess))) is less than TOL since the rate of convergence for some cases may be very slow.

var _target = 40000;
var _cashflow = [1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1934, 1398];
var _tolerance = 1e-8;

var correctGuess = calcGuess(_target, _cashflow, _tolerance);

console.log("Final guess:", correctGuess);

function calcGuess(target, cashflow, tolerance) {
	var f = function(x) {
    	var sum = 0.0;
    	for (var i = 0; i < cashflow.length; i++) {
    		sum += cashflow[i] * Math.pow(1 + guess, -i);
  		}
        return sum - target;
    }
    
    // Derivative of f
    var df = function(x) {
    	  var sum = 0.0;
    	  for (var i = 0; i < cashflow.length; i++) {
    		  sum += cashflow[i] * (-i) * Math.pow(1 + guess, -i - 1);
  		  }
        return sum;
    }
    
    // Initial guess
    var guess = 1 - target / cashflow.reduce(function(a, b) { return a + b; }, 0);
    
    // Newton-Raphson
    for (var iter = 0; iter < 1000; iter++) {
    	  guess -= f(guess) / df(guess);
        if(Math.abs(f(guess)) < tolerance) {
        	// Found guess, return
            break;
        }
        console.log(iter, ":", guess);
    }
    
    console.log("Difference:", f(guess));
    return guess;
}

Upvotes: 2

Related Questions