Bisection Plus Program

[Namir]

This program implements the new Bisection Plus algorithm for the HP-Prime. Click here to download a pdf file that discusses the new algorithm.

Algorithm

Code:

Given f(x)=0, the root-bracketing interval [A,B], and the tolerance for the root of f(x):

Calculate Fa = f(A) and Fb=f(B).
Exit if Fa*Fb > 0
X2 = A
Repeat 
  LastX2 = X2
  X1=(A+B)/2
  Fx1 = f(X1)
  If Fx1*Fa > 0 then
    Slope = (Fb – Fx1)/(B – X1)
    Intercept = Fb – Slope * B
  Else
    Slope = (Fa – Fx1)/(A – X1)
    Intercept = Fa – Slope * A
  End If  
  X2=-Intercept / Slope
  Fx2 = f(X2)
  If Fx1*Fx2 < 0 then
    A = X1
    Fa = Fx1
    B = X2
    Fb = Fx2
  Else
    If Fx2*Fa > 0 then
      A=X2
      Fa=Fx2
    Else
      B=X2
      Fb=Fx2
    End If
  End If  
Until |A-B| < tolerance OR |X2 - LastX2| < tolerance
Return X2

Listing

Code:

EXPORT FX(X)
BEGIN
  RETURN EXP(X)-3*X*X;
END;

EXPORT BISPLS(a,b,toler)
BEGIN
  LOCAL x1,x2,fa,fb,fx1,fx2,i;
  LOCAL slope,intercept,lastx2;
  
  fa:=FX(a);
  fb:=FX(b);
  IF fa*fb > 0 THEN
    RETURN "FA AND FB HAVE SAME SIGN";
  END;
  x2:=a;
  i:=0;
  REPEAT
    i:=i+1;
    lastx2:=x2;
    x1:=(a+b)/2;
    fx1:=FX(x1);
    IF fx1*fa > 0 THEN
      slope:=(fb-fx1)/(b - x1);
      intercept:=fb - slope * b;
    ELSE
      slope:=(fa - fx1)/(a - x1);
      intercept:=fa - slope * a;
    END;   
    x2:=-intercept / slope;
    fx2:=FX(x2);
    IF fx1*fx2 < 0 THEN
      a:=x1;
      fa:=fx1;
      b:=x2;
      fb:=fx2;
    ELSE
      IF fx2*fa > 0 THEN
        a:=x2;
        fa:=fx2;
      ELSE
        b:=x2;
        fb:=fx2;
      END;
    END;
  UNTIL (ABS(a-b) < toler OR ABS(x2 - lastx2) < toler);
  RETURN {x2, i};  
END;

Example

Find the root for f(x)=exp(x)-3*X^2 in teh range [3,4].

1. Type "BISPLS(3,4,1E-8) and press [ENTER].
2. The calculator displays {3.7330790286, 8}

The first number in the resulting list is the root. The second number is the iterations count.

Customization

Edit the code of function FX to implement the f(x) you want to work with.