Podemos calcular

11

Estou procurando um algoritmo eficiente para o problema:

Entrada : O número inteiro positivo 3n (armazenado como bits) para algum número inteiro n0 .

Saída : O número n .

Pergunta : Podemos calcular n partir dos bits de 3n em O(n) tempo?


Esta é uma pergunta teórica motivada pela minha resposta a uma pergunta math.SE Como encontrar uma fórmula para esta bijeção? . Nesta questão, o autor queria encontrar uma bijeção de

{2n3m:n0 and m0}
e os números naturais N={1,2,} . Propus
2m3n2m(2n+1)
como uma solução. Outra resposta lá afirmou "não existe uma fórmula simples", o que me faz pensar em quão simples (computacionalmente) minha solução proposta é.

Com a minha solução proposta, se sabemos que e m , podemos facilmente calcular 2 m ( 2 n + 1 ) (escrever os dígitos binários de n seguido por 1 seguido de m zeros). Isso leva tempo O ( n + m ) .nm2m(2n+1)n1mO(n+m)

Encontrar partir dos bits de 2 m 3 n equivale a encontrar o bit menos significativo (que pode ser calculado contando as mudanças de bits corretas, deixando 3 n na memória). Isso leva tempo O ( m ) .m2m3n3nO(m)

No entanto, também precisamos encontrar , o que pode ser mais difícil. Seria possível encontrar n dividindo repetidamente por 3 , mas isso parece um desperdício. Requer n operações de divisão, cada uma das quais levará tempo O ( n ) , portanto, esse é o tempo O ( n 2 ) no total. [Na verdade, após cada iteração, o número de dígitos diminui linearmente, mas isso ainda resulta em tempo de O ( n 2 ) .]nn3nO(n)O(n2)O(n2)

Parece que deveríamos ser capazes de explorar sabendo que a entrada é uma potência de .3

Rebecca J. Stones
fonte
2
Qual é o seu modelo exato de computação? Quais operações são permitidas no tempo ? (Se pudéssemos fazer aritmética com números, como log 2 3 seria bastante útil ...)O(1)log23
Yuval Filmus
3
O voto negativo pode explicar o voto negativo? Não parece uma pergunta trivial. Qual é o melhor tempo de execução em algum modelo de computação razoável?
Yuval Filmus
1
Estou imaginando fitas com zeros, zeros e células vazias (com um número infinito de fitas). Eu quero que operações de alternância e deslocamento de esquerda / direita sejam executadas no tempo . (Se tivermos um marcador de 0-th bit em uma fita infinita, o deslocamento para a esquerda / direita é alcançado deslocando o marcador). Ao contrário de uma máquina de Turing, não quero que demore algum tempo para mover um ponteiro. Portanto, "alternar o bit 0-th" leva o mesmo tempo que "alternar o bit 124126-th". O(1)
Rebecca J. Pedras
Pode estar de alguma forma relacionado a esta questão
J.-E.
O limite inferior de óbvio? Ω(n)
Boris Bukh 13/09

Respostas:

9

A abordagem óbvia é:

(1) Calcule uma aproximação para o . Você pode aproximá-lo para dentro de um erro aditivo de 1 contando o número de bits na representação binária fornecida e para dentro de um erro aditivo de ϵ olhando adicionalmente para o O superior ( log 1log2(3n)ϵbits de entrada. Ele deve ser suficiente para escolher um valor constante deε, de modo que (após combinação com o erro no passo (2)) das extremidades finais de resultados acima dentro de um erro aditivo de1/2da correcta.O(log1ϵ)ϵ1/2

(2) Calcule uma aproximação ao . Não estou familiarizado com os algoritmos para isso, mas espero que eles levem tempo polinomial no número de bits de precisão que você precisa, e você só precisa de O ( log n ) bits de precisão.log2(3)O(logn)

(3) Divida a resposta em (1) pela resposta em (2) e arredonde para o número inteiro mais próximo.

Portanto, o primeiro passo leva tempo linear (na maioria dos modelos de computação, embora talvez não seja o caso de alguns com pouca potência, como as máquinas de Turing de cabeça única ) e os demais passos devem ser polilogarítmicos.

David Eppstein
fonte
3
log2(3)tO(M(t)logt)M(t)O(tlogt2logt)t
Obrigado pela referência e desculpas por ser muito preguiçoso para procurar por mim mesmo.
David Eppstein
9

n>03nL=log2(3n)+1

L2log23nL1log23.
L13L
n=L1log23.
Jeffε
fonte
4

k3n3nmod10k3nmod5k35k3φ(5k)=5k1×4

Portanto, usando o log discreto e o levantamento de Hensel, acho que você deve poder calcular partir dos dígitos baixos de muita eficiência. Em outras palavras, você começa calculando partir do dígito baixo de , levando o log discreto de para a base , módulo ; isso revela o e pode ser feito no tempo . Então, você encontra o log discreto de para a base , módulo ; isso revela o e pode ser feito emnmodφ(5k)k3nnmod43n3nmod535nmod4O(1)3nmod25e25nmod20O(1) time (aproveitando o conhecimento do , existem apenas possibilidades que você precisa tentar). Iterar. Em cada etapa, você usa o conhecimento de para ajudá-lo a calcular com eficiência o log discreto de , aproveitando o fato de que existem apenas valores possíveis para .nmod45nmodφ(5k1)3nmod5k5nmodφ(5k)

Agora apenas deixe ser grande o suficiente, e isso revela .kn

Você precisará descobrir se o tempo de execução é , mas me parece que pode ser. Suspeito que seja suficiente deixar e suspeito que você possa fazer cada iteração em tempo, para um total de tempo.O(n)k=O(n)O(1)O(n)

DW
fonte