Versión corta de la pregunta: Presumiblemente, es poli $(t)$ . Pero, ¿qué polinomio, y podría proporcionar una referencia?
Versión larga de la pregunta: Me sorprende preguntar esto, porque es una pregunta que suena muy básica. He aquí algunas variantes de la misma:
- ¿Cuánto tiempo se tarda en calcular $\pi$ a $t$ ¿puntos de precisión?
- ¿Cuánto tiempo se tarda en calcular $\sin(x)$ a $t$ ¿puntos de precisión?
- ¿Cuánto tiempo se tarda en calcular $e^x$ a $t$ ¿puntos de precisión?
- ¿Cuánto tiempo se tarda en calcular $\mathrm{erf}(x)$ a $t$ ¿puntos de precisión?
- Cuánto tiempo y cuántos bits aleatorios se necesitan para generar una variable aleatoria (discreta) $X$ de manera que haya un acoplamiento de $X$ con una gaussiana estándar $Z \sim N(0,1)$ para lo cual $|X - Z| < \delta$ excepto con una probabilidad máxima de $\epsilon$ ?
En mi área de la teoría de la ciencia de la computación, nadie parece prestar mucha atención a estas cuestiones; la descripción de un algoritmo podría decir típicamente
"Generar dos variables aleatorias gaussianas $Z$ y $Z'$ y comprobar si $\sin(Z \cdot Z') > 1/\pi$ "
o algo así. Pero técnicamente, uno debería preocuparse por la complejidad del tiempo aquí.
Un colega que es más experto en estas cosas me aseguró que todas esas "funciones de calculadora" llevan como mucho un tiempo poli $(t)$ . Creo que esto es cierto. Pero de nuevo, ¿qué polinomio (por curiosidad, al menos), y cuál es la referencia?
Supuse que las respuestas estarían en todos los libros de texto de análisis numérico, pero no pude encontrarlas. Parece (quizás razonablemente) que el análisis numérico se preocupa principalmente de obtener las respuestas con una precisión fija como 32 o 64 bits o lo que sea. Pero es de suponer que alguien ha pensado en obtener los resultados con una precisión arbitraria, ya que se puede escribir
Digits := 5000; erf(1.0);en Maple y te dará una respuesta de inmediato. Pero parecía difícil de encontrar. Después de mucho buscar, di con la frase clave "algoritmo no restringido" que me llevó al artículo "An unrestricted algorithm for the exponential function", Clenshaw-Olver-1980. Es bastante difícil de leer, ya que analiza la complejidad temporal para $e^x$ en términos de ocho (??!) parámetros, pero su ecuación (4.55) parece dar algunas respuestas: quizás $\tilde{O}(t^2)$ suponiendo que $|x|$ es constante?
Y realmente, todo ese trabajo para el pequeño $e^x$ ? En cuanto a erf $(x)$ En el año 2009 encontré el artículo "The functions erf and erfc computed with arbitrary precision" de Chevillard. Era más fácil de leer, pero todavía me llevaría algún tiempo extraer la respuesta; mi primera impresión fue $\tilde{O}(t^{3/2})$ . Pero, de nuevo, seguro que esta cuestión no se investigó por primera vez en 2009, ¿verdad?
(Por cierto, la pregunta #5 es la que realmente quiero saber la respuesta, pero probablemente pueda resolverla a partir de la respuesta a la pregunta #4).
