A função exponencial sobre números algébricos

Como está escrito, o problema requer tempo , onde é o comprimento da entrada (infelizmente você usou para outra coisa). Com efeito, se por exemplo é um número inteiro positivo (dado pela sua mínima polinomial ) e , o tamanho da saída é exponencial do tamanho da entrada. É claro que esse limite é ideal, pois existem várias maneiras de calcular o resultado no tempo . $2^{\Omega(m)}$ $m$ $n$ $\alpha$ $x-\alpha$ $n=0$ $2^{O(m)}$

Deixe-me tentar reformular a questão para que faça um pouco mais de sentido. A questão principal é como escolher a representação da entrada e saída, bem como a noção de aproximação, para que a exponenciação tenha uma chance de ser computável em tempo polinomial.

Uma maneira foi mencionada por Kaveh nos comentários: restringir o domínio a um intervalo finito fixo. Enquanto isso funciona, é desnecessariamente restritivo; em particular, não há uma boa maneira de transformar um número algébrico em um que seja delimitado, de modo que seus exponenciais tenham algo a ver um com o outro.

Uma abordagem mais flexível é representar a entrada como um número de ponto fixo e a saída como um número de ponto flutuante . Para ser específico, uma representação de ponto fixo é uma sequência denotando , onde , e uma representação de ponto flutuante é

\pm a_{r} a_{r - 1} \dots a_{0} . a_{- 1} \dots a_{- s}

$\pm a_ra_{r-1}\dots a_0.a_{-1}\dots a_{-s}$

\pm \sum_{j} a_{j} 2^{j}

$\pm\sum_ja_j2^j$

a_{j} \in {0, 1}

$a_j\in\{0,1\}$

com uma interpretação semelhante, onde

é um número inteiro binário e

. (Como uma exceção, nós também permitir

para representar a si mesmo.) Uma aproximação de uma verdadeira

bits deabsolutaprecisão é um verdadeiro

tal que

, e uma aproximação de

bits derelativaprecisão é

\pm 2^{e} \times a_{0} . a_{- 1} \dots a_{- s}

$\pm2^e\times a_0.a_{-1}\dots a_{-s}$

e

$e$

a_{0} = 1

$a_0=1$

0

$0$

x

$x$

m

$m$

x^{'}

$x'$

| x - x^{'} | < 2^{- m}

$|x-x'|<2^{-m}$

m

$m$

tal que

. Usaremos precisão absoluta para aproximações de ponto fixo e precisão relativa para aproximações de ponto flutuante. Segue-se que em ambos os casos, também podemos assumir

(até perda de um bit de precisão).

x^{'}

$x'$

| 1 - x^{'} / x | < 2^{- m}

$|1-x'/x|<2^{-m}$

s \leq m

$s\le m$

Representações de ponto fixo e ponto flutuante de racionais gaussianos diádicos e aproximações de números complexos são definidas de forma semelhante, usando um par de reais. Em todos os lugares abaixo, indica o tamanho total da entrada. $n$

Agora, deixe (real ou complexa) exponenciação ser o seguinte problema: a entrada é uma representação de ponto fixo de um número e um unária número natural , e a saída é uma aproximação de ponto flutuante de a bits de precisão relativa. Dualmente, o logaritmo toma como entrada um número de ponto flutuante e unário , e a saída é uma aproximação de ponto fixo do (por exemplo, o ramo principal no caso complexo) a bits de precisão absoluta. $x$ $m$ $e^x$ $m$ $x$ $m$ $\log x$ $m$

Enquanto mantemos limites de tempo de execução que satisfazem algumas condições de regularidade moderada e ignoramos fatores multiplicativos constantes, temos:

A complexidade da exponenciação, logaritmo ou qualquer função analítica semelhante é pelo menos a complexidade da multiplicação de números inteiros: por exemplo, podemos ler de para suficientemente grande , linear no comprimento de . $a^2$ $\exp(a2^{-t})=a2^{-t}+a^22^{-2t-1}+O(a^32^{-3t})$ $t$ $a$
Exponenciação e logaritmo têm a mesma complexidade. A razão é que podemos calcular o inverso de uma função agradável pela iteração de Newton (ou métodos mais sofisticados, como no Brent ), usando a avaliação da própria função. A iteração normalmente envolve multiplicações ou divisões, mas podemos pagá-las pelo ponto anterior.

Quanto aos números algébricos , eles podem ser representados por seu polinômio mínimo (escrito como uma sequência de coeficientes inteiros em binário) junto com alguns meios para distinguir entre as raízes do mesmo polinômio. Uma maneira natural de fazer isso é exigir um intervalo ou disco de isolamento: um par de números de pontos fixos tal que . Precisamos pelo menos exigir que seja uma raiz única de com essa propriedade, mas algo mais forte pode ser mais adequado. Mais sobre isso mais tarde. $\alpha$ $f$ $c,\rho$ $|c-\alpha|<\rho$ $\alpha$ $f$

Deixe a aproximação do número algébrico ser o seguinte problema: dado um número algébrico na representação acima, e em unário, calcule uma aproximação (complexa) de ponto fixo de a bits de precisão absoluta. $\alpha$ $m$ $\alpha$ $m$

$\DeclareMathOperator\re{Re}$ A pergunta original solicitou , mas deixe-me ignorá-lo por enquanto e definir a exponenciação algébrica de números como o seguinte problema: dado e como acima, calcule uma aproximação (complexa) de ponto flutuante de a bits relativos precisão. $\re e^\alpha$ $\alpha$ $m$ $e^\alpha$ $m$

Fato: Até fatores lineares, a complexidade da exponenciação algébrica de números é a mesma que a complexidade da aproximação de números algébricos mais a complexidade da exponenciação complexa.

Esboço de prova: por um lado, podemos primeiro calcular a aproximação de ponto fixo de e exponenciá-la. Observe que bits de precisão absoluta para determinam a bits de precisão relativa e vice-versa. $\alpha$ $m+O(1)$ $\alpha$ $e^\alpha$ $m$

Por outro lado, se podemos fazer exponenciação algébrica de números, também podemos fazer exponenciação simples, pois podemos facilmente converter um número de ponto fixo (considerado exato) em sua representação como um número algébrico. Pelos comentários acima, isso significa que também podemos calcular logaritmos no mesmo tempo. Assim, podemos aproximar um número algébrico primeiro aproximando e, em seguida, obtendo um logaritmo. QED $e^\alpha$

Isso divide a questão em dois problemas não relacionados. O limite superior mais conhecido na exponenciação é

Teorema ( Brent ): Se podemos multiplicar números inteiros de bits no tempo , podemos calcular exponenciação complexa (e logaritmo) no tempo . $n$ $M(n)$ $O(M(n)\log n)$

O limite inferior mais conhecido é o mencionado acima. O limite superior mais conhecido em é $\Omega(M(n))$ $M(n)$ pelo algoritmo de Fürer. $n\log n\,2^{O(\log^*n)}$

Descobrir o estado da arte para a aproximação de números algébricos (ou seja, encontrar raízes) é um pouco mais difícil, pois ainda é uma área de pesquisa ativa, e as formulações de limites na literatura geralmente não são tão claras quanto se deseja. Vamos significam . $\tilde O(f(n))$ $O(f(n)\mathrm{polylog}(f(n)))$

Para uma aproximação real da raiz, Pan e Tsigaridas fornecem:

Teorema: real número aproximação algébrica pode ser feito em tempo , onde , e é máximo de bits de comprimentos dos coeficientes de . $\tilde O(d^2\tau+dm)$ $d=\deg(f)$ $\tau$ $f$

No mesmo artigo, eles mencionam como o limite mais conhecido para a aproximação de raízes complexas . Em um artigo um pouco mais recente ( http://arxiv.org/abs/1404.4775 ), eles parecem reivindicar os mesmos limites para o caso complexo e para o caso real, supondo que o disco de isolamento fornecido tenha uma taxa de isolamento (o distância do centro do disco à outra raiz mais próxima de dividida pelo raio do disco) pelo menos , aproximadamente, mas está escrito de uma maneira bastante confusa e posso interpretá-lo mal. $\tilde O(d^3+d^2m)$ $f$ $1+1/\log d$

Agora, a complicação final. Eu defini o problema como aproximação de , enquanto a pergunta pede . Isto, na verdade, faz com que o problema mais difícil: se , em seguida, uma aproximação de para bits de precisão relativa tem erro , o que pode muito bem ser superior a em si, e em qualquer caso, não é garantido para ser delimitada por . $e^\alpha$ $\re e^\alpha$ $\re e^\alpha\ll\operatorname{Im}e^\alpha$ $x+iy$ $e^\alpha$ $m$ $y2^{-m}$ $x$ $x2^{-m}$

Para exponenciação de razões exatas, podemos contornar o problema:

Proposição: Dado unário , onde são racionais binários (ou números exatos de pontos fixos), podemos calcular uma aproximação de ponto flutuante de para bits de precisão relativa no mesmo tempo limite exponenciação complexa como definida acima, até fator linear. ( seja, usando o algoritmo de Brent.) $\alpha=x+iy$ $m$ $x,y$ $\re e^\alpha$ $m$ $O(M(n)\log n)$

Esboço de prova: temos . Podemos aproximar , e os números de ponto flutuante são facilmente multiplicado, o problema consiste em aproximar com erro relativo . Podemos calcular o número inteiro mais próximo de , onde é ou , onde $\re e^\alpha=e^x\cos y$ $e^x$ $\cos y$ $2^{-m}$ $k$ $2y/\pi$ $\cos y$ $\pm\cos y'$ $\pm\sin y'$ satisfaz. O problema surge quando precisamos calcular oeé muito pequeno, pois, para termosabits de precisão relativa, precisamos debits de precisão absoluta. Suponha que, ondesão números inteiros dados como entrada. Se $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'$ é pequeno, temos uma boa aproximação racional de : $\pi$ Agora,é conhecido por ter uma medida irrationality finito(a corrente é ligadaporSalikhov). Isso implica

| π - \frac{2 u}{k v} | \leq \frac{2 | y^{'} |}{k} .

$\left|\pi-\frac{2u}{kv}\right|\le\frac{2|y'|}k.$

π

$\pi$

ν

$\nu$

7.6063

$7{.}6063$

que fornece um limite superior linear no

em termos do comprimento da entrada. Podemos assim calcular

com a precisão desejada; avaliar

não é então um problema (se

é suficientemente pequena, podemos apenas ter

). QED

| y^{'} | \geq \frac{1}{2 k^{ν - 1} v^{ν}},

$|y'|\ge\frac1{2k^{\nu-1}v^\nu},$

\log | {y^{'}}^{- 1} |

$\log|{y'}^{-1}|$

y^{'}

$y'$

\sin y^{'}

$\sin y'$

y^{'}

$y'$

\sin y^{'} \approx y^{'}

$\sin y'\approx y'$

Não sei se o mesmo vale para algébrica . No argumento acima, pode-se obter um limite no do teorema de Baker , no entanto, nenhuma de suas versões que eu vi é boa o suficiente para tornar linear a precisão necessária no tamanho da entrada: em particular, os limites envolvem um polinômio (bastante desagradável) em . Isso torna o algoritmo resultante polinomial no tamanho da entrada, mas com um expoente ridículo. $\alpha$ $\log|y'|$ $\deg(f)$

Emil Jeřábek
fonte

Penso que a questão principal é que a exponenciação sobre números inteiros não é computável em poli-tempo. Portanto, uma maneira de lidar com a exponenciação sobre números reais é separar essa questão das demais: 1. encontre um número inteiro

tal que

, 2. calcule

, 3. retorne

como resposta.

k

$k$

0 \leq b / k < 1

$0 \leq b/k < 1$

r = (b / k)^{e}

$r = (b/k)^e$

(r, k, e)

$(r,k,e)$

Kaveh

Desculpe, estou perdida. O que é

e para que é

uma resposta? De qualquer forma, o objetivo de usar uma representação diferente para entrada e saída, como acima, é tornar o tempo polinomial da exponenciação de número inteiro: você pode calcular

trivialmente apenas criando

expoente de ponto flutuante e

funciona da mesma forma (o expoente é

e, em seguida, prossiga para aproximar o número limitado

k, b, e

$k,b,e$

(r, k, e)

$(r,k,e)$

2^{a}

$2^a$

a

$a$

e^{a}

$e^a$

⌊ a / \log 2 ⌋

$\lfloor a/\log 2\rfloor$

para obter a mantissa).

\exp (a - ⌊ a / \log 2 ⌋ \log 2)

$\exp(a-\lfloor a/\log 2\rfloor\log 2)$

Emil Jeřábek

Desculpe Emil, eu estava um pouco enigmático. Considere o problema em que queremos calcular

. O que eu estava tentando dizer era que o único problema que impede a computação ou de maneira eficiente é o resultado da ineficiência da exponenciação em números inteiros.

b^{e}

$b^e$

Kaveh

Sim, em certo sentido, o problema é que a exponenciação de número inteiro é ineficiente (ou melhor, o resultado é muito grande). No entanto, não entendo como sua proposta deve funcionar. Como você representa

? Se

é um

bit inteiro, em seguida, se digamos

, então

é exponencialmente pequena, portanto, que estão de volta em um quadrado. De qualquer forma, desde que você está representando efetivamente o resultado como

, este é essencialmente um base-

ponto flutuante, exceto que não é normalizado e

r

$r$

e

$e$

n

$n$

b / k \approx 1 / 2

$b/k\approx1/2$

r \approx 2^{- 2^{n}}

$r\approx 2^{-2^n}$

k^{e} r

$k^er$

k

$k$

k

$k$ pode variar, o que dificulta o cálculo dessas representações. Quais são os benefícios?

Emil Jeřábek

A função exponencial sobre números algébricos

Respostas: