Brent RootFinder

by otorineko6790

JavaScript

/*
var test_counter;
var pv;
function f1 (x) { test_counter++; return (Math.pow(x,2)-1)*x - 5; }
function f2 (x) { test_counter++; return Math.cos(x)-x; }
function f3 (x) { test_counter++; return Math.sin(x)-x; }
function f4 (x) { test_counter++; return (x + 3) * Math.pow(x - 1, 2); }
[
  [f1, 2, 3],
  [f2, 2, 3],
  [f2, -1, 3],
  [f3, -1, 3], 
  [f4, -4, 4/3]
].forEach(function (args) {
  test_counter = 0;
  var root = uniroot.apply( pv, args );			//args ==> [f1, 2, 3]
  console.log( 'uniroot:', args.slice(1), root, test_counter );
})//*/
//f(x)=x^3-3x^2-x+9=0
console.log(uniroot (func, 0, -2));
function func(x){return ((x-3)*x-1)*x+9;}
function uniroot ( func, lowerLimit, upperLimit, errorTol, maxIter ) {
  var a = lowerLimit, 
  		b = upperLimit,
      c = a,
      fa = func(a),
      fb = func(b),
      fc = fa,
      s = 0,
      fs = 0,
      tol_act,   // Actual tolerance
      new_step,  // Step at this iteration
      prev_step, // Distance from the last but one to the last approximation
      p,         // Interpolation step is calculated in the form p/q; division is delayed until the last moment
      q;

  errorTol = errorTol || 0;
  maxIter  = maxIter  || 1000;

  while ( maxIter-- > 0 ) {
  
    prev_step = b - a;
   
    if ( Math.abs(fc) < Math.abs(fb) ) {
      // Swap data for b to be the best approximation
      a = b, b = c, c = a;
      fa = fb, fb = fc, fc = fa;
    }

    tol_act = 1e-15 * Math.abs(b) + errorTol / 2;
    new_step = ( c - b ) / 2;

    if ( Math.abs(new_step) <= tol_act || fb === 0 ) {
      return b; // Acceptable approx. is found
    }

    // Decide if the interpolation can be tried
    if ( Math.abs(prev_step) >= tol_act && Math.abs(fa) > Math.abs(fb) ) {
      // If prev_step was large enough and was in true direction, Interpolatiom may be tried
      var t1, cb, t2;
      cb = c - b;
      if ( a === c ) { // If we have only two distinct points linear interpolation can only be applied
        t1 = fb / fa;
        p =...