¿Cuál es la complejidad de la función de registro?

Question

¿Cuál es la complejidad de la función de base de registro ?

Answer 1

Esto realmente depende del dominio de qué valores desea calcular un logaritmo.

Para duplicados IEEE, muchos procesadores pueden tomar logaritmos en una sola instrucción de ensamblaje; x86 tiene las instrucciones FYL2X y FYL2XP1, por ejemplo. Aunque típicamente instrucciones como éstas sólo tomarán el logaritmo de alguna base fija, pueden ser utilizadas para tomar logaritmos en bases arbitrarias mediante el hecho de que

registro _un b = log _c b/log _c a

simplemente tomando dos logaritmos y encontrando su cociente.

Para enteros generales (de precisión arbitraria), puede usar la cuadratura repetida combinada con una búsqueda binaria para tomar logaritmos usando solo operaciones aritméticas O (log log n) (cada vez que cuadra un número duplica el exponente, lo que significa solo puede cuadrar el número log log n veces antes de exceder su valor y hacer una búsqueda binaria). Usando some cute tricks with Fibonacci numbers, puede hacer esto solo en el espacio O (log n). Si está calculando el binary logarithm, existen algunos trucos divertidos que puede usar con los cambios de bits para calcular el valor en menos tiempo (aunque la complejidad asintótica es la misma).

Para números reales arbitrarios, la lógica es más difícil. Puede usar el método de Newton o la serie de Taylor para calcular los logaritmos con una precisión determinada, aunque confieso que no estoy familiarizado con los métodos para hacerlo. Sin embargo, rara vez necesita hacer esto porque la mayoría de los números reales son IEEE dobles y hay mejores algoritmos (o incluso instrucciones de hardware) en ese caso.

Espero que esto ayude!