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

10

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

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 1+registro2(xn)=1 1+nregistro2(x)registro2(x)registro2(x)kO(M(k)registrok) é 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)kO(sregistro2s)sxn

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(sregistro2(s))sxn

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

Bruno
fonte
sugiro migrar / "promover" isso para a Ciência da Computação Teórica
vzn 26/11/14
@vzn: Eu não acho que isso é útil ...
de Bruno
Por que não? esta pergunta me faz lembrar de ataques algorítmicos sobre Dysons conjectura por exemplo abrangidos pela RJLipton em 1 , 2
vzn
Simplesmente porque encontrei uma resposta para minha pergunta, então não há necessidade de perguntar em outro lugar em minha mente.
Bruno

Respostas:

1

[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)kx2k

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|yyy1+logy

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.|x2k|=1+2klogx2klog(x)log(x)klog(x)k1x2kk

Bruno
fonte
11
Por que o número de bits em permite calcular log x em k bits de precisão? Sua redução realmente funciona? E se o caso especial em que n = 2 k fosse muito mais fácil / mais difícil do que todos os outros valores possíveis de n (não potências de dois)? Você tem uma maneira de descartar essa possibilidade? x2kregistroxkn=2kn
DW
@ DW: Volto a esta pergunta, após o comentário do vzn. Minha prova é a seguinte: O número de bits de um número inteiro é 1 + log y . Assim, o número de bits em x 2 k é 1 + 2 k log x . Além disso, 2 k log x é o mesmo que log x, mas mudou as posições k para a esquerda. Assim, 2 k log x fornece (pelo menos) os k primeiros bits dey1+registroyx2k1 1+2kregistrox2kregistroxregistroxk2kregistroxk . Portanto, se você pode calcular o número de bits de x 2 k , subtraindo 1 ao resultado, obtém os primeiros k bits do log x . Isso faz sentido? registroxx2k1 1kregistrox
de Bruno
Sim, isso faz mais sentido para mim! Especialmente porque você está apenas tentando mostrar dureza. Posso encorajá-lo a atualizar sua resposta com esta explicação mais detalhada? Obrigado por voltar a isso e documentar a resposta à sua própria pergunta.
DW