Iterative calculation of $\log x$ Suppose one is given an initial approximation of $\log x$, $y_0$, so that:
$$y_0 = \log x + \epsilon \approx \log x$$
Here, all that is known about $x$ is that $x>1$. Is there a general method of improving that estimation using only addition & multiplication, i.e. without exponentiation or logarithms?
$$y_1 = f(y_0, x)=\ ?$$

I don't know of any way to improve a close guess of the log as you do with square root in Newton-Raphson unless you have the inverse of the log function.  Note that the exponential is easy to evaluate for small arguments because it is a rapidly converging power series.  
If you have an exact log of a number z that is close to x, calculate w=x/z.   w  will be close to 1.  And it is quick and easy to calculate the natural log of numbers close to 1.  
Crude: use ln(w) = w-1
Less crude:  a1 = (1+w)/2, and approximate ln(w) = (w-1)/a1.  This looks like trapezoidal integration 1 to w of dt/t.  You could do better with simpson's rule and other numerical integration methods, but that is not where I want to lead you.
Better: g1 = Sqrt(w), and approximate ln(w) = (w-1)/g1
Continuing, we can get better divisors.  a2 = (a1+g1)/2, g2 = Sqrt(a2*g1), etc.  This does not have quadratic convergence like the Gauss AGM algorithm, but it can be accelerated by the same method used in HP calculator's Romberg accelerated trapezoidal integrator.  See Carlson, "An Algorithm for Computing Logarithms and Arctangents", Mathematics of Computation, April 1972.  Only a few iterations are needed for very great accuracy. This was taught to me by Nate Grossman of UCLA at a Forth Interest Group meeting way back in the last century.  (Another or his favorite methods was Newton-Raphson on the exponential.)
A lot of our numerical technology involves strategies for avoiding "slow" operations on the computer: multiplication, inverse, square root, etc.  Some day these will be incorporated into hardware and take only a single machine cycle.  New worlds of high speed computing will open up.  Until then, fast calculation of logs is a core infrastructure of number crunching and a rich field for further exploration.
This is not exactly what you wanted, but I hope it is helpful.  
