Raiz quadrada inteira - Integer square root

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 ,

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

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

Algoritmo usando o método de Newton

Uma forma de cálculo e é usar o método de Heron , que é um caso especial do método de Newton , para encontrar uma solução para a equação , dando a fórmula iterativa ${\ displaystyle {\ sqrt {n}}}$${\ displaystyle {\ mbox {isqrt}} (n)}$${\ displaystyle x ^ {2} -n = 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 . ${\ displaystyle \ {x_ {k} \}}$ ${\ displaystyle {\ sqrt {n}}}$${\ displaystyle k \ to \ infty}$

Critério de parada

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

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

garante no algoritmo acima. ${\ 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.

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. ${\ displaystyle {\ sqrt {n}}}$${\ displaystyle n}$${\ displaystyle \ {x_ {k} \}}$${\ displaystyle x_ {0}}$${\ displaystyle {\ mbox {isqrt}} (n)}$

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 ${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$

${\ 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

${\ displaystyle \ left \ lfloor {\ frac {1} {2}} \ left (x_ {k} + \ left \ lfloor {\ frac {n} {x_ {k}}} \ right \ rfloor \ right) \ direita \ 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. ${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$

Na versão original, tem-se para e para . Portanto, na versão inteira, tem-se e até que a solução final seja alcançada. Para a solução final , um tem e , então o critério de parada é . ${\ displaystyle {x} _ {k} \ geq {\ sqrt {n}}}$${\ displaystyle k \ geq 1}$${\ displaystyle {x} _ {k}> {x} _ {k + 1}}$${\ displaystyle {x} _ {k}> {\ sqrt {n}}}$${\ displaystyle \ lfloor {x} _ {k} \ rfloor \ geq \ lfloor {\ sqrt {n}} \ rfloor}$${\ displaystyle {x} _ {k} \ geq \ lfloor {x} _ {k} \ rfloor> {x} _ {k + 1} \ geq \ lfloor {x} _ {k + 1} \ rfloor}$${\ displaystyle {x} _ {s}}$${\ displaystyle {x} _ {s}}$${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor \ leq \ lfloor {x} _ {s} \ rfloor \ leq {\ sqrt {n}}}$${\ displaystyle \ lfloor {x} _ {s + 1} \ rfloor \ geq \ lfloor {x} _ {s} \ rfloor}$${\ displaystyle \ lfloor {x} _ {k + 1} \ rfloor \ geq \ lfloor {x} _ {k} \ 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. ${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$${\ displaystyle n + 1}$${\ displaystyle n + 1}$${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor +1}$

Exemplo de implementação em C

// Square root of integer
unsigned long int_sqrt ( unsigned long s )
{
	unsigned long x0 = s >> 1;				// Initial estimate
                                            // Avoid overflow when s is the maximum representable value

	// Sanity check
	if ( x0 )
	{
		unsigned long x1 = ( x0 + s / x0 ) >> 1;	// Update
		
		while ( x1 < x0 )				// This also checks for cycle
		{
			x0 = x1;
			x1 = ( x0 + s / x0 ) >> 1;
		}
		
		return x0;
	}
	else
	{
		return s;
	}
}

Exemplo numérico

Por exemplo, se alguém calcula a raiz quadrada inteira de 2.000.000 usando o algoritmo acima, obtém-se a sequência 1.000.000, 500.001, 250.002, 125.004, 62.509, 31.270, 15.666, 7.896, 4.074 , 2 282, 1 579, 1 422, 1 414, 1 414. São necessários um total de 13 etapas de iteração. Embora o método de Heron converta quadraticamente perto da solução, menos de um bit de precisão por iteração é obtido no início. Isso significa que a escolha da estimativa inicial é crítica para o desempenho do algoritmo.

Quando um cálculo rápido para a parte inteira do logaritmo binário ou para o comprimento de bits está disponível (como, por exemplo, std :: bit_width em C ++ 20 ), é melhor começar em

${\ displaystyle x_ {0} = 2 ^ {\ lfloor (\ log _ {2} n) / 2 \ rfloor +1}}$,

que é a menor potência de dois maior que . No exemplo da raiz quadrada número inteiro de 2 000 000, , , e a sequência resultante é de 2 048, 1 512, 1 417, 1 414, 1 414. Neste caso são necessários apenas 4 passos iteração. ${\ displaystyle {\ sqrt {n}}}$${\ displaystyle \ lfloor \ log _ {2} n \ rfloor = 20}$${\ displaystyle x_ {0} = 2 ^ {11} = 2048}$

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, ainda resultará em um quadrado . Se parar após a posição de um, o resultado calculado será a raiz quadrada inteira. ${\ displaystyle {\ sqrt {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 works for only non-negative inputs"
    if n < 2:
        return n

    # Recursive call:
    small_cand = integer_sqrt(n >> 2) << 1
    large_cand = small_cand + 1
    if large_cand * large_cand > n:
        return small_cand
    else:
        return large_cand


# equivalently:
def integer_sqrt_iter(n: int) -> int:
    assert n >= 0, "sqrt works for only non-negative inputs"
    if n < 2:
        return n

    # Find the shift amount. See also [[find first set]],
    # shift = ceil(log2(n) * 0.5) * 2 = ceil(ffs(n) * 0.5) * 2
    shift = 2
    while (n >> shift) != 0:
        shift += 2

    # Unroll the bit-setting loop.
    result = 0
    while shift >= 0:
        result = result << 1
        large_cand = (
            result + 1
        )  # Same as result ^ 1 (xor), because the last bit is always 0.
        if large_cand * large_cand <= n >> shift:
            result = large_cand
        shift -= 2

    return result

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.

Em linguagens de programação

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

• (isqrt x): Common Lisp .
• math.isqrt(x): Python . (desde a versão 3.8)

Veja também

• Métodos de cálculo de raízes quadradas

Referências

links externos

• Uma visão geométrica do algoritmo de raiz quadrada