La función exponencial sobre números algebraicos

Dado un número algebraico , estoy interesado en encontrar una aproximación de ℜ ( e α ) hasta una precisión dada, donde ℜ ( ) se refiere a la parte real del número complejo.$\alpha$$\Re(e^\alpha)$$\Re()$

Formalmente, quiero calcular un número racional tal que | ℜ ( e α ) - r | ≤ 2 - $r$

$$|\Re(e^\alpha)-r|\leq 2^{-n}$$

está dado por un polinomio mínimo (estándar).$\alpha$

¿Qué tan rápido podemos resolver este problema?

---

Cuando se da como un punto flotante, la siguiente referencia$\alpha$

R. Brent. Evaluación rápida de precisión múltiple de funciones elementales. JACM, 1976.

Parece dar una respuesta.

Sin embargo, no estoy seguro de que pueda usarse para el número algebraico . $\alpha$

Tal como está escrito, el problema requiere un tiempo de , donde m es la longitud de entrada (desafortunadamente usó n para otra cosa). De hecho, si, por ejemplo, α es un número entero positivo (dado por su polinomio mínimo x - α ) yn = 0 , el tamaño de la salida es exponencial en el tamaño de la entrada. Este límite es, por supuesto, óptimo, ya que hay varias formas de calcular el resultado en el tiempo 2 O ( m ) .$2^{\Omega(m)}$$m$$n$$\alpha$$x-\alpha$$n=0$$2^{O(m)}$

---

Permítanme intentar reformular la pregunta para que tenga un poco más de sentido. El problema principal es cómo elegir la representación de la entrada y la salida, así como la noción de aproximación, de modo que la exponenciación tenga una gran posibilidad de ser computable en el tiempo polinómico.

Kaveh mencionó una forma en los comentarios: restringir el dominio a un intervalo finito fijo. Si bien esto funciona, es innecesariamente restrictivo; en particular, no hay una buena manera de transformar un número algebraico en uno que esté limitado de modo que sus exponenciales tengan algo que ver entre sí.

Un enfoque más flexible es representar la entrada como un número de punto fijo y la salida como un número de coma flotante . Para ser específicos, una representación de punto fijo es una cadena denota ± ∑ j a j 2 j , donde a j ∈ { 0 , 1 } , y una representación de coma flotante es ± 2 e

$$\pm a_ra_{r-1}\dots a_0.a_{-1}\dots a_{-s}$$ $\pm\sum_ja_j2^j$$a_j\in\{0,1\}$ con una interpretación similar, donde e es un número entero binario, y a 0 = 1 . (Como excepción, también permitimos que 0 se represente a sí mismo). Una aproximación de un x reala m bits deprecisiónabsolutaes un x ' realtal que | x - x ′ | < 2 - m , y una aproximación a m bits deprecisiónrelativaes $$\pm2^e\times a_0.a_{-1}\dots a_{-s}$$ $e$$a_0=1$$0$$x$$m$$x'$$|x-x'|<2^{-m}$$m$ tal que | 1 - x ′ / x | < 2 - m . Usaremos precisión absoluta para aproximaciones de punto fijo y precisión relativa para aproximaciones de punto flotante. Se deduce que en ambos casos, también podemos suponer s ≤ m (hasta la pérdida de un bit de precisión).$x'$$|1-x'/x|<2^{-m}$$s\le m$

Las representaciones de punto fijo y punto flotante de racionales gaussianos diádicos, y las aproximaciones de números complejos, se definen de manera similar, utilizando un par de reales. En todas partes a continuación, denota el tamaño total de la entrada.$n$

Ahora, dejemos que la exponenciación (real o compleja) sea ​​el siguiente problema: la entrada es una representación de punto fijo de un número un número natural unario m , y la salida es una aproximación de coma flotante de e x a m bits de relativa precisión. Dualmente, el logaritmo toma como entrada un número de coma flotante xy unario m , y la salida es una aproximación de punto fijo de log x (digamos, la rama principal en el caso complejo) a m bits de precisión absoluta.$x$$m$$e^x$$m$$x$$m$$\log x$$m$

Mientras nos atenemos a los límites de tiempo de ejecución que satisfacen algunas condiciones de regularidad leves, e ignoramos los factores multiplicativos constantes, tenemos:

• La complejidad de la exponenciación, el logaritmo o cualquier función analítica similar es, al menos, la complejidad de la multiplicación de enteros: por ejemplo, podemos leer de exp ( a 2 - t ) = a 2 - t + a 2 2 - 2 t - 1 + O ( a 3 2 - 3 t ) para t suficientemente grande , lineal en la longitud de a .$a^2$$\exp(a2^{-t})=a2^{-t}+a^22^{-2t-1}+O(a^32^{-3t})$$t$$a$
• La exponenciación y el logaritmo tienen la misma complejidad. La razón es que podemos calcular el inverso de una función agradable mediante la iteración de Newton (o métodos más sofisticados como en Brent ) utilizando la evaluación de la función misma. La iteración generalmente implica multiplicaciones o divisiones, pero podemos permitirnos esto en el punto anterior.

$\alpha$$f$$c,\rho$$|c-\alpha|<\rho$$\alpha$$f$

$\alpha$$m$$\alpha$$m$

$\DeclareMathOperator\re{Re}$$\re e^\alpha$$\alpha$$m$$e^\alpha$$m$

Realidad: hasta factores lineales, la complejidad de la exponenciación de números algebraicos es la misma que la complejidad de la aproximación de números algebraicos más la complejidad de la exponenciación compleja.

$\alpha$$m+O(1)$$\alpha$$e^\alpha$$m$

$e^\alpha$

Esto divide la pregunta en dos problemas bastante no relacionados. El límite superior más conocido en exponenciación es

$n$$M(n)$$O(M(n)\log n)$

$\Omega(M(n))$$M(n)$$n\log n\,2^{O(\log^*n)}$

$\tilde O(f(n))$$O(f(n)\mathrm{polylog}(f(n)))$

Para una aproximación de raíz real , Pan y Tsigaridas dan:

$\tilde O(d^2\tau+dm)$$d=\deg(f)$$\tau$$f$

$\tilde O(d^3+d^2m)$$f$$1+1/\log d$

---

$e^\alpha$$\re e^\alpha$$\re e^\alpha\ll\operatorname{Im}e^\alpha$$x+iy$$e^\alpha$$m$$y2^{-m}$$x$$x2^{-m}$

Para la exponenciación de racionales exactos, podemos evitar el problema:

$\alpha=x+iy$$m$$x,y$$\re e^\alpha$$m$$O(M(n)\log n)$

$\re e^\alpha=e^x\cos y$$e^x$$\cos y$$2^{-m}$$k$$2y/\pi$$\cos y$$\pm\cos y'$$\pm\sin y'$$y'=y-k\frac\pi2$$|y'|\le\pi/4$$\sin y'$$y'$$\sin y'$$m$$m+\log|{y'}^{-1}|$$y=u/v$$u,v$$y'$$\pi$

$$\left|\pi-\frac{2u}{kv}\right|\le\frac{2|y'|}k.$$ $\pi$$\nu$$7{.}6063$ $$|y'|\ge\frac1{2k^{\nu-1}v^\nu},$$ $\log|{y'}^{-1}|$$y'$$\sin y'$$y'$$\sin y'\approx y'$

$\alpha$$\log|y'|$$\deg(f)$