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

10

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

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).log 2 ( x ) log 2 ( x ) k O ( M ( k ) log k ) M ( k ) k O ( s log 2 s ) s x n1+Journal2(Xn)=1+nJournal2(X)Journal2(X)Journal2(X)kO(M(k)Journalk)M(k)kO(sJournal2s)sXn

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?s x nO(sJournal2(s))sXn

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

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:

1

[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 .k x 2 klog(x)kx2k

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 1 + log y |y|yyy1+logy

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. 2 k log(x)log(x)klog(x)k1 x 2 k k|x2k|=1+2klogx2klog(x)Journal(X)kJournal(X)k1X2kk

Bruno
la source
1
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é? log x k n = 2 k nx2klogxkn=2kn
DW
@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 de1 + log y x 2 k 1 + 2 k log x 2 k log x log x k 2 k log x k log x x 2 k 1 k log xy1+logyx2k1+2klogx2klogxlogxk2klogxklogxx2k1klogX. 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.
DW