Calcul du nombre de bits d'une grande puissance d'entier

Étant donné deux entiers et en représentation binaire, quelle est la complexité du calcul de la taille en bits de ? $x$ $n$ $x^n$

Une façon de procéder consiste à calculer en calculant une approximation de avec une précision suffisante. Il apparaît que le calcul avec bits de précisions peut se faire dans où est le temps nécessaire pour calculer le produit de deux entiers de longueur . Cela donne un algorithme (pas spécialement simple) de complexité approximativement si est une limite sur la taille des bits de et (si je n'ai fait aucune erreur). $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)$ $M(k)$ $k$ $O(s\log^2 s)$ $s$ $x$ $n$

Peut-on battre où est la taille de et (dans le cas où ils ont des tailles comparables)? Existe-t-il un algorithme simple pour obtenir cette complexité ou mieux? $O(s\log^2(s))$ $s$ $x$ $n$

Remarque: Je m'intéresse à la complexité d'un modèle théorique tel que les machines de Turing.

complexity-theory time-complexity binary-arithmetic Bruno
la source

suggérer de migrer / "promouvoir" cela vers l' informatique théorique

vzn

@vzn: Je ne pense pas que ce soit utile ...

Bruno

pourquoi pas? cette question me rappelle les attaques algorithmiques sur la conjecture Dysons, par exemple, comme couvert par RJLipton dans 1 , 2

vzn

Tout simplement parce que j'ai trouvé une réponse à ma question, donc pas besoin de la poser ailleurs dans mon esprit.

Bruno

Réponses:

[modifier] Comme suggéré, je modifie ma réponse pour donner plus de détails.

La réponse à ma deuxième question est non :

Proposition. Calculer jusqu'à la précision est au moins aussi difficile que calculer la taille en bits de . $\log(x)$ $k$ $x^{2^k}$

Preuve. Soitdésigne la taille en bits d'un entier . Remarquez tout d'abord que pour un entier non négatif , la taille en bits de est . $|y|$ $y$ $y$ $y$ $1+\lfloor \log y\rfloor$

Ainsi, . Maintenant est positions décalées vers la gauche. Ainsi, on peut calculer à la précision en soustrayant simplement à la taille de bit de et en décalant les positions résultantes vers la droite. $\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$

Bruno
la source

Pourquoi le nombre de bits dans vous permet-il de calculer à bits de précision? Votre réduction fonctionne-t-elle réellement? Et si le cas spécial où était beaucoup plus facile / difficile que toutes les autres valeurs possibles de (non-puissances-de-deux)? Avez-vous un moyen d'exclure cette possibilité?

x^{2^{k}}

$x^{2^k}$

\log x

$\log x$

k

$k$

n = 2^{k}

$n=2^k$

n

$n$

@DW: Je reviens à cette question, après le commentaire de vzn. Ma preuve est la suivante: Le nombre de bits d'un entier est . Ainsi, le nombre de bits dans est . De plus, est identique à mais décalé de positions vers la gauche. Ainsi, vous donne (au moins) les premiers bits de . Ainsi, si vous pouvez calculer le nombre de bits de , en soustrayant au résultat, vous obtenez les premiers bits de

y

$y$

1 + ⌊ \log y ⌋

$1+\lfloor\log y\rfloor$

x^{2^{k}}

$x^{2^k}$

1 + ⌊ 2^{k} \log x ⌋

$1+\lfloor 2^k\log x\rfloor$

2^{k} \log x

$2^k\log x$

\log x

$\log x$

k

$k$

⌊ 2^{k} \log x ⌋

$\lfloor 2^k\log x\rfloor$

k

$k$

\log x

$\log x$

x^{2^{k}}

$x^{2^k}$

1

$1$

k

$k$

\log x

$\log x$ . Est-ce que ça a du sens?

Bruno

Oui, cela a plus de sens pour moi! D'autant plus que vous essayez juste de montrer la dureté. Puis-je vous encourager à mettre à jour votre réponse avec cette explication plus détaillée? Merci d'être revenu à ce sujet et d'avoir documenté la réponse à votre propre question.