Criterios de tirar a raiz quadrada

Na teoria dos números , a raiz quadrada inteira (isqrt) de um inteiro positivo n é o inteiro positivo m, que é o maior inteiro menor ou igual à raiz quadrada de n ,

Índice Show

Algoritmo usando o método de Newton
Usando apenas divisão inteira
Domínio de computação
Critério de parada
Exemplo de implementação em C
Algoritmo dígito a dígito
Usando operações bit a bit
Em linguagens de programação
Veja também
Referências
links externos

isqrt ( n ) = ⌊ n ⌋ . {\ displaystyle {\ mbox {isqrt}} (n) = \ lfloor {\ sqrt {n}} \ rfloor.}

Por exemplo, porque e . $isqrt ( 27 ) = 5 {\ displaystyle {\ mbox {isqrt}} (27) = 5}$ $5 ⋅ 5 = 25 ≤ 27 {\ displaystyle 5 \ cdot 5 = 25 \ leq 27}$ $6 ⋅ 6 = 36 > 27 {\ displaystyle 6 \ cdot 6 = 36> 27}$

Algoritmo usando o método de Newton

Uma maneira de calcular e usar o método de Newton para encontrar uma solução para a equação , fornecendo a fórmula iterativa $n {\ displaystyle {\ sqrt {n}}}$ $isqrt ( n ) {\ displaystyle {\ mbox {isqrt}} (n)}$ $x 2 - n = 0 {\ displaystyle x ^ {2} -n = 0}$

x k + 1 = 1 2 ( x k + n x k ) , k ≥ 0 , x 0 > 0 {\displaystyle {x}_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.}

A sequência converge quadraticamente para as . Pode-se comprovar que se for escolhido como palpite inicial, pode-se parar assim que ${ x k } {\displaystyle \{x_{k}\}}$ $n {\displaystyle {\sqrt {n}}}$ $k → ∞ {\displaystyle k\to \infty }$ $x 0 = n {\displaystyle x_{0}=n}$

| x k + 1 − x k | < 1 {\displaystyle |x_{k+1}-x_{k}|<1}

para garantir que $⌊ x k + 1 ⌋ = ⌊ n ⌋ . {\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor .}$

Usando apenas divisão inteira

Para calcular para inteiros muito grandes n , pode-se usar o quociente de divisão euclidiana para ambas as operações de divisão. Isso tem a vantagem de usar apenas números inteiros para cada valor intermediário, tornando desnecessário o uso de representações de ponto flutuante de números grandes. É equivalente a usar a fórmula iterativa $⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor }$

x k + 1 = ⌊ 1 2 ( x k + ⌊ n x k ⌋ ) ⌋ , k ≥ 0 , x 0 > 0 , x 0 ∈ Z . {\displaystyle {x}_{k+1}=\left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {Z} .}

Usando o fato de que

⌊ 1 2 ( x k + ⌊ n x k ⌋ ) ⌋ = ⌊ 1 2 ( x k + n x k ) ⌋ , {\displaystyle \left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor =\left\lfloor {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right)\right\rfloor ,}

pode-se mostrar que isso atingirá um número finito de iterações. $⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor }$

No entanto, não é necessariamente um ponto fixo da fórmula iterativa acima. Na verdade, pode-se mostrar que é um ponto fixo se e somente se não for um quadrado perfeito. Se for um quadrado perfeito, a sequência termina em um ciclo de período dois entre e em vez de convergir. $⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor }$ $⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor }$ $n + 1 {\displaystyle n+1}$ $n + 1 {\displaystyle n+1}$ $⌊ n ⌋ {\displaystyle \lfloor {\sqrt {n}}\rfloor }$ $⌊ n ⌋ + 1 {\displaystyle \lfloor {\sqrt {n}}\rfloor +1}$

Domínio de computação

Embora seja irracional para muitos , a sequência contém apenas termos racionais quando é racional. Assim, com este método não é necessário sair do campo dos números racionais para fazer o cálculo , fato que apresenta algumas vantagens teóricas. $n {\displaystyle {\sqrt {n}}}$ $n {\displaystyle n}$ ${ x k } {\displaystyle \{x_{k}\}}$ $x 0 {\displaystyle x_{0}}$ $isqrt ( n ) {\displaystyle {\mbox{isqrt}}(n)}$

Critério de parada

Pode-se provar que é o maior número possível para o qual o critério de parada $c = 1 {\displaystyle c=1}$

| x k + 1 − x k | < c {\displaystyle |x_{k+1}-x_{k}|<c}

garante no algoritmo acima. $⌊ x k + 1 ⌋ = ⌊ n ⌋ {\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor }$

Em implementações que usam formatos de número que não podem representar todos os números racionais exatamente (por exemplo, ponto flutuante), uma constante de parada menor que um deve ser usada para proteger contra erros de arredondamento.

Exemplo de implementação em C

// Raiz quadrada de inteiro sem sinal longo int_sqrt ( s longo sem sinal ) { longo sem sinal x0 = s >> 1 ; // estimativa inicial // Verificação de sanidade if ( x0 ) { unsigned long x1 = ( x0 + s / x0 ) >> 1 ; // Atualizarwhile ( x1 < x0 ) // Isso também verifica o ciclo { x0 = x1 ; x1 = ( x0 + s / x0 ) >> 1 ; }return x0 ; } else { return s ; } }

Algoritmo dígito a dígito

O algoritmo de caneta e papel tradicional para calcular a raiz quadrada baseia-se no trabalho dos dígitos mais altos para os mais baixos e, à medida que cada novo dígito, escolhe o maior que ainda produzirá um quadrado . Se parar após a posição de um, o resultado calculado será a raiz quadrada inteira. $n {\displaystyle {\sqrt {n}}}$ $≤ n {\displaystyle \leq n}$

Usando operações bit a bit

Se estiver trabalhando na base 2 , a escolha do dígito é simplificada para aquele entre 0 (o "candidato pequeno") e 1 (o "candidato grande"), e as manipulações dos dígitos podem ser expressas em termos de operações de deslocamento binário. Com *sendo multiplicação, <<sendo desvio à esquerda, e >>sendo deslocamento para a direita lógico, uma recursiva algoritmo para encontrar a raiz quadrada inteiro de qualquer número natural é:

def integer_sqrt ( n : int ) -> int : assert n > = 0 , "sqrt funciona apenas para entradas não negativas" se n < 2 : retornar n # Recursiva chamada: small_cand = integer_sqrt ( n >> 2 ) << 1 large_cand = small_cand + 1 se large_cand * large_cand > n : retorno small_cand outra coisa : retorno large_cand# equivalentemente: def integer_sqrt_iter ( n : int ) -> int : assert n > = 0 , "sqrt funciona apenas para entradas não negativas" se n < 2 : retornar n # Encontre a quantidade de deslocamento. Veja também [[encontrar primeiro conjunto]], # shift = ceil (log2 (n) * 0,5) * 2 = ceil (ffs (n) * 0,5) * 2 shift = 2 enquanto ( n >> shift ) ! = 0 : shift + = 2 # Desenrole o loop de definição de bits. result = 0 while shift > = 0 : result = result << 1 large_cand = ( result + 1 ) # O mesmo que result ^ 1 (xor), porque o último bit é sempre 0. if large_cand * large_cand <= n >> shift : resultado = grande_cand deslocamento - = 2 resultado de retorno

As apresentações tradicionais em papel e caneta do algoritmo dígito a dígito incluem várias otimizações não presentes no código acima, em particular o truque de pré-subtrair o quadrado dos dígitos anteriores que torna desnecessária uma etapa de multiplicação geral. Veja Métodos de cálculo de raízes quadradas § Woo ábaco para um exemplo. [1]

Em linguagens de programação

Algumas linguagens de programação dedicam uma operação explícita ao cálculo da raiz quadrada inteira além do caso geral ou podem ser estendidas por bibliotecas para esse fim.

(isqrt x): Common Lisp . [2]
math.isqrt(x): Python . [3] (desde a versão 3.8)