Cálculo iterativo de $\log x$

Question

Supongamos que se tiene una aproximación inicial de $\log x$, $y_0$, de modo que: $$y_0 = \log x + \epsilon \approx \log x$$

Aquí, todo lo que se sabe sobre $x$ es que $x>1$. ¿Existe un método general para mejorar esa estimación solo usando sumas y multiplicaciones, es decir, sin exponenciación o logaritmos? $$y_1 = f(y_0, x)=\ ?$$

Answer 1

Hace mucho tiempo, en el siglo pasado, tenía una calculadora temprana sin función logarítmica. Para hacer un logaritmo, presionaba el botón de raíz cuadrada diez veces, restaba $1$ y multiplicaba por $1,024$. La respuesta era precisa hasta $4$ decimales, lo cual era mejor que lo que mis dos palos calibrados podían ofrecer. La raíz cuadrada es una función poderosa que se puede usar para aproximar muchas otras.

No ridiculices los palos calibrados; ¡fueron los que hicieron la mayor parte de la ingeniería que nos llevó a la luna! Recientemente construí una regla de cálculo con palitos de Starbucks que hace multiplicación módulo $23$. Usé logaritmos en base $7$.

Answer 2

En cualquier caso, también necesitas saber que $x_0=e^{y_0}$.

Luego, la corrección se da por $y-y_0=\ln\left(\dfrac x{x_0}\right)=\ln(1+\delta)$, donde $\delta$ es pequeño. Puedes evaluarlo por Taylor, lo cual convergerá linealmente,

$$\ln(1+\delta)\approx\delta-\frac{\delta^2}2+\frac{\delta^3}3\cdots$$

También puedes limitarte a la primera término $$\ln(1+\delta)\approx\delta,$

pero entonces tendrás que corregir con $x_1=x_0e^{-\delta}\approx x_0\left(1-\delta+\frac{\delta^2}2\cdots\right)$, lo que converge un poco más rápido.

No creo que haya un atajo.

---

Un enfoque similar se da por el método CORDIC.

Precomputa una serie de constantes decrecientes $l_k=\log(a_k)$, por ejemplo $a_k=1+2^{-k}$.

Aplicarás los siguientes pasos para todos los $k$ sucesivamente:

$$\text{mientras } a_kx_n

(Si $a_{k+1}>\sqrt{a_k}$, un $\text{if}$ es suficiente.)

Answer 3

En lugar de resolver $y - \ln(x) = 0$ para $y$ puedes resolver $g(y) = e^y - x = 0$

Dada la aproximación inicial $y_0 \approx \ln(x)$ puedes intentar resolver $y$ usando el método de Newton:

$$y_{n + 1} = y_n - \frac{g(y_n)}{g'(y_n)}= y_n - \frac{e^{y_n} - x}{e^{y_n}} = y_n - 1 +\frac{x}{e^{y_n}}$$

Cuando no está permitida la exponenciación puedes aproximar $e^{y}$ con $\left(1 + \frac{y}{2^m} \right)^{2^m}$ usando multiplicación repetida: $$\begin{aligned} \left(1 + \frac{y}{2^m} \right)^{2^m} &= \left(1 + \frac{y}{2^m} \right)^{2^{m - 1}} \cdot \left(1 + \frac{y}{2^m} \right)^{2^{m - 1}} \\ \\2^{-m} &= \frac{1}{2} \cdot 2^{-m + 1}\end{aligned}$$

Answer 4

No conozco ninguna forma de mejorar una aproximación cercana del logaritmo como lo haces con la raíz cuadrada en Newton-Raphson a menos que tengas la función inversa del logaritmo. Ten en cuenta que la exponencial es fácil de evaluar para argumentos pequeños porque es una serie de potencias que converge rápidamente.

Si tienes un logaritmo exacto de un número z que está cerca de x, calcula $w=x/z$. $w$estará cerca de 1. Y es rápido y fácil calcular el logaritmo natural de números cercanos a 1.

Crudo: utiliza $\ln(w) = w-1$

Menos crudo: $a1 = (1+w)/2$, y aproxima $\ln(w) = (w-1)/a1$. Esto parece una integración trapezoidal de 1 a w de dt/t. Podrías hacerlo mejor con la regla de Simpson y otros métodos de integración numérica, pero no es hacia donde quiero dirigirte.

Mejor: $g1 = \sqrt w$, y aproxima $\ln(w) = (w-1)/g1$

Continuando, podemos obtener mejores divisores. $a2 = (a1+g1)/2, g2 = \sqrt{a2*g1}$, etc. Esto no tiene convergencia cuadrática como el algoritmo Gauss AGM, pero puede ser acelerado por el mismo método utilizado en el integrador trapezoidal acelerado de Romberg de la calculadora HP. Consulta Carlson, "Un algoritmo para calcular logaritmos y arcotangentes", Matemáticas de la Computación, abril de 1972. Solo se necesitan unas pocas iteraciones para una gran precisión. Esto me lo enseñó Nate Grossman de la UCLA en una reunión del Forth Interest Group en el siglo pasado. (Otro de sus métodos favoritos era Newton-Raphson en la exponencial.)

Una gran parte de nuestra tecnología numérica implica estrategias para evitar operaciones "lentas" en la computadora: multiplicación, inverso, raíz cuadrada, etc. Algún día estas serán incorporadas en el hardware y tomarán solo un ciclo de máquina. Se abrirán nuevos mundos de computación de alta velocidad. Hasta entonces, el cálculo rápido de logaritmos es una infraestructura fundamental para el procesamiento numérico y un campo rico para seguir explorando.

Esto no es exactamente lo que querías, pero espero que sea útil.

Answer 5

Considera el hecho de que el número con el que estás trabajando es un número de punto flotante, entonces el logaritmo de éste es

$\log( b ) = \log( 2^{\rm exp} * 1.S )$, donde exp es el exponente y S es la mantisa.

$\log( b ) = \text{exp} * \log( 2 ) + \log( 1.S )$

Dado que $1.S$ está entre 1 y 2, asume que es 2 entonces

$\log( b ) ~ (\text{exp} + 1) * \log( 2 )$.

Un par de iteraciones deberían dar el valor correcto entonces.