Para verificar si el número es raíz cuadrada o no sin usar la función sqrt?

Answer 1

Supongamos que consideramos la suma [matemática] S = 1 + 3 + 5 + .. + (2k + 1) [/ matemática]

si calculamos la suma obtenemos [matemática] S = \ dfrac {k} {2} (2 + (k-1) 2) [/ matemática] usando la suma de un AP ([matemática] S = \ dfrac {n } {2} (2a_0 + (n-1) d) [/ matemáticas]).

Observe que [matemáticas] S = k ^ 2 [/ matemáticas]

Entonces, si comienza a sumar los números impares en secuencia hasta que la suma exceda el número dado, sabrá que es un cuadrado o no. Si la suma se vuelve exactamente igual al número dado, entonces tienes su raíz cuadrada exacta. p.ej.

para [matemáticas] N = 9, 1 + 3 + 5 = 9 [/ matemáticas]. entonces, para 3 términos, la suma es exactamente igual, por lo tanto, la raíz es 3.

Este método es de [math] O (\ sqrt {N}) [/ math] complejidad.

Una solución mucho más fácil es simplemente recorrer hasta que el cuadrado sea menor que el número.

para (largo largo x = 1;; x ++) {
if (x * x == N) devuelve x;
de lo contrario si (x * x> N) devuelve -1;
}

pero usar la multiplicación es mucho más costoso que las sumas.

otro método sería utilizar el método de Newton para dar complejidad logarítmica, pero nuevamente esto requiere la división de “dobles”, por lo tanto, puede no ser exacto para cuadrados perfectos.

También hay un método probabilístico para esto. Mira este enlace Forma eficiente de determinar si un número es Cuadrado perfecto

si [matemáticas] a ^ {\ frac {p – 1} {2}} \; \ equiv \; 1 \; (mod \; p) \; [/ math] entonces el número es una raíz perfecta con probabilidad de [math] 1 – \ dfrac {1} {2 ^ q} [/ math] para q primos marcados.

También podría usar la búsqueda binaria para esto. Ideone.com

Answer 2

Es fácil. Al menos para números reales.

is_a_square_root = lambda x: x> = 0