Multiplication de grands nombres

Question

En analysant des algorithmes, je vois que nous supposons généralement une multiplication pour prendre une seule instruction d'ordinateur. Mais cette hypothèse n'est pas pertinente lorsque la taille du nombre (en termes de nombre de bits). Dans la forme la plus basique de la multiplication, multiplier deux nombres de n bits est habituellement O (n^2). Dans ce contexte, quelle peut être la complexité (en termes d'opérations de bits) pour calculer x^n (x élevé à la puissance de n)?

Avec l'approche expliqué, la complexité me semble être exponentielle n (mais pas sûr du chiffre exact)

Answer 1

La complexité du calcul de x^n dépend bien sûr de l'algorithme utilisé pour calculer la puissance et la multiplication. Si vous calculez la puissance par Exponentiation en quadrature, vous devez multiplier O (log n). À chaque étape, vous devez soit mettre un chiffre carré, soit multiplier deux nombres et mettre un carré sur l'un des deux.

Si x a d(x) chiffres, le x^n a Θ (n * d (x)) chiffres, dans la dernière étape, on place, un certain nombre d'environ n/2*d(x) chiffres (et, éventuellement, de multiplier ce nombre avec une plus petite) et le l'algorithme est alors terminé en multipliant le carré répété x^(2^k), si 2^k <= n < 2^(k+1), avec l'accumulateur.

Soit S(m) le coût de mise au carré un nombre m à chiffres (peut ou ne peut pas être le même que le coût M(m) de la multiplication de deux nombres m arbitraires à chiffres). Les carrés doivent alors approximativement

S(2^(k-1)*d(x)) + S(2^(k-2)*d(x)) + S(2^(k-3)*d(x)) + ... 

travail. Depuis S(m) >= m, c'est-à-dire entre S(2^(k-1)*d(x)) et 2*S(2^(k-1)*d(x)). Donc le travail pour les équarrissages est dominé par la dernière étape. Pour la multiplication d'un x^(2^s) avec l'accumulateur, c'est la même chose, la multiplication finale domine le travail. L'accumulateur final peut être presque aussi grande que la place répétée, de sorte que le coût total de l'éducation x à la n puissance -ème par élévation au carré est répété

Θ(M(2^k*d(x)), 

qui est Θ(M(n*d(x))). Avec la multiplication naïve - M(m) = O(m^2) - vous obtenez alors un coût total de O(n^2*d(x)^2). En utilisant un algorithme de multiplication plus avancé (Karatsuba, Toom-Cook, Schönhage-Strassen, ...), vous obtenez une complexité beaucoup plus faible, jusqu'à un peu plus de O(n*d(x)*log (n*d(x)) * log log (n*d(x))).

Lors du calcul de la puissance en multipliant de façon itérative avec x, en n étapes, nous M(m,k) représentent le coût de la multiplication d'un nombre m à chiffres d'un numéro k à chiffres. Étant donné que l'un des facteurs est toujours x, le coût total est

M(d(x),d(x)) + M(d(x),2*d(x)) + M(d(x),3*d(x)) + ... + M(d(x),(n-1)*d(x)) 

Avec l'algorithme de schoolbook avec le coût M(m,k) = m*k, cela résume à n*(n-1)/2*d(x)^2, de sorte que le coût total est à nouveau Θ(n^2*d(x)^2). Mais les facteurs constants sont plus grands que pour l'exponentiation par équarrissage répété.

Lorsque vous multipliez le nombre de longueurs très différentes, comme cela arrive ici après quelques itérations, vous ne pouvez pas - pour autant que je sache - réduire le coût M(m,k) bien au-dessous Θ(m*k) - si m < k, afficher les numéros en tant que 1 chiffre nombre et un r -digit nombre (r*m <= k < (r+1)*m) dans la base b^m, vous pouvez réduire le coût de multiplier "chiffres" en utilisant les meilleurs algorithmes si m est assez grand, mais vous ne pouvez pas réduire le facteur r. Donc, cet algorithme a alors une complexité de O(n^2*M(d(x))), le facteur n^2 ne peut pas être éliminé.

Answer 2

Wikipedia a une bonne vue d'ensemble des temps de complexité pour les différents algorithmes de multiplication. Pour répondre à votre question, en supposant la méthode naïve du livre scolaire de multiplier deux nombres à m chiffres (qui a une complexité de O (m^2) et la méthode naïve d'élever à une puissance en multipliant un nombre par lui-même n fois, vous avez n multiplications, donc une complexité de O (n * m^2) ou simplement O (nm^2)

Answer 3

n^coûts k:

O((log(n))^k) 

log (n) - bIT- représentation de n

^k - parce que l'algorithme simple pour multiplier deux nombre de n chiffres s coûts O (n^2)