Algoritmo de raíz cuadrada entero

Question

Actualmente estoy trabajando mi camino a través de David M. Bressoud "Factorización y Pruebas de Primalidad", y yo estoy luchando con un ejercicio (ejercicio 5.7) que le pide al lector demostrar que el siguiente algoritmo produce el mayor entero menor o igual a la raíz cuadrada de $n$:

\begin{align} \text{INITALIZE:} \quad &\text{READ} \;n \\ &a \leftarrow n \\ &b \leftarrow \lfloor (n+1)/2 \rfloor \\\\ \text{MYSTERY_LOOP:} \quad &\text{WHILE} \: b < a \; \text{DO} \\ &\quad a \leftarrow b \\ &\quad b \leftarrow \lfloor (a \times a + n) / (2 \times a) \rfloor \\\\ \text{TERMINATE:}\quad &\text{WRITE} \; a \end{align}

Sé de análisis real de que la secuencia de $x_{m+1} = \frac{x_m^2 + n}{2 x_m}$ converge a la raíz cuadrada de $n$ (para cualquier sensato $x_0$), por lo tanto moralmente, yo puedo creer que el anterior algoritmo converge a la parte entera de la raíz cuadrada de $n$.

¿Cómo podemos demostrar formalmente que el algoritmo anterior obras (es decir, termina en un número finito de pasos, de tal manera que $a^2 \leq n$$(a+1)^2 >n$), y por otra parte, ¿de inicio las iteraciones con $b = \lfloor\frac{n+1}{2} \rfloor$? Es $\lfloor\frac{n+1}{2} \rfloor$ sólo una muy cruda aproximación? ¿Cuál es su importancia?

He intentado dividir el piso en una parte real menos una parte entre 0 y 1 (es decir,$\lfloor x \rfloor = x - \{x\}$), pero no he sido capaz de llegar muy lejos con esto.

Además, tenemos la misma convergencia cuadrática que tenemos cuando nos calcular el (ordinario) de la raíz cuadrada usando el método de Newton?

Answer 1

Después de algunos enraizamiento de todo, he encontrado la respuesta en otro hilo, pero en aras de la exhaustividad, voy a reproducir el argumento aquí (la prueba es tomada de un libro de texto de Cohen):

En primer lugar, tenga en cuenta que $a$ $b$ siempre son positivos. Si el algoritmo no terminar, la condición en el misterio de bucle ($b <a$) implica que tendríamos un infinito, estrictamente decreciente, la secuencia de enteros positivos, lo cual es una contradicción, ya que hay sólo un número finito de números de menos de $n$. De manera que el algoritmo termina.

Por lo tanto, en algún punto, debemos tener la $b \geq a$, es decir,$$\left\lfloor \frac{a^2 +n}{2a} \right\rfloor \geq a.$$ Also note that $$\frac{t^2 + n}{2t} \geq \sqrt{n}$$ for all positive $ t$ (easily shown), thus we have $$a \geq \left\lfloor\sqrt{n}\right\rfloor.$$ So assume $un$ does not equal $\lfloor\sqrt{n}\rfloor$. So $\geq \lfloor\sqrt{n}\rfloor +1$ which implies that $^2 > n$. Putting this together, we get $$0 \leq\left\lfloor\frac{a^2 +n}{2a}\right\rfloor -a = \left\lfloor \frac{n -a^2}{2a} \right\rfloor < 0$$ because $n-a^2 < 0$. This is a contradiction, and thus, $$ must be equal to the integer square root of $$ n.

En el enlace de arriba, también hay algo de debate sobre la complejidad del algoritmo anterior, que me puede agregar más tarde.

Answer 2

Usando la notación de la $a$ $b$ sólo es necesario cuando la programación.

Se han identificado correctamente que el algoritmo da una secuencia de valores, que voy a llamar (como lo hizo) el $x_m$.

Así tenemos que la relación se $x_{m+1} = \lfloor \frac{x_m^2 + n}{2 x_m} \rfloor$

Comenzando con $x_0=n$ da $x_{1} = \lfloor \frac{x_0^2 + n}{2 x_0} \rfloor=\lfloor \frac{n^2 + n}{2 n} \rfloor = \lfloor \frac{n+1}{2} \rfloor$, que responde a una de sus preguntas. También demuestra que el cambio de $x_0$ $x_1$es siempre una disminución (a menos que n=1).

Dados dos términos sucesivos de la secuencia de $x_m$$x_{m+1}$, hay tres resultados posibles:

1) $x_{m+1}=x_m$

2) $x_{m+1}<x_m$

3) $x_{m+1}>x_m$

Vamos a considerar estos a su vez.

1) $x_{m+1}=x_m$

$\lfloor \frac{x_m^2 + n}{2 x_m} \rfloor=x_m$

El $floor$ función puede ser tratado por expresar $\lfloor \frac{x_m^2 + n}{2 x_m} \rfloor=\frac{x_m^2 + n}{2 x_m}-p$ donde $0 \le p < 1$

Así tenemos a $\frac{x_m^2 + n}{2 x_m}-p=x_m$

Reorganización de da $\frac{n-x_m^2}{2 x_m}=p$

Desde $0 \le p < 1$, podemos decir que el $0 \le \frac{n-x_m^2}{2 x_m} < 1$

Tener en cuenta esto en dos partes, tenemos:

$0 \le \frac{n-x_m^2}{2 x_m}$

$x_m$ es positivo, por lo $0 \le {n-x_m^2}$

$x_m^2 \le n$

$x_m \le \sqrt n$

Entonces:

$\frac{n-x_m^2}{2 x_m} < 1$

${n-x_m^2} < {2 x_m}$

$n<x_m^2 + 2 x_m$

Completando el cuadrado,

$n+1<x_m^2 + 2 x_m+1$

$n+1<(x_m + 1)^2$

$\sqrt {n+1}<x_m + 1>$

$\sqrt {n+1}-1<x_m $

Hay que poner las dos desigualdades de nuevo juntos nos da $\sqrt {n+1}-1<x_m \le \sqrt n$

Se puede demostrar (binomio de expansión) que $\sqrt {n+1}-1>\sqrt n -1 $ tenemos que:

$\sqrt n - 1 <x_m \le \sqrt n$

Así que si la secuencia converge a un valor, entonces este será el entero más grande menor o igual a la raíz cuadrada de $n$.

Podría ser, sin embargo, que los valores oscilan sin convergentes. ¿Qué acerca de esas situaciones?

Movimiento:

2) $x_{m+1}<x_m$

Siguiendo el mismo método que antes, tenemos

$\frac{x_m^2 + n}{2 x_m}-p<x_m$

$\frac{n - x_m^2}{2 x_m}<p$

$\frac{n - x_m^2}{2 x_m}<1$

${n - x_m^2}<{2 x_m}$

$n<x_m^2+2 x_m$

$n+1<x_m^2+2 x_m+1$

$n+1<(x_m+1)^2$

$\sqrt {n+1}<x_m+1$

$x_m>\sqrt {n+1}-1$

Como antes, esto da $x_m>\lfloor \sqrt n \rfloor$

Si hay dos sucesivas disminuciones en el valor, tanto en $x_m$ $x_m+1$ será mayor que $x_m>\lfloor \sqrt n \rfloor$, pero los valores se acercan más a $x_m>\lfloor \sqrt n \rfloor$, teniendo así la convergencia.

3) $x_{m+1}>x_m$

$\frac{x_m^2 + n}{2 x_m}-p>x_m$

$\frac{n - x_m^2}{2 x_m}>p$

Sabemos que $p \ge 0$, lo $\frac{n - x_m^2}{2 x_m} \ge 0$

$n - x_m^2 \ge 0$

$x_m^2 \le n$

$x_m \le \sqrt n$

Esto significa que un aumento en los valores de la secuencia sólo ocurre si el valor de la secuencia es menor o igual a la raíz cuadrada. No puede haber un infinito de ejecución de los aumentos porque finalmente el valor será mayor que la raíz cuadrada. Por lo tanto, no debe ser finalmente una disminución en los valores de la secuencia.