¿Acceso directo a la búsqueda de la raíz cuadrada de un cuadrado perfecto?

Question

He estado tratando de acelerar un algoritmo donde la operación más costosa es la raíz cuadrada. Sin embargo, a menudo puedo garantizar que el valor de entrada es un cuadrado perfecto. ¿Tengo curiosidad por saber si hay cualquier algoritmos que se encuentran la raíz cuadrada más rápidamente (tiempo constante?) si se sabe que la entrada es un cuadrado perfecto?

Gracias, Ryan

Answer 1

La suma de los primeros números impares $k$ es $k^2$. Sabiendo esto, usted puede calcular la raíz cuadrada mediante la suma de números impares sucesivos (a partir de uno)-una vez el valor de entrada, devuelve el número de sumatorias que hiciste.

Por ejemplo, $16 = 1 + 3 + 5 + 7$; es $4$ sumandos, así $\sqrt{16}=4$. Este proceso siempre funciona, ya que nuestra entrada se garantiza que sea de la forma $k^2$ $k \in \mathbb N$.

Creo que este método funcionaría en $O(\sqrt n)$.

Answer 2

Con enteros dentro sensible límites en comparación con lo que su CPU puede calcular de forma nativa, puede ser bastante fácil para restringir el rango de números binarios de búsqueda para encontrar la raíz cuadrada de x.

(0. quitar los dos bloques de final 0 a partir de su número binario. Cada bloque de quitar es un factor de 2 a se multiplica el resultado del paso siguiente. Esto se puede hacer en tiempo constante, si no me equivoco: Observar la estructura de "Restar 1 y XOR con la entrada" para los números con $t$ trailing 0s. A continuación, utilice el POPCNT (Hamming de peso) la instrucción de los más graves de la Cpu. Después de la eliminación de estos 0s, es decir, dividiendo por $4^n$, usted terminará para arriba con un número impar; si usted termina con un número después de la eliminación de un número de 0s, su número no es un cuadrado perfecto.)

1. Encontrar $k=\lfloor\log_2 x\rfloor$, ver https://graphics.stanford.edu/~seander/bithacks.html
2. $a=\frac k2$
3. Por lo tanto, $2^a$ se convierte en un límite inferior para el $\sqrt x$ $2^{a+1}$ superior. Ambos valores se pueden encontrar a través del desplazamiento de bits a 1.
4. Desde aquí, hacer un binario search1.

Dudo que sería mucho más rápido de conversión de punto flotante y dejar que la FPU hacerlo en hardware, dándole un valor aproximado, comvertable de vuelta a entero, de los que sólo se necesita buscar pequeños intervalos (es decir, la pérdida de precisión) para el entero de la raíz cuadrada.

Tenga en cuenta que a tales problemas como el tuyo, algorítmica elegancia a menudo desempeña un papel de menor importancia - que necesita para ser rápido en hardware real, de modo que la ejecución de evitar una gran cantidad de memoria de la interacción es una buena cosa, y: con instrucciones SIMD, haciendo cuatro a 16 operaciones del mismo tipo tome el tiempo de hacer uno, así que si usted simplemente necesita para probar un par de enteros para su plaza, la modificación de su algoritmo para poder probar cuatro en paralelo es la forma más eficiente de ahorro de la mitad de las operaciones necesarias.

Usted tiene un problema tecnológico, no tanto numéricos.

---

1 búsqueda binaria se supone que puede hacer un cuadrado y una comparación de una vez; como se indicó antes, podría muy bien ser capaz de dividir el intervalo en cinco trozos de búsqueda mediante el cálculo de los cuatro productos a la vez y comparar los cuatro números a la vez el uso de SIMD. Esto además, indicios de que incluso si no debe haber ningún constante de tiempo del algoritmo (y estoy bastante seguro de que no hay ninguno), usted puede ser mejor de $\mathcal O(n^2·\log_2 x)$; comparar Fürer del algoritmo.

Answer 3

Creo que la única ventaja adquirida por tener un cuadrado perfecto en métodos analíticos es que usted sabe que un algoritmo iterativo realmente terminar. Así que en lugar aquí es un número teórico de la solución que va a trabajar para los números de menos de $2^{66}$.

Hecho 1: Si $p$ es una de las principales con el $p \equiv 3 \mod 4$ $x$ es un cuadrado perfecto,$\mod p$, luego $$x \equiv \left(x^{(p+1)/4}\right)^2 \mod p,$$ i.e. you can compute the modular square root by exponentiating by $(p+1)/4$. (Ver https://crypto.stackexchange.com/a/20994/18112)

Hecho 2: Los números $m_{17}=2^{17}-1$, $m_{19}=2^{19}-1$, y $m_{31}=2^{31}-1$ (Mersenne) de los números primos cuyo producto es mayor que $2^{66}$.

Método: Vamos a $S$ ser la plaza cuya raíz $t$ le gustaría encontrar. Calcular los siguientes $$t_{17} \equiv S^{2^{15}} \mod m_{17}$$ $$t_{19} \equiv S^{2^{17}} \mod m_{19}$$ $$t_{31} \equiv S^{2^{29}} \mod m_{31}$$ Entonces el Teorema del Resto Chino da $$t \equiv \pm 31207 t_{17} m_{19} m_{31} \pm 298611 m_{17} t_{19} m_{31} \pm 413071270 m_{17} m_{19} t_{31} \mod m_{17}m_{19}m_{31}$$ , a Continuación, compruebe estos 8 posibilidades.

Observaciones: no sé cómo computacionalmente eficiente, esto es; es más de una solución matemática de tomar ventaja de saber que $S$ es un cuadrado. Me atrevería a adivinar que es lo "constante de tiempo" como usted podría conseguir como el número de pasos es esencialmente fija, sino que la constante puede ser mayor que el $\sqrt{n}$ de otros métodos para este rango de $n$.

Answer 4

Creo que una búsqueda binaria tipo de algoritmo sería muy eficiente para grandes valores de entrada si sabemos que la entrada es un cuadrado perfecto.

Deje $n$ ser el valor de la entrada.

1. Comenzar con dos enteros $a$ $b$ tal que $a^2 < n$$b^2 > n$. Podríamos usar $a=0$$b=n$.

2. Encontrar el punto medio de la $a$ $b$ y redondee al entero más cercano, si es necesario. Llamar a esto $m$.

3. Encontrar $m^2$. Si $m^2=n$ $m$ es la raíz cuadrada. Si $m^2>n$ $m$ es demasiado alto, por lo que volvemos al paso 2 con $a$ $m$ como nuestros dos números enteros. Si $m^2<n$ $m$ es demasiado bajo, así que volvemos al paso 2 con $m$ $b$ como nuestros dos números enteros. Repita hasta que la raíz cuadrada se encuentra.

El cuadrado de $m$ puede ser lo que ralentiza el algoritmo de abajo, sin embargo, creo que la multiplicación de los algoritmos se implementan en hardware del procesador y por lo tanto muy eficiente. En términos de número de operaciones, creo que la búsqueda binaria se podría ejecutar en tiempo logarítmico y por consiguiente, sería preferible $O(\sqrt n)$ para grandes valores de entrada. Sin embargo, no soy experto en el algoritmo de la eficiencia...