Sobre a complexidade computacional do recíproco
Deixei $N$ ser um número inteiro positivo.
Eu gostaria de determinar $\mathcal{O}(\frac{1}{N})$.
Deixei $n$ denotam o número de bits em $(N)_{2}$, a representação binária de $N$.
Se a divisão longa comum for usada, estou correto em assumir que o cálculo do recíproco de $N$ será $\mathcal{O}(n)$? Meu raciocínio é este ---
No caso de divisão do inteiro $a$ pelo inteiro $b$, a complexidade de tempo Big-O associada à expansão decimal da fração $\frac{a}{b}$ é (estou presumindo), $len(a) \cdot len(b)$, Onde $len$ é o número de bits na forma binária dos inteiros $a$ e $b$, respectivamente. Portanto, para$\left(\frac{1}{N}\right)_{2} = \frac{1}{n}$, $\mathcal{O}(1/N) = len1 \cdot lenN$ = $n$.
Este raciocínio está correto?
Aliás, o $N$s que tenho em mente são muito, muito grandes. Espero que isso não importe em termos de obtenção de um grande$\mathcal{O}$ estimativa, mas por favor me avise se tiver.
Muito Obrigado.
Respostas
Assumindo "se a divisão longa comum for usada", calcular $1/N$ em representação binária longe o suficiente "para produzir a repetição exata" levará até $\mathcal O(nN)$ operações de bits.
Considere a complexidade de um único passo do algoritmo de divisão longa usual, executado que presumimos na aritmética binária. Vamos subtrair um$n$-bit operando de outro, o que significa $n$ subtrair com emprestar operações.
Em seguida, precisamos limitar o comprimento da repetição - a sequência de repetição da representação binária do recíproco $1/N$- porque isso relaciona o número de etapas de subtração exigidas pela divisão longa. Não podemos ter certeza a priori de quantas dessas etapas são necessárias, e pode-se argumentar que, nas etapas em que o bit do dividendo experimental é zero, nenhuma subtração real é necessária. Por outro lado, estamos procurando um limite superior e, além disso, verificar se zero ou um é o bit de dividendo de teste correto é uma comparação de dois$n$Quantidades de bits, então pode ser necessário realizar a subtração para saber se ela é necessária ou não.
Curiosamente o comprimento $k$da sequência de repetição é a ordem multiplicativa de$2$ módulo o maior divisor ímpar de $N$. Geralmente, seria removido qualquer fator uniforme de$N$ para começar (os zeros à direita de sua representação binária, portanto, uma quantidade conhecida) e, portanto, reduzindo ao caso $N$em si é estranho. Assumiremos assim para o resto da discussão.
Isso é frequentemente discutido no contexto de uma expansão decimal repetida aqui no Math.SE. Veja, por exemplo, esta pergunta anterior e a resposta de Ross Millikan, vinculando o comprimento da parte decimal repetida$k$ para o número inteiro positivo mínimo, de modo que $10^k \equiv 1 \bmod N$.
Por uma questão prática, embora se possa determinar separadamente esse comprimento com antecedência, pode-se simplesmente realizar a divisão longa até que um resto de um seja obtido. É onde nossa divisão$1/N$ começou, então, se chegarmos a esse ponto novamente, todos os passos se repetirão depois.
Agora quão grande pode $k$estar? Como a ordem multiplicativa de$2$ dentro $\mathbb Z/N\mathbb Z$ divide a função totiente de Euler $\varphi(N)$, isso nos dá um limite superior. Na verdade, a conjectura de Artin sobre as raízes primitivas implica que para um número infinito de valores primários de$N$, esta ordem multiplicativa $k$ será $N-1$. (Lembre-se do conhecido caso decimal de$1/7$ tendo um comprimento repetido de seis ... porque $10^6 \equiv 1 \bmod 7$.) Para obter mais informações, consulte o artigo da Wikipedia Full repetend prime .