Computando o número de bits de uma grande potência de número inteiro

Dado dois inteiros e n na representação binária, qual é a complexidade de calcular o tamanho de bit de x n ?$x$$n$$x^n$

Uma maneira de fazer isso é calcular calculando uma aproximação do log 2 ( x ) com precisão suficiente. Parece que o cálculo do log 2 ( x ) com k bits de precisão pode ser feito em O ( M ( k ) log k ) em que M $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor n\log_2(x)\rfloor$$\log_2(x)$$\log_2(x)$$k$$O(M(k)\log k)$ é o tempo necessário para calcular o produto de dois números inteiros de comprimento k . Isso gera um algoritmo (não especialmente simples) de complexidade, aproximadamente O ( s log 2 s ) se s é um limite no tamanho de bits de x e n (se eu nãocometernenhum erro).$M(k)$$k$$O(s\log^2 s)$$s$$x$$n$

Podemos vencer onde s é o tamanho de x e n (no caso em que eles têm tamanhos comparáveis)? Existe um algoritmo simples para obter essa complexidade ou melhor?$O(s\log^2(s))$$s$$x$$n$

Nota: Estou interessado na complexidade de um modelo teórico como as máquinas de Turing.

[editar] Como sugerido, edito minha resposta para fornecer mais detalhes.

A resposta para minha segunda pergunta é não :

Proposição. O cálculo do até a precisão k é pelo menos tão difícil quanto o tamanho de bit de x 2 k .$\log(x)$$k$$x^{2^k}$

Prova. Let denota o tamanho do bit de um número inteiro y . Primeiro observe que, para um número inteiro não negativo y , o tamanho do bit de y é 1 + ⌊ log y ⌋ .$|y|$$y$$y$$y$$1+\lfloor \log y\rfloor$

Assim, . Agora 2 k log ( x ) é log ( x ) deslocado k posições para a esquerda. Assim, pode-se calcular o log ( x ) com precisão k subtraindo 1 para o tamanho de bit de x 2 k e deslocando as posições k do resultado para a direita.$\left|x^{2^k}\right| = 1+\lfloor 2^k\log x\rfloor$$2^k\log(x)$$\log(x)$$k$$\log(x)$$k$$1$$x^{2^k}$$k$