An Attempt to Challenge the Bisection method for root findin Namir Unregistered Posts: 2,247 Threads: 200 Joined: Jun 2005 08-13-2011, 12:18 PM Early this morning I had a curios idea in my head. How do the following two modifications to the Bisection method stack up against the Bisection method for finding roots? 1. A Random Method where we select a point at random inside the root-bracketing interval. The selected point's function value determines which part of the interval [A,B] to keep in order to zoom in on the root. 2. A Hybrid method in which we alternate between a regular Bisection step that chooses the midpoint in interval [A,B] and random step that chooses at random a point inside [A, B]. I ran 100,000 iterations to find the zero in [3,4] for my function e^x-3*x^2 = 0. The results are: 1. The hybrid method outperformed the Bisection method only in 5% of the iterations. The maximum saving in iterations was 10. The average and std deviation in iterations saved were about 2.0 and 1.26 iterations. 2. The Random method outperformed the Bisection method only in 2% of the iterations. The maximum saving in iterations was 11. The average and std deviation in iterations saved were about 2.5 and 1.72 iterations. The histogram for the savings in iterations for both methods looks like an exponential decay. So for now, the Bisection has done better than the above two suggested modifications. That was fun!! Namir Marcus von Cube, Germany Unregistered Posts: 3,283 Threads: 104 Joined: Jul 2005 08-13-2011, 05:46 PM It simply depends on how smooth your function is. The close the two points are the more the function between them looks like a straight line and bisection would give the exact result. (Or did I just mix up bisection with the Regula Falsi?) Namir Unregistered Posts: 2,247 Threads: 200 Joined: Jun 2005 08-13-2011, 07:18 PM The Bisection looks only at the sign of the functions' values. The Reguli Falsi uses the function values as weights to estimate the new guess inside the root-bracketing interval. I developed the Quartile algorithm a few years ago, which performs better than the Bisection. The new method compares the absolute values of the function to calculate the refined guess (also inside the root-bracketing interval). Dieter Unregistered Posts: 653 Threads: 26 Joined: Aug 2010 08-14-2011, 09:41 AM Quote: (Or did I just mix up bisection with the Regula Falsi?) Yes. Bisection simply means that, if f(x=2) is > 0 and f(x=10) < 0, try x=6 next. The regula falsi (linear interpolation) uses a weighted average instead. If f(x=2) is 8 and f(x=10) is -4, i.e. "twice as close" to zero, the new estimate divides the x-interval [2; 10] the same way. So the next value is 7,33. Dieter Namir Unregistered Posts: 2,247 Threads: 200 Joined: Jun 2005 08-14-2011, 10:06 AM Reguli False has a little negative feature in that it does not intuitively shrink the root-bracketing interval like Bisection does. If you are using Reguli Falsi, you might as well switch to the tangent method. I believe the HP-34 Solve is based on the tangent method. Namir Dieter Unregistered Posts: 653 Threads: 26 Joined: Aug 2010 08-14-2011, 10:22 AM Quote: I believe the HP-34 Solve is based on the tangent method. Since you say HP-34 and not WP-34 I think you refer to the HP-34C. As far as I know the 34C uses a modified secant method, i.e. a variation of the regula falsi. The WP-34s uses Brent's algorithm where several methods are combined. I assume that "tangent method" refers to something like Newton's algorithm, i.e. place a tangent to the graph and find its intersection with the x-axis. Such a method requires just one initial guess, while HP Solve (just as the 34s) requires two guesses, preferably with opposite signs of the function result. Dieter Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 08-14-2011, 05:57 PM I'm pretty sure the 34C uses a modified secant method. It has checks for going too far and escaping a bracketing interval. The 34S uses Brent's method which fits a quadratic in the best case. it also has guards and interval bracketing in place. - Pauli « Next Oldest | Next Newest »

 Possibly Related Threads… Thread Author Replies Views Last Post A fast Bernoulli Number method for the HP Prime Namir 16 5,281 11-22-2013, 04:46 PM Last Post: Namir [HP Prime] Using n-root symbol and exponent problem uklo 7 2,784 11-11-2013, 01:39 AM Last Post: Alberto Candel [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 2,349 11-05-2013, 02:44 AM Last Post: Marcus von Cube, Germany HP PRIME - Bode and Black plots - first attempt dg1969 0 1,011 10-20-2013, 01:32 PM Last Post: dg1969 A brand new calculator benchmark: "middle square method seed test" Pier Aiello 25 6,657 09-13-2013, 01:58 PM Last Post: Pier Aiello Cubic root (-8) = 2 ? Gilles Carpentier 37 9,875 08-12-2013, 10:26 PM Last Post: jep2276 Downhill Simplex Method (Nelder Mead) for WP-34S Marcel Samek 0 855 07-07-2013, 03:05 AM Last Post: Marcel Samek Square Root Simplifier for HP39gII Mic 4 1,908 03-11-2013, 08:25 AM Last Post: Eddie W. Shore Cube root on standard calculator Thomas Klemm 22 6,126 11-09-2012, 06:11 AM Last Post: Pierre RPN HP39gII : An attempt to summarize our discusion Gilles Carpentier 18 4,525 07-27-2012, 06:44 PM Last Post: Gilles Carpentier

Forum Jump: