¿Cuál es la complejidad temporal de calcular sin(x) con t bits de precisión?

Question

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:

1. ¿Cuánto tiempo se tarda en calcular $\pi$ a $t$ ¿puntos de precisión?
2. ¿Cuánto tiempo se tarda en calcular $\sin(x)$ a $t$ ¿puntos de precisión?
3. ¿Cuánto tiempo se tarda en calcular $e^x$ a $t$ ¿puntos de precisión?
4. ¿Cuánto tiempo se tarda en calcular $\mathrm{erf}(x)$ a $t$ ¿puntos de precisión?
5. 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).

Answer 1

Knuth da varios algoritmos para el muestreo de una distribución normal utilizando funciones elementales, dadas las muestras de una distribución uniforme. Como en el caso anterior, la complejidad esperada es $O(M(n) \log{n})$ . Capítulo 7 de Recetas numéricas es un breve estudio de los métodos relacionados. Puede ser útil consultar el MPFR, ya que no puede asumir $O(1)$ operaciones en coma flotante. GSL tiene varias implementaciones.

Answer 2

Si supones que el coste de las operaciones aritméticas básicas es independiente de la precisión, lo cual, por supuesto, no es cierto y conoces de antemano el nivel de precisión deseado y precalculas algunas tablas. Puedes calcular sin(x) y cos(x) en tiempo lineal con respecto a la precisión utilizando el algoritmo CORDIC. Es decir, después de hacer un trabajo previo relativamente barato es posible calcular sin(x) y cos(x) para diferentes valores de x con la misma precisión de forma muy barata.