Sur la complexité informatique de la réciprocité
Laisser $N$ être un entier positif.
Je voudrais déterminer $\mathcal{O}(\frac{1}{N})$.
Laisser $n$ dénotent le nombre de bits dans $(N)_{2}$, la représentation binaire de $N$.
Si la division longue ordinaire est utilisée, ai-je raison de supposer que le calcul de la réciproque de $N$ sera $\mathcal{O}(n)$? Mon raisonnement est le suivant ---
Dans le cas de la division de l'entier $a$ par l'entier $b$, la complexité temporelle Big-O associée à l'expansion décimale de la fraction $\frac{a}{b}$ est (je présume), $len(a) \cdot len(b)$, où $len$ est le nombre de bits sous forme binaire des entiers $a$ et $b$, respectivement. Par conséquent, pour$\left(\frac{1}{N}\right)_{2} = \frac{1}{n}$, $\mathcal{O}(1/N) = len1 \cdot lenN$ = $n$.
Ce raisonnement est-il correct?
Incidemment, le $N$s je pense sont très, très grands. Je m'attends à ce que cela n'ait pas d'importance en termes d'obtention d'un grand$\mathcal{O}$ estimation, mais s'il vous plaît aviser moi si c'est le cas.
Merci beaucoup.
Réponses
En supposant "si une division longue ordinaire est utilisée", calculer $1/N$ dans la représentation binaire assez loin "pour produire la répétition exacte" prendra jusqu'à $\mathcal O(nN)$ opérations sur les bits.
Considérez la complexité d'une seule étape de l'algorithme de division longue habituel, réalisé que nous supposons en arithmétique binaire. Nous en soustraire un$n$-bits opérande d'un autre, ce qui signifie $n$ opérations de soustraction avec emprunt.
Nous devons ensuite limiter la longueur de la répétition - la séquence répétitive de la représentation binaire de la réciproque $1/N$- parce que cela concerne le nombre d'étapes de soustraction requises par la division longue. Nous ne pouvons pas être sûrs a priori du nombre de ces étapes nécessaires, et on pourrait soutenir que dans les étapes où le bit de dividende d'essai est nul, aucune soustraction réelle n'est nécessaire. D'autre part, nous recherchons une borne supérieure, et en outre, vérifier si zéro ou un est le bon bit de dividende d'essai est une comparaison de deux$n$-bits, on peut donc avoir besoin d'effectuer la soustraction pour savoir si elle est nécessaire ou non.
Fait intéressant, la longueur $k$de la séquence répétitive est l' ordre multiplicatif de$2$ modulo le plus grand diviseur impair de $N$. On aurait généralement supprimé tout facteur pair de$N$ pour commencer (les zéros de fin de sa représentation binaire, donc une quantité connue) et donc réduire au cas $N$lui-même est étrange. Nous le supposerons pour le reste de la discussion.
Ceci est souvent discuté dans le contexte d'une expansion décimale répétée ici sur Math.SE. Voir par exemple cette question précédente et la réponse de Ross Millikan, liant la longueur de la partie décimale répétée$k$ à l'entier positif minimal tel que $10^k \equiv 1 \bmod N$.
En pratique, bien que l'on puisse déterminer séparément cette longueur à l'avance, on peut simplement effectuer la division longue jusqu'à ce qu'un reste de un soit obtenu. C'est là que notre division$1/N$ commencé, donc si nous atteignons à nouveau ce point, toutes les étapes se répéteront par la suite.
Maintenant quelle taille peut $k$être? Comme l'ordre multiplicatif de$2$ dans $\mathbb Z/N\mathbb Z$ divise la fonction totient d'Euler $\varphi(N)$, cela nous donne une borne supérieure. En fait, la conjecture d'Artin sur les racines primitives implique que pour une infinité de valeurs premières de$N$, cet ordre multiplicatif $k$ sera $N-1$. (Rappelez-vous le cas décimal bien connu de$1/7$ avoir une longueur de répétition six ... parce que $10^6 \equiv 1 \bmod 7$.) Pour de plus amples informations , voir l'article de Wikipedia plein repetend premier .