Sulla complessità computazionale del reciproco

Sep 21 2020

Permettere $N$ essere un numero intero positivo.

Vorrei determinare $\mathcal{O}(\frac{1}{N})$.

Permettere $n$ denota il numero di bit in $(N)_{2}$, la rappresentazione binaria di $N$.

Se viene utilizzata la divisione lunga ordinaria, ho ragione nel presumere che il calcolo del reciproco di $N$ sarà $\mathcal{O}(n)$? Il mio ragionamento è questo ---

In caso di divisione dell'intero $a$ dall'intero $b$, la complessità temporale Big-O ha associato l'espansione decimale della frazione $\frac{a}{b}$ è (presumo), $len(a) \cdot len(b)$, dove $len$ è il numero di bit nella forma binaria degli interi $a$ e $b$, rispettivamente. Quindi, per$\left(\frac{1}{N}\right)_{2} = \frac{1}{n}$, $\mathcal{O}(1/N) = len1 \cdot lenN$ = $n$.

Questo ragionamento è corretto?

Per inciso, il $N$Ho in mente sono molto, molto grandi. Mi aspetto che questo non abbia importanza in termini di ottenere un grande$\mathcal{O}$ stima, ma per favore avvisami se lo fa.

Grazie molto.

Risposte

3 hardmath Sep 24 2020 at 04:41

Supponendo "se viene utilizzata la divisione lunga ordinaria", il calcolo $1/N$ nella rappresentazione binaria abbastanza lontano "per produrre l'esatta ripetizione" richiederà fino a $\mathcal O(nN)$ operazioni di bit.

Si consideri la complessità di un singolo passaggio del solito algoritmo di divisione lunga, svolto si presume in aritmetica binaria. Ne sottraeremo uno$n$-bit operando da un altro, il che significa $n$ operazioni di sottrazione con prestito.

Dobbiamo quindi limitare la lunghezza della ripetizione, la sequenza ripetuta della rappresentazione binaria del reciproco $1/N$- perché si riferisce al numero di passaggi di sottrazione richiesti dalla divisione lunga. Non possiamo essere sicuri a priori di quanti passaggi di questo tipo siano necessari, e si potrebbe sostenere che nei passaggi in cui il bit del dividendo di prova è zero, non è necessaria alcuna sottrazione effettiva. D'altra parte stiamo cercando un limite superiore, e inoltre verificare se zero o uno è giusto il bit del dividendo di prova è un confronto di due$n$quantità di bit, quindi potrebbe essere necessario eseguire la sottrazione per sapere se è necessaria o meno.

È interessante notare che la lunghezza $k$della sequenza ripetuta è l' ordine moltiplicativo di$2$ modulo il più grande divisore dispari di $N$. Generalmente si sarebbe rimosso qualsiasi fattore pari di$N$ per cominciare (gli zeri finali della sua rappresentazione binaria, quindi una quantità nota) e quindi ridurre al caso $N$in sé è strano. Assumeremo così per il resto della discussione.

Questo è spesso discusso nel contesto di un'espansione decimale ripetuta qui su Math.SE. Vedi ad esempio questa domanda precedente e la risposta di Ross Millikan, legando la lunghezza della parte decimale ripetuta$k$ all'intero minimo positivo tale che $10^k \equiv 1 \bmod N$.

In pratica, sebbene si possa determinare separatamente quella lunghezza in anticipo, si può semplicemente eseguire la divisione lunga finché non si ottiene il resto di una. Ecco dove la nostra divisione$1/N$ iniziato, quindi se raggiungiamo di nuovo quel punto, tutti i passaggi verranno ripetuti in seguito.

Ora quanto grande può $k$essere? Come l'ordine moltiplicativo di$2$ nel $\mathbb Z/N\mathbb Z$ divide la funzione totiente di Eulero $\varphi(N)$, che ci dà un limite superiore. Infatti la congettura di Artin sulle radici primitive implica che per infiniti valori primi di$N$, questo ordine moltiplicativo $k$ sarà $N-1$. (Ricorda il noto caso decimale di$1/7$ avere una durata di ripetizione sei ... perché $10^6 \equiv 1 \bmod 7$.) Per ulteriori informazioni, vedere l'articolo di Wikipedia Full repetend prime .