¿Cómo funciona el algoritmo de Knuth para calcular el logaritmo?

Question

Eché un vistazo a Knuth's El arte de la programación informática libro 1. En el capítulo 1, sección 1.2.2, ejercicio 25, presenta el siguiente algoritmo para calcular el logaritmo:

dado $x\in[1,2)$ haz lo siguiente:

L1: [Initialize] Set $y\leftarrow0$ , $z\leftarrow x/2$ , $k\leftarrow1$ .

L2: [Prueba de fin] Si $x=1$ para.

L3: [Compare] Si $x-z<1$ Pasa a la L5.

L4: [Reducir valores] Fijar $x\leftarrow x-z$ , $z\leftarrow x/2^k$ , $y\leftarrow y+\log_b(2^k/(2^k-1))$ y pasar a L2.

L5: [Shift] Set $z\leftarrow z/2$ , $k\leftarrow k+1$ y pasar a L2.

(El algoritmo necesita una tabla auxiliar que almacene $\log_b2$ , $\log_b(4/3)$ y así sucesivamente, hasta tantos valores como la precisión del ordenador.

Entonces Knuth concluye: este ejercicio es para explicar por qué el algoritmo anterior terminará y por qué calcula una aproximación de $y=\log_b x$ .

Bueno, veo que funciona, pero no soy capaz de explicar por qué...

Answer 1

La idea es que si podemos expresar $x$ como producto $x=\prod a_i$ donde el $1<a_{i+1}\leq a_{i}$ alors $\log x = \sum \log a_i$ y si el $a_i$ disminuyen lo suficientemente rápido, entonces podemos obtener una buena aproximación tomando sumas parciales, asumiendo que hemos precalculado $\log a_i$ .

Obviamente, con un algoritmo de este tipo, muy a menudo NO terminaremos, por lo que tendremos que parar cuando seamos lo suficientemente buenos. Esto se debe a que si el $a_i$ se eligen de un conjunto contable $B=\{b_i\}$ entonces sólo un número contable de números tendrá expresiones como productos de sólo un número finito de $b_i$ (mediante repeticiones). Así que el paso $L2$ tiene que ser modificado a una condición como $|x-1|<\epsilon$ para algunos $\epsilon$ determinar la precisión.

¿Qué hace el algoritmo? En cada etapa, comienza con $x$ y encuentra el más pequeño $k$ tal que $x-z=x(1-2^{-k})>1$ lo que equivale a $x>(1-2^{-k})^{-1}=\frac{2^k}{2^k-1}=a_i$ . A continuación, sustituimos $x$ con $x/a_i$ y continuar recursivamente, sabiendo que $\log x = \log a_i + \log x/a_i$ .

Al final, sabemos que estaremos fuera de mi un factor (multiplicativo) de no más de $\log(1+\epsilon)\approx \epsilon$ (si $\epsilon$ es pequeño, y podemos utilizar las series de Taylor para poner límites explícitos a $\epsilon$ para que el error de esta aproximación sea tan pequeño como se desee), y debido a nuestra suposición de que $1\leq x <2$ esto se traduce en un error absoluto de como máximo $\log 2 \log (1+\epsilon) < 2\epsilon$ .