   Critique my recursive stochastic hill-climbing algorithm
  I have a recursive stochastic hill-climbing algorithm for solving equations.The things I would like to work on are performance, efficiency and my own understanding of the algorithm, as I worked it out through a combination of intuition, mathematical instinct and late-night braining.*Snip*Latest two code sections at the bottom.[Edited by - Narf the Mouse on April 12, 2010 10:02:56 PM]
  Just from a quick scan, there's some variables named such that their purpose is unclear, like (Func<Double[], Double, Double> f... f? Really? Give things names that make it clear what they are doing without scanning all the code to infer it from usage.EquationSolveWithin takes a lot of arguments and has a shedload of data, can it be broken up into smaller methods with their own concern. Don't speculate on the performance implications of this just yet; this looks like c#, the JIT may observe the heat (high call frequency) of one of your smaller methods and optimise it further than it can with such a large method. Either way, strive for clarity over speculative performance gains.Ditch the commented out code, it's a distraction. Don't leave in "debug hook" code, use conditional breakpoints.Break conditions like the following out into sensibly named methods i.e instead of    } while (Math.Round(output, 11) != Math.Round(target, 11) && high != low && tempHigh != current && tempLow != current && (foundCloser || iterationsWithoutBetter < 50));prefer  } while (SomeSensibleName());, same with;  if ((closest.HasValue && high < closest && oldHigh > target) ||(closest.HasValue && high > closest && oldHigh < target))and   if ((closest.HasValue && low > closest && oldHigh > target) ||(closest.HasValue && low < closest && oldHigh < target))  These are stylistic but the will help reason about the algorithm. This is what I'd do before any actual tweaking, your mileage may vary.   ;  Ok, I've put all the complicated checks into their own functions; in doing so, I found one legacy check that was unnecessary, as it was doing the same thing wether it returned true or false, so that's been optimized out.And thanks.   public static List<Double> EquationSolver(Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target = 0, Filter filter = null)   {  List<Double> list = new List<double>();  EquationSolveWithin(equationToSolve, inputs, target, 0, Double.MaxValue, ref list, filter);  EquationSolveWithin(equationToSolve, inputs, target, 0, (-Double.MaxValue), ref list, filter);  return list;   }   public static void EquationSolveWithin(  Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target,  Double low, Double high, ref List<Double> list, Filter filter  )   {  Double current = ((high - low) / 2.0) + low;  Double output = 0;  Double? firstOutput = null;  bool reverse = false;  Double distance = high * high * high;  Double lastDistance = high * high * high;  Double oldLow = low;  Double oldHigh = high;  Double tempLow = low;  Double tempHigh = high;  Double? closest = null;  Double closestDistance = 0;  int iterationsWithoutBetter = 0;  bool foundCloser = false;  do  { current = ((high - low) / 2.0) + low; /* if (!firstOutput.HasValue)current = ((high - low) / 2.0) + low; elsecurrent = ((high - low) * GeneralData.Random.NextDouble()) + low; */ tempLow = low; tempHigh = high; lastDistance = distance; output = equationToSolve(inputs, current); if (!firstOutput.HasValue) {firstOutput = output;distance = output - target;lastDistance = output - target;closestDistance = output - target;closest = current;foundCloser = true;iterationsWithoutBetter = 0; } distance = output - target; /* if (high <= 20000) {int j = 0;++j; } */ if (ShouldReverse(distance, lastDistance))reverse = !reverse; if (!reverse) {high = current;// high = ((high - current) / 2.0) + current; } else {low = current;// low = ((current - low) / 2) + low; } foundCloser = false; ++iterationsWithoutBetter; if (Math.Abs(distance) <= Math.Abs(closestDistance)) {closestDistance = output - target;closest = current;foundCloser = true;iterationsWithoutBetter = 0; } if (GoneToFarA(target, high, oldHigh, closest)) {if (!reverse)    high = closest.Value * 2;else    low = closest.Value / 2; } if (GoneToFarB(target, low, oldHigh, closest)) {if (!reverse)    low = closest.Value / 2;else    high = closest.Value * 2; }  } while ( NotDone(target, low, high, current, output, tempLow, tempHigh, iterationsWithoutBetter, foundCloser)  );  Boolean passedFilter = PassedFilter(filter, current);  if (NewAndValid(target, list, current, output, passedFilter))  { list.Add(Math.Round(current, 11)); EquationSolveWithin(equationToSolve, inputs, target, oldLow, current, ref list, filter); EquationSolveWithin(equationToSolve, inputs, target, current, oldHigh, ref list, filter);  }  // -19x^5 + 18x^4 + 125x^3 + -56x^2 + -150x + 29 =  // x1 = 2.6220971863491  // x2 = 1.3224569490446  // x3 = 0.1859002930856  // x4 = -1.9980761764108  // x5 = -1.1850098310158   }   private static bool ShouldReverse(Double distance, Double lastDistance)   {  return (distance > 0 && lastDistance < 0) || (distance < 0 && lastDistance > 0) || (Math.Abs(distance) > Math.Abs(lastDistance));   }   private static bool GoneToFarA(Double target, Double high, Double oldHigh, Double? closest)   {  return (closest.HasValue && high < closest.Value && oldHigh > target) || (closest.HasValue && high > closest.Value && oldHigh < target);   }   private static bool GoneToFarB(Double target, Double low, Double oldHigh, Double? closest)   {  return (closest.HasValue && low > closest.Value && oldHigh > target)  || (closest.HasValue && low < closest.Value && oldHigh < target);   }   private static bool NotDone(Double target, Double low, Double high, Double current, Double output, Double tempLow, Double tempHigh, int iterationsWithoutBetter, bool foundCloser)   {  return Math.Round(output, 11) != Math.Round(target, 11) && high != low && tempHigh != current && tempLow != current && (foundCloser || iterationsWithoutBetter < 15);   }   private static Boolean PassedFilter(Filter filter, Double current)   {  Boolean passedFilter = false;  if (filter != null)  { double? first = filter.value; double? second = filter.Process(current); passedFilter = (first != second);  }  else passedFilter = true;  return passedFilter;   } private static bool NewAndValid(Double target, List<Double> list, Double current, Double output, Boolean passedFilter)   {  return passedFilter && !list.Contains(Math.Round(current, 11)) && Math.Round(output, 11) == Math.Round(target, 11);   };  It wasn't correctly filtering; I've fixed that. Also, I've added an optional "searchRange" potential optimization.   public static List<Double> EquationSolver(  Func<Double[], Double, Double> equationToSolve,   Double[] inputs,   double target = 0,   Filter filter = null,  double searchRange = Double.MaxValue)   {  List<Double> list = new List<double>();  EquationSolveWithin(equationToSolve, inputs, target, 0, searchRange, ref list, filter);  EquationSolveWithin(equationToSolve, inputs, target, 0, (-searchRange), ref list, filter);  return list;   }   public static void EquationSolveWithin(  Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target,  Double low, Double high, ref List<Double> list, Filter filter  )   {  Double current = ((high - low) / 2.0) + low;  Double output = 0;  Double? firstOutput = null;  bool reverse = false;  Double distance = high * high * high;  Double lastDistance = high * high * high;  Double oldLow = low;  Double oldHigh = high;  Double tempLow = low;  Double tempHigh = high;  Double? closest = null;  Double closestDistance = 0;  int iterationsWithoutBetter = 0;  bool foundCloser = false;  do  { current = ((high - low) / 2.0) + low; /* if (!firstOutput.HasValue)current = ((high - low) / 2.0) + low; elsecurrent = ((high - low) * GeneralData.Random.NextDouble()) + low; */ tempLow = low; tempHigh = high; lastDistance = distance; output = equationToSolve(inputs, current); if (!firstOutput.HasValue) {firstOutput = output;distance = output - target;lastDistance = output - target;closestDistance = output - target;closest = current;foundCloser = true;iterationsWithoutBetter = 0; } distance = output - target; /* if (high <= 20000) {int j = 0;++j; } */ if (ShouldReverse(distance, lastDistance))reverse = !reverse; if (!reverse) {high = current;// high = ((high - current) / 2.0) + current; } else {low = current;// low = ((current - low) / 2) + low; } foundCloser = false; ++iterationsWithoutBetter; if (Math.Abs(distance) <= Math.Abs(closestDistance)) {closestDistance = output - target;closest = current;foundCloser = true;iterationsWithoutBetter = 0; } if (GoneToFarA(target, high, oldHigh, closest)) {if (!reverse)    high = closest.Value * 2;else    low = closest.Value / 2; } if (GoneToFarB(target, low, oldHigh, closest)) {if (!reverse)    low = closest.Value / 2;else    high = closest.Value * 2; }  } while ( NotDone(target, low, high, current, output, tempLow, tempHigh, iterationsWithoutBetter, foundCloser)  );  if (NewAndValid(target, list, current, output))  { if (PassedFilter(filter, current)) {list.Add(Math.Round(current, 11));EquationSolveWithin(equationToSolve, inputs, target, oldLow, current, ref list, filter);EquationSolveWithin(equationToSolve, inputs, target, current, oldHigh, ref list, filter); }  }  // -19x^5 + 18x^4 + 125x^3 + -56x^2 + -150x + 29 =  // x1 = 2.6220971863491  // x2 = 1.3224569490446  // x3 = 0.1859002930856  // x4 = -1.9980761764108  // x5 = -1.1850098310158   }   private static bool ShouldReverse(Double distance, Double lastDistance)   {  return (distance > 0 && lastDistance < 0) || (distance < 0 && lastDistance > 0) || (Math.Abs(distance) > Math.Abs(lastDistance));   }   private static bool GoneToFarA(Double target, Double high, Double oldHigh, Double? closest)   {  return (closest.HasValue && high < closest.Value && oldHigh > target) || (closest.HasValue && high > closest.Value && oldHigh < target);   }   private static bool GoneToFarB(Double target, Double low, Double oldHigh, Double? closest)   {  return (closest.HasValue && low > closest.Value && oldHigh > target)  || (closest.HasValue && low < closest.Value && oldHigh < target);   }   private static bool NotDone(Double target, Double low, Double high, Double current, Double output, Double tempLow, Double tempHigh, int iterationsWithoutBetter, bool foundCloser)   {  return Math.Round(output, 11) != Math.Round(target, 11) && high != low && tempHigh != current && tempLow != current && (foundCloser || iterationsWithoutBetter < 15);   }   private static Boolean PassedFilter(Filter filter, Double current)   {  Boolean passedFilter = false;  if (filter != null)  { double? first = filter.value; double? second = filter.Process(current); passedFilter = (first != second);  }  else passedFilter = true;  return passedFilter;   } private static bool NewAndValid(Double target, List<Double> list, Double current, Double output)   {  return !list.Contains(Math.Round(current, 11)) && Math.Round(output, 11) == Math.Round(target, 11);   }