Calcular el pecado hiperbólico más rápido que con una serie de potencias estándar

Question

Utilizando $$ \sinh x = x + \tfrac{x^3}{3!}+ \tfrac{x^5}{5!} + \tfrac{x^7}{7!}+ \cdots$$ como la serie Standard Power. Esta serie tarda mucho tiempo en ejecutarse. ¿Se puede escribir sin usar los exponenciales divididos por un factorial enorme? Las funciones de ejemplo en ¿Hay alguna forma de obtener las funciones trigonométricas sin una calculadora? utilizando la representación en serie de "Taylor adaptada" para el seno y el coseno son muy rápidos y dan las mismas respuestas. Quiero usarlo dentro de mi programa de calculadora.

Muchas gracias.

Answer 1

Tenga en cuenta que $$\sinh x=\frac{e^x-e^{-x}}2$$ Así que todo lo que necesitas es una forma rápida de calcular la exponencial $e^x$ . Puedes usar la serie de Taylor normal, pero eso es lento. Así que puedes usar la definición $$e^x=\lim_{n\to\infty}\left(1+\frac xn\right)^n$$ Para el cálculo, utilice $n$ como un poder de $2$ , $n=2^k$ . Primero se calcula $y=1+\frac x{2^k}$ , entonces se repite el $y=y\cdot y$ operación $k$ tiempos. La idea de calcular la exponencial rápida la he sacado de esto artículo .

Answer 2

Permítanme considerar el problema desde un punto de vista informático suponiendo que no se sabe cómo calcular $e^x$ .

La serie infinita es $$\sinh(x)=\sum_{n=0}^\infty \frac{x^{2n+1}}{(2n+1)!}$$ Si se calcula cada término independientemente del otro, seguro que es caro, ya que hay que calcular cada potencia de $x$ así como cada factorial.

Pero supongamos que en lugar de eso escribes $$\sinh(x)=\sum_{n=0}^\infty T_n \qquad \text{where} \qquad T_n=\frac{x^{2n+1}}{(2n+1)!}\qquad \text{and} \qquad T_0=x$$ entonces $$T_{n+1}= \frac {t\,\, T_n}{m(m+1)}\qquad \text{where} \qquad t=x^2\qquad \text{and} \qquad m=2n+2$$ Esto sería mucho menos costoso en términos de operaciones básicas y número de ellas.

Se podría utilizar el mismo truco para la mayoría de las funciones expresadas como series infinitas.

Answer 3

Una opción mucho mejor que la respuesta de Andrei es utilizar la identidad $\exp(x) = \exp(x·2^{-k})^{2^k}$ para la elección juiciosa de $k$ y utilizar la serie de Taylor para aproximar $\exp(x·2^{-k})$ con suficiente precisión.

Supongamos que queremos calcular $\exp(x)$ utilizando la identidad anterior para $p$ -bit de precisión, lo que significa un error relativo de $2^{-p}$ . Realizaremos cada operación aritmética con $q$ -bit de precisión, donde $q=p+k+m$ y $k,m$ son enteros positivos que determinaremos más adelante. Para calcular $\exp(x·2^{-k})^{2^k}$ con error relativo $2^{-p}$ necesitamos calcular $\exp(x·2^{-k})$ con un error relativo como máximo de alrededor de $r_0 := 2^{-p-k-1}$ porque en cada cuadratura el error $r_n$ cambia a alrededor de $r_{n+1} ≤ 2r_n+2^{-q}$ , dando $r_k+2^{-q} ≤ (r_0+2^{-q})·2^k$ y por lo tanto $r_n ≤ 2^{-p}$ .

Por lo tanto, necesitamos utilizar suficientes términos de la expansión de Taylor para $\exp(x·2^{-k})$ para que nuestro error sea como máximo $|\exp(x·2^{-k})|·2^{-p-k-1}$ . Si $k = \max(0,\log_2 |x|) + c$ para algún número entero positivo $c$ entonces $|x·2^{-k}|<2^{-c}$ y así $|\exp(x·2^{-k})| > \exp(-1/2) > 1/2$ por lo que basta con que nuestro error sea menor que $2^{-p-k-1}/2$ . Asignamos este margen de error a dos mitades, una para el resto de Taylor y otra para el error en nuestras operaciones aritméticas. Dejando que $z := x·2^{-k}$ tenemos $\sum_{i=n}^∞ |z^i/i!| ≤ |z|^n/n! · \sum_{i=0}^∞ (|z|/n)^i ≤ |z|^n/n! ≤ 2^{-c·n}$ para cualquier $n ≥ 1$ por lo que sólo tenemos que calcular $\sum_{i=0}^{n-1} z^i/i!$ donde $n ≥ 1$ y $2^{-c·n} < 2^{-p-k-1}/4$ , ambos se mantienen si $c·n ≥ p+k+3$ . Cada término requiere una suma, una multiplicación y una división, a través de la identidad trivial $z^{n+1}/(n+1)! = z^n/n! · z/n$ y, por tanto, si empezamos con $z$ en $q$ -de precisión, entonces el error relativo acumulado es, como máximo, de unos $2n·2^{-q}$ ya que cada " $· z/n$ "introduce un factor de error adicional de aproximadamente $(1+2^{-q})^2$ . Como queremos $2n·2^{-q} < 2^{-p-k-1}/4$ , o lo que es lo mismo $n < 2^{m-4}$ es suficiente con tener $m = \log_2 n + 4$ .

Incluso si utilizamos la multiplicación de los libros de texto, es decir, que la multiplicación en $q$ -La precisión de los bits se lleva $O(q^2)$ tiempo, el método anterior produce un algoritmo relativamente eficiente al elegir $k$ adecuadamente. La fase de Taylor toma $O(n·q^2)$ tiempo, y la fase de exponenciación tarda $O(k·q^2)$ tiempo. Si elegimos $c = \sqrt{p}$ podemos elegir $n = \sqrt{p}+k$ que dará $k,n ∈ O( \sqrt{p} + \log |x| )$ y $q ∈ O( p + \log |x| )$ . Así, para $x$ dentro de un dominio acotado, todo el algoritmo tarda $O(p^{2.5})$ tiempo.

---

Lo anterior se basa en técnicas puramente elementales. Un análisis más cuidadoso utilizando las mismas técnicas arroja un algoritmo aún mejor (véase Evaluación eficiente de funciones elementales de precisión múltiple ).

Hay formas de hacerlo mucho mejor, que se reducen básicamente a utilizar una iteración AM-GM para calcular $\ln$ y, a continuación, utilizando la inversión de Newton-Raphson para obtener $\exp$ (ver La media aritmética-geométrica y el cálculo rápido de funciones elementales ).