Conference rusure::math

2014.0. "Computing the derivative of a rational function" by CXXC::REINIG (This too shall change) Fri Nov 17 1995 09:33

I found the following homework problem quite interesting.  

Let R(x) be a rational function computable by a straight-line algorithm
involving m arithmetical operations.  How many operations does it to compute
the derivative?


Let E be a field: (E, +, *, /, -), and let A be a subset of E.

A* is a straight-line algorithm of length m over (E,A) if A*=A(1),A(2),A(m),
where
                 -
                |   some a in A
                |   (-, j, k)   j,k < i
        A(i) = <    (+, j, k)   j,k < i
                |   (*, j, k)   j,k < i
                |   (/, j, k)   j,k < i
                 _

We shall define V, the value function inductively.  We introduce the symbol u
for undefined term (e.g. division by 0).  A(1) must be an element of A, so let
A(1) = a.  Then, V(1) = A(1).  Suppose that V(1),V(2),...,V(i-1) are
determined (possibly some of them equal to u).  Then

                 -
                |  A(i)          A(i) in A
                |  V(j) - V(k)   A(i) = (-, j, k)
        V(i) = <   V(j) + V(k)   A(i) = (+, j, k)
                |  V(j) * V(k)   A(i) = (*, j, k)
                |  V(j) / V(k)   A(i) = (/, j, k)
                 _

where we use the convention that x/y = u if y = 0 and  x op y = u if either
x = u or y = u and op one of {+, *, /, -}.