Calcule la raíz cuadrada usando adiciones (bit) y desplazamientos como primitivas

Pregunta: Dado un bits número natural , cómo calcular utilizando sólo adiciones y cambios (BIT)?$n$$N$$\lceil \sqrt{N} \rceil$$O(n)$

El consejo es utilizar la búsqueda binaria. Sin embargo, no pude lograr la complejidad requerida (obtuve ).$O(n^2)$

¿Qué quiere decir con using only $O(n)$ (bit) additions and shifts:

Este es un ejercicio en un libro de algoritmos.
En mi opinión, significa que agregar dos, digamos -bit, números naturales cuesta y cambiar a, digamos -bit, número natural también cuesta . Entonces solo se nos permite usar tales operaciones veces. No menciona el costo de la comparación. Supongo que podemos ignorarlo o suponer que comparar dos, digamos -bit, números naturales también cuesta .$n$$O(1)$$n$$O(1)$$O(1)$$O(n)$
$n$$O(1)$

Mi algoritmo$O(n^2)$ :

1. Determine el rango del número de bits de : Por lo tanto, t_1 \ triangleq \ lfloor \ frac {n-1} {2} \ rfloor + 1 \ le t \ le \ lceil \ frac {n} {2} \ rceil + 1 \ triangleq t_2.$t$$\lceil \sqrt{N} \rceil$ $$2^{\frac{n-1}{2}} \le \sqrt{N} \le 2^{\frac{n}{2}} \Rightarrow 2^{\lfloor \frac{n-1}{2} \rfloor} \le \lceil \sqrt{N} \rceil \le 2^{\lceil \frac{n}{2} \rceil}$$ $$t_1 \triangleq \lfloor \frac{n-1}{2} \rfloor + 1 \le t \le \lceil \frac{n}{2} \rceil + 1 \triangleq t_2.$$
2. Búsqueda binaria: busque $\lceil \sqrt{N} \rceil$ entre $2^{t_1}$ y $2^{t_2}$ utilizando la búsqueda binaria. Para cada número $x$ , para calcular $x^2$ usando adiciones y cambios como primitivas y compararla con $N$ .

La complejidad es, por lo tanto, para veces de búsqueda binaria y computación , cada una de las cuales toma adiciones y desplazamientos.$O(n \times n) = O(n^2)$$O(n)$$x^2$$O(n)$

Un algoritmo iterativo parece que debería funcionar.

Deje . Supongamos que sabemos que es la aproximación entera a , es decir, , y supongamos que conocemos el valor de (obtenido previamente).$M=\lfloor N/4 \rfloor$$x$$\sqrt{M}$$x=\lceil \sqrt{M} \rceil$$x^2$

Ahora queremos encontrar . ¿Cuáles son los posibles valores de ? Estoy bastante seguro de que los únicos valores posibles son o . Y es fácil probar ambos y ver cuál es el correcto. En particular, para , tenemos , que puede obtenerse de mediante dos desplazamientos a la izquierda ( tiempo); para , tenemos , que puede obtenerse a partir de y con cuatro desplazamientos a la izquierda y dos adiciones ( de tiempo). Ahora solo compara esos dos valores con$y=\lceil \sqrt{N} \rceil$$y$$y=2x$$y=2x+1$$y=2x$$y^2=4x^2$$x^2$$O(1)$$y=2x+1$$y^2=4x^2+4x+1$$x^2$$x$$O(1)$$N$ para ver cuál es el correcto.

De esta manera, obtenemos un algoritmo iterativo en el que hacemos iteraciones, y donde cada iteración toma tiempo. El tiempo total de ejecución es , según sea necesario.$n/2$$O(1)$$O(n)$

Me doy cuenta de que esto no usó la búsqueda binaria. Oh bien.

¿Estamos hablando enteros aquí? Donde N es n bits de largo?

A = 2(n/2), B = A  and C = A2
Step: B = B/2
     If C > N,  
         C = C - 2AB + B2    // too high - make smaller
         A = A - B
     Else 
         C = C + 2AB + B2   // keep this bit
         A = A + B                 
Repeat until B = 0                  // =1 on last loop

El bucle se realiza n / 2 veces, lo que debería proporcionarle un rendimiento de O (n)

Editar: ¿Cómo funciona y por qué?
Esta es una versión de Aproximación sucesiva, que también se utiliza en algoritmos CORDIC.
Comenzando con el bit único más grande posible (con un cuadrado menor que N), establece un bit a la vez y calcula el nuevo cuadrado.
Si el nuevo cuadrado aún es menor que N, mantenga el bit como establecido.
Si el nuevo cuadrado es demasiado grande, borre el bit, deshaga el efecto de agregarlo y pase al siguiente bit.

Ejemplo: N = 441 (1 1011 1001 binario), n = 9

Start:  A = 24 = 16 (1 0000)  B = 16 C = 256 (100 0000)

1   B = 8 (1000) C = 256 + 2(16)(8) + (8)(8) = 576 (10 0100 0000) {high}
    A = 16 + 8 = 24
2   B = 4  (100) C = 576 - 2(16)(4) + (4)(4) = 400 (1 1001 0000) {low}
    A = 24 - 4 = 20
3   B = 2   (10) C = 400 + 2(20)(2) + (2)(2) = 484  (1 1110 0100) {high}
    A = 20 + 2 = 22
4   B = 1    (1) C = 484 - 2(20)(1) + (1)(1) = 441  (1 1011 1001) {keep this}
    A = 22 - 1 = 21
5   B = 1/2 or 0 in integer math; end

El método principal es la de rellenar los trozos de de izquierda a derecha, manteniendo nuestra estimación por debajo de ella, o más bien la plaza de nuestra estimación por debajo de . Cada bit es una potencia de 2, por lo que cuadrar o multiplicar otro número por siempre es un cambio de bit. $\sqrt{N}$$N$$b$$b$

Si la estimación actual es , , y ya conocemos , obtenemos , y podemos reescribir los términos segundo y tercero como y . A continuación, se suma todo y prueba (supongo que puede hacer ) y establecer el bit si la plaza está todavía por debajo .$a$$b=2^i$$a^2$$(a+b)^2 = a^2 + 2ab + b^2$$a << (i+1)$$1 << (i << 1)$$<$$i$$N$

Comenzamos el ciclo en y hacemos cuenta regresiva a cero, manteniendo y medida que avanzamos. Es una especie de búsqueda binaria, pero una donde los límites se asignan a diferencias de un solo bit.$i = n/2 = n >> 1$$a$$a^2$

Me gusta la respuesta de Alan Campbell : con un seguimiento cuidadoso de las conjeturas anteriores, la nueva resta es fácil cada vez, y la raíz cuadrada binaria shift-and-add es casi tan rápida como una división binaria shift-and-add.

Pero puede ser posible ir más rápido, en lugar de hacer su próxima suposición con un solo dígito binario, en lugar de usar un algoritmo "Ab" x "Ab", y hacer que su próxima suposición sea el promedio de su suposición anterior, y el número original dividido por la suposición anterior. Parece que llevaría más tiempo, no más corto. Sin embargo, la división no tiene que ser exacta. Entonces, si la división solo se ejecuta en la raíz cuadrada del número de dígitos restantes para encontrar, entonces en realidad podría ahorrar tiempo. Además, si para su división usa el método francés, de división de taquigrafía, entonces podría romper algo de velocidad en su cálculo para divisiones realmente grandes.

Ahora, si agregamos cálculos en paralelo que producen resultados corregibles preliminares antes de encontrar la respuesta ... entonces podríamos estar en algo.