Peut-on calculer

Je cherche un algorithme efficace pour le problème:

Entrée : l'entier positif (stocké sous forme de bits) pour un entier . $3^n$ $n \geq 0$

Sortie : Le nombre . $n$

Question : Peut-on calculer partir des bits de en temps ? $n$ $3^n$ $O(n)$

Il s'agit d'une question théorique motivée par ma réponse à une question math.SE Comment trouver une formule pour cette bijection? . Dans cette question, l'auteur a voulu trouver une bijection à partir de et les nombres naturels . J'ai proposé comme solution. Une autre réponse y affirmait "il n'y a pas de formule simple", ce qui me fait me demander à quel point (sur le plan du calcul) la solution proposée est simple.

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

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

N = {1, 2, \dots}

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

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

$2^m 3^n \mapsto 2^m(2n+1)$

Avec ma solution proposée, si nous connaissons et , nous pouvons facilement calculer (écrire les chiffres binaires de suivi de suivi de zéros). Cela prend du temps . $n$ $m$ $2^m(2n+1)$ $n$ $1$ $m$ $O(n+m)$

Trouver partir des bits de revient à trouver le bit le moins significatif (qui peut être calculé en comptant les décalages de bits à droite, en laissant en mémoire). Cela prend du temps . $m$ $2^m 3^n$ $3^n$ $O(m)$

Cependant, nous devons également trouver , ce qui pourrait être plus difficile. Il serait possible de trouver en divisant à plusieurs reprises par , mais cela semble inutile. Cela nécessite opérations de division, chacune prenant du temps , c'est donc un temps au total. [En fait, après chaque itération, le nombre de chiffres diminuera linéairement, mais cela se traduira toujours par un temps .] $n$ $n$ $3$ $n$ $O(n)$ $O(n^2)$ $O(n^2)$

Il semble que nous devrions être en mesure d'exploiter sachant que l'entrée est une puissance de . $3$

ds.algorithms time-complexity Rebecca J. Stones
la source

Quel est votre modèle exact de calculs? Quelles opérations sont autorisées en temps

? (Si nous pouvions faire de l'arithmétique avec des nombres tels que

ce serait très utile ...)

O (1)

$O(1)$

\log_{2} 3

$\log_2 3$

Yuval Filmus

Le downvoter peut-il expliquer le downvote? Cela ne semble pas du tout être une question banale. Quel est le meilleur temps de fonctionnement sous un modèle de calcul raisonnable?

Yuval Filmus

J'imagine des bandes avec des 0, des 1 et des cellules vides (avec un nombre infini de bandes). Je souhaite que les opérations de basculement d'un bit et de décalage gauche / droite s'exécutent en temps

. (Si nous avons un marqueur le 0-ème bit sur une bande infinie, alors le décalage gauche / droite est obtenu en décalant le marqueur). Contrairement à une machine Turing, je ne veux pas que cela prenne du temps pour déplacer un pointeur. Ainsi, "basculer le 0-ème bit" prend le même temps que "basculer le 124126-ème bit".

O (1)

$O(1)$

Rebecca

Cela pourrait être en quelque sorte lié à cette question

J.-E.

La borne inférieure de

évidente?

Ω (n)

$\Omega(n)$

Boris Bukh

Réponses:

L'approche évidente est:

(1) Calculez une approximation pour . Vous pouvez approcher à l' intérieur d' une erreur de l' additif 1 en comptant le nombre de bits dans la représentation binaire donnée, et à l' intérieur d' une erreur d'additif en regardant en outre au sommet $\log_2(3^n)$ $\epsilon$ bits de l'entrée. Il suffirait de choisir une valeur constante de,sorte que (après combinaison avec l'erreur dansétape (2)) Le résultat final extrémités au seinune erreur additifde correct. $O(\log\frac{1}{\epsilon})$ $\epsilon$ $1/2$

(2) Calculez une approximation pour . Je ne connais pas les algorithmes pour cela, mais je m'attends à ce qu'ils prennent un polynôme temporel dans le nombre de bits de précision dont vous avez besoin, et vous n'avez besoin que de bits de précision. $\log_2(3)$ $O(\log n)$

(3) Divisez la réponse à (1) par la réponse à (2) et arrondissez à l'entier le plus proche.

Ainsi, la première étape prend du temps linéaire (dans la plupart des modèles de calcul, mais peut-être pas pour certains sous-alimentés comme les machines de Turing à tête unique ) et les étapes restantes doivent être polylogarithmiques.

David Eppstein
la source

Je crois que le calcul de

bits de précision prend du temps

, où

est le temps de multiplier

-bit Nombres. Voir Brent - Zimmermann, loria.fr/~zimmerma/mca/pub226.html

\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$

Ryan O'Donnell

Merci pour la référence, et excuses d'être trop paresseux pour le rechercher moi-même.

David Eppstein

Pour tout entier , l'écriture de en binaire nécessite exactement bits. Une algèbre élémentaire implique que $n>0$ $3^n$ $L = \lceil \log_2(3^n)+1\rceil$ Pour toute longueur de bit, il y a au plus un entier dans cette plage. Ainsi, étant donné une puissance entière dequi estbitslong, l'exposant doit être le nombre entier

\frac{L - 2}{{Journal}_{2} 3} \leq n \leq \frac{L - 1}{{Journal}_{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}{{Journal}_{2} 3} ⌋ .

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

Jeffε
la source

$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$

$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)$ $n \bmod 4$ $5$ $n \bmod \varphi(5^{k-1})$ $3^n \bmod 5^k$ $5$ $n \bmod \varphi(5^k)$

$k$ $n$

$O(n)$ $k=O(n)$ $O(1)$ $O(n)$

DW
la source