Usuário:Lechatjaune/Testes

Em Matemática, a raiz quadrada inteira é definida como parte inteira da Raiz quadrada de um número inteiro positivo:

$$\operatorname {isqrt} (n)=\lfloor {\sqrt {n}}\rfloor .$$

A raiz quadrada inteiro de n é o inteiro positivo que satisfaz a condição:

$$m^{2}\leq n<{(m+1)}^{2}.$$

Algoritmos

Algoritmos escolares

Ilustração da propriedade que todo quadrado perfeito n² é a soma dos n menores ímpares positivos.

Todo quadrado perfeito n² pode ser escrito como a soma dos n menores números ímpares positivos.

m = 12 = 1
m = 22 = 4
m = 32 = 9
m = 42 = 16
m = 52 = 25

A partir dessa observação, um método de encontrar a raiz quadrada inteira consiste em observar que a diferença entre dois quadrados perfeitos e seu antecessor é um número ímpar, justamente a soma das suas raízes, por exemplo: 11² - 10² = 21 = 11 + 10 ou 23² - 22² = 45 = 23 + 22. Essa propriedade vem do produto notável (x + 1)² - x² = 2x + 1 = (x + 1) + x. Dessa forma, pode-se somar os números ímpares até chegar no inteiro cuja raiz quadrada se procura. O método pode ser melhorado, subtraindo do radicando um quadrado perfeito conhecido e inferior a ele. Por exemplo: ao calcular raiz quadrada de 144, subtrai-se 100, que é 10², que é equivalente a subtrair os dez primeiros primos positivos. A sequência é:

144 - 100 = 189

44 - 21 = 23

23 - 23 = 0

Portanto 23² = 12, pois foram executados mais dois passo.

Referências para linear e busca binária.

=

Método de Heron em aritmética inteira

O seguinte algoritmo calcula a raiz quadrada inteira empregando apenas divisão inteira:

1. Inicializa x com qualquer inteiro não superior à raiz quadrada de n. Por exemplo, n.
2. Atribui a y o valor de x + (n / x) / 2, em que todas as operações devem ser feitas em aritmética inteira.
3. Se y < x, atribui a x o valor de y. Senão retorna x.