This is a very simple Puzzlet:  find the root of the equation shown above.  To make it even simpler, I can tell you the answer is somewhere in the region of 2.  However, just to make it a little more interesting,   you’re asked to work to 10 decimal places of accuracy …

Cubic equations are difficult to solve by formula or other means.  An extremely effective iterative technique is known as Newton’s Method.  It involves successive approximations based on slope of the curve at the root.  At each iteration, the process declares:

A better root r_b is equal to the current root r _c minus f( r_c )/f’( r_c ). 

That is, the root can be refined by subtracting from the current root the function’s  value divided by the value of the first differential of the   function.  Just  keep doing this until the required degree of accuracy has  been  reached.  You can see this in action in the Ibasic code below, and it’s explained further in the commentary boxes.

' Puzzlet #005.
' Find the root of the following equation:
' x³ - x² - x = 1.  The answer must be
' accurate to ten decimal places.
' By Dave Ellis.

def p, r: double
' p = f(root), r = f'(root) because the
' algorithm uses Newton's Method
def oldRoot, root: double
def flag, itCount: int
root = 2.0
flag = 0
itCount = 0
openconsole

do
    itCount = itCount + 1
    oldRoot = root
   p = root ^   3 - root ^   2 - root - 1
   r = 3*root ^   2 - 2*root - 1
    root = root - p/r
    if abs(root - oldRoot) < .00000000001
        flag = -1
    endif
until flag = -1 | itCount > 20

print "Root of equation is ",
print using ("#.##########", root)
print: print "That's all, folks!"
print: print "Press any key to continue ..."
do:until inkey$ <> ""
closeconsole
end


PROGRAM NOTES

Variable root is initially set to 2.0,   since we were given this hint to begin with.  Variable oldRoot is used to take root ’s current value when a new value is  established.  

Variable flag will be used to indicate when  the required degree of accuracy  has been reached, and itCount is used to count the number of iterations taken to get there.

Variable p holds the value obtained when the equation is evaluated with oldRoot.  Note the equation is rearranged here to include all terms on the LHS: 
x ³ – x² – x – 1.

Variable r holds the value when the equation is evaluated with the first differential of the equation.  In this case, 3x ² – 2x – 1.

If the difference between root and oldRoot is less than 10^-11, we have the required degree of accuracy, and can set flag.

When flag is set (-1, or TRUE), the DO loop is exited.  Note that an alternative exit condition occurs if itCount exceeds  20.  This is a safety measure.  Newton’s method converges so quickly that, if you haven’t reached a solution by then, you aren’t going to!  Things are diverging, which means your original guess at the root was too far from the actual root.  This alternative exit prevents the computer hanging.   The rest of the code is just a way of pretty-printing the solution.

When you run the code, it produces the inset screen.  As hinted in the introduction, the answer is quite close to 2.  This is the only root to the equation, although it does have turning points.

Root of equation x^3 - x^2 - x = 1: 1.8392867552, to 10 decimal places. It took 5 iterations to find. Press any key to continue ...