Podemos calcular

Estou procurando um algoritmo eficiente para o problema:

Entrada : O número inteiro positivo $3^n$ (armazenado como bits) para algum número inteiro $n \geq 0$ .

Saída : O número $n$ .

Pergunta : Podemos calcular $n$ partir dos bits de $3^n$ 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

{2^{n} 3^{m} : n \geq 0 and m \geq 0}

$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$ e os números naturais

N = {1, 2, \dots}

$\mathbb{N}=\{1,2,\ldots\}$ . Propus

2^{m} 3^{n} \mapsto 2^{m} (2 n + 1)

$2^m 3^n \mapsto 2^m(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 , podemos facilmente calcular (escrever os dígitos binários de seguido por seguido de zeros). Isso leva tempo . $n$ $m$ $2^m(2n+1)$ $n$ $1$ $m$ $O(n+m)$

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

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

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

ds.algorithms time-complexity Rebecca J. Stones
fonte

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

seria bastante útil ...)

O (1)

$O(1)$

\log_{2} 3

$\log_2 3$

Yuval Filmus

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

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)

$O(1)$

Rebecca J. Pedras

Pode estar de alguma forma relacionado a esta questão

J.-E.

O limite inferior de

óbvio?

Ω (n)

$\Omega(n)$

Boris Bukh 13/09

Respostas:

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 superior $\log_2(3^n)$ $\epsilon$ 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 deda correcta. $O(\log\frac{1}{\epsilon})$ $\epsilon$ $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 bits de precisão. $\log_2(3)$ $O(\log n)$

(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

\log_{2} (3)

$\log_2(3)$

t

$t$

O (M (t) \log t)

$O(M(t) \log t)$

M (t) \leq O (t \log t 2^{\log^{*} t})

$M(t) \leq O(t \log t 2^{\log^* t})$

t

$t$

Obrigado pela referência e desculpas por ser muito preguiçoso para procurar por mim mesmo.

David Eppstein

$n>0$ $3^n$ $L = \lceil \log_2(3^n)+1\rceil$

\frac{L - 2}{\log_{2} 3} \leq n \leq \frac{L - 1}{\log_{2} 3} .

$\frac{L-2}{\log_2 3} \le n \le \frac{L-1}{\log_2 3}.$

L \geq 1

$L\ge 1$

3

$3$

L

$L$

n = ⌊ \frac{L - 1}{\log_{2} 3} ⌋ .

$n = \left\lfloor\frac{L-1}{\log_2 3}\right\rfloor.$

Jeffε
fonte

$k$ $3^n$ $3^n \bmod 10^k$ $3^n \bmod 5^k$ $3$ $5^k$ $3$ $\varphi(5^k)=5^{k-1} \times 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 em $n \bmod \varphi(5^k)$ $k$ $3^n$ $n \bmod 4$ $3^n$ $3^n \bmod 5$ $3$ $5$ $n \bmod 4$ $O(1)$ $3^n \bmod 25$ $e$ $25$ $n \bmod 20$ $O(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 . $n \bmod 4$ $5$ $n \bmod \varphi(5^{k-1})$ $3^n \bmod 5^k$ $5$ $n \bmod \varphi(5^k)$

Agora apenas deixe ser grande o suficiente, e isso revela . $k$ $n$

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