Algoritmo de precisión arbitraria de raíz cuadrada entera?

9

¿Hay algún algoritmo subcuadrático conocido para calcular el piso de la raíz cuadrada de un nentero de bits?

El algoritmo ingenuo sería algo así como

def sqrt(x):
    r = 0
    i = x.bit_length() // 2
    while i >= 0:
        inc = (r << (i+1)) + (1 << (i*2))
        if inc <= x:
            x -= inc
            r += 1 << i
        i -= 1
    return r

Esto requiere O(n)iteraciones, cada una con adiciones que son O(n)tiempo, por lo que es O(n^2)tiempo en general. ¿Hay algo más rápido? Sé que para el caso de la multiplicación hay algoritmos especiales que funcionan mejor que el tiempo cuadrático, pero no puedo encontrar nada para las raíces cuadradas.

Antimonio
fuente
Mi respuesta a algo relacionado podría ayudar a cs.stackexchange.com/a/37338/12052 . El único problema es que, una parte de la ecuación necesaria que necesitarías encontrar empíricamente para ajustar su precisión.
Francesco Gramano
@FrancescoGramano: Lo siento, no creo que eso ayude.
Aryabhata
por cierto, ¿es este requisito subcuadrático parte de un problema mayor? Porque la diferencia entre el cuadrático simple y el subcuadrático complicado podría no ser tan grande en la práctica. ¿O es solo de interés teórico?
Aryabhata
@Aryabhata Lo siento, no vi tu comentario antes. No, no es parte de un problema mayor, solo curiosidad.
Antimonio

Respuestas:

5

Puede usar el método de Newton o cualquiera de varios otros métodos para encontrar aproximaciones a las raíces del polinomio .p(x)=x2c

La tasa de convergencia para el método de Newton será cuadrática, lo que significa que el número de bits correctos se duplica en cada iteración. Esto significa que son suficientes iteraciones del método de Newton.O(lgn)

Cada iteración del método de Newton calcula

xj+1=xj(xj2c)/(2xj)=0.5xj+c2xj.

La complejidad de bits de la multiplicación es , para multiplicar dos enteros de bits (ignorando los factores ). La complejidad de bits para la división (a bits de precisión) es la misma. Por lo tanto, cada iteración se puede calcular en operaciones . Multiplicando por iteraciones, encontramos que el tiempo de ejecución general para calcular la raíz cuadrada con bits de precisión es . Esto es subcuadrático.blglgbb O (nlgn)O(lgn)n O (n(lgn)2)O (blgb)blglgbbO (nlgn)O(lgn)nO (n(lgn)2)

Creo que un análisis más cuidadoso muestra que esto se puede mejorar al tiempo de ejecución de (al tener en cuenta que solo necesitamos conocer cada con una de aproximadamente bits, en lugar de bits de precisión). Sin embargo, incluso el análisis más básico ya muestra un tiempo de ejecución que es claramente subcuadrático.xjjnO (nlgn)xjjn

DW
fuente
En binario, uno también tiene una gran conjetura inicial usando la identidad . En lugar de calcular el registro, se puede aproximar como el número de dígitos en x . Por ejemplo, log 2 101011 6 . x1/2=21/2log2xlog2xxlog21010116
Nick Alger
@DW: ¿Pero no estamos buscando una raíz cuadrada entera? Si realiza la iteración del método de newton utilizando solo aritmética de enteros, entonces necesitamos alguna justificación adicional para la afirmación , ¿no? De lo contrario, ya estamos asumiendo una precisión suficientemente grande ... Perdón si me falta algo obvio. O(logn)
Aryabhata
@DW: "La tasa de convergencia para el método de Newton" no será cuadrática si , y no sé qué sucede con los valores de c que no son reales no negativos.c=0cSu estimación de la complejidad de bits de la multiplicación es más estricta de lo que sugiere su siguiente comentario . Además, "necesitamos conocer cada dentro de" "bits de precisión". 2xj2j
@Aryabhata: No estamos "buscando una raíz cuadrada entera"; estamos buscando "el piso de la raíz cuadrada". Tiene razón sobre el problema de la aritmética de enteros, aunque las mismas complejidades de bits se mantienen para las operaciones de punto flotante.
1
@RickyDemer, sí, es un caso especial, porque entonces la raíz de p ( x ) tiene multiplicidad 2, pero cuando , la raíz tiene multiplicidad 1 lo que el método de Newton no tiene convergencia cuadrática. Supongo que nadie usaría el método de Newton para calcular la raíz cuadrada de (porque la raíz cuadrada de cero es obviamente cero). Entonces, ¿qué estás tratando de decir? ¿Es su comentario un comentario trivial que se aborda agregando algo a mi respuesta que dice "caso especial la raíz cuadrada de cero", o hay algo más profundo que me estoy perdiendo? c=0p(x)c = 0c>0c=0
DW
6

Uno de los problemas con el método de Newton es que requiere una operación de división en cada iteración, que es la operación entera básica más lenta.

Sin embargo, el método de Newton para la raíz cuadrada recíproca no. Si es el número para el que desea encontrar , repita:1x1x

ri+1=12ri(3xri2)

Esto a menudo se expresa como:

d i = 1 - w i x r i + 1 = r i + r i d i

wi=ri2
di=1wix
ri+1=ri+ridi2

Eso son tres operaciones de multiplicación. La división por dos se puede implementar como un desplazamiento a la derecha.

Ahora el problema es quer no es un número entero. Sin embargo, puede manipularlo como tal mediante la implementación de punto flotante manualmente, y haciendo un montón de operaciones de desplazamiento para compensar cuando sea apropiado.

Primero, cambiemos la escala de :x

x=22ex

donde nos gustaría que sea ​​mayor que, pero cercano a, . Si ejecutamos el algoritmo anterior en lugar de , encontramos . Entonces, . 1 x x r = 1x1xxr=1xx=2erx

Ahora dividamos en una mantisa y exponente:r

ri=2eiri

donde es un número entero. Intuitivamente, representa la precisión de la respuesta.riei

Sabemos que el método de Newton duplica aproximadamente el número de dígitos significativos precisos. Entonces podemos elegir:

ei+1=2ei

Con un poco de manipulación, encontramos:

ei+1=2ei
wi=ri2
xi=x22eei+1
di=2ei+1wixi2ei+1
ri+1=2eiriridi2ei+1

En cada iteración:

xrix2e+ei

Como ejemplo, intentemos calcular la raíz cuadrada de . Sabemos que la respuesta es . La raíz cuadrada recíproca es , por lo que estableceremos (esta es la escala del problema) y para nuestra conjetura inicial elegiremos y . (Es decir, elegimos para nuestra estimación inicial de ).x=263231212231e=31r0=3e0=23412

Entonces:

e1=4,r1=11
e2=8,r2=180
e3=16,r3=46338
e4=32,r4=3037000481

Podemos determinar cuándo dejar de iterar comparando con ; Si he calculado correctamente, debería ser lo suficientemente bueno. Sin embargo, nos detendremos aquí y encontraremos:eieei>2e

2633037000481×263231+32=3037000481

La raíz cuadrada entera correcta es , por lo que estamos bastante cerca. Podríamos hacer otra iteración o una iteración final optimizada que no duplique . Los detalles se dejan como ejercicio.3037000499ei

Para analizar la complejidad de este método, tenga en cuenta que multiplicar dos enteros de bits requiere operaciones . Sin embargo, hemos organizado las cosas para que . Por lo que la multiplicación para calcular multiplica dos números de bits para producir un número de bits, y los otros dos multiplicaciones multiplicar dos números -bit para producir una -número de bit.bO(blogb)ri<2eiwieiei+1ei+12ei+1

En cada caso, el número de operaciones por iteración es , y se requieren iteraciones . La multiplicación final está en el orden de las operaciones . Entonces, la complejidad general son las operaciones , que es subcuadrática en el número de bits en . Eso cumple todos los requisitos.O ( log e ) O ( 2 e log 2 e ) O ( e log 2 e ) xO(eilogei)O(loge)O(2elog2e)O(elog2e)x

Sin embargo, este análisis esconde un principio importante que todos los que trabajan con enteros grandes deben tener en cuenta: debido a que la multiplicación es superlineal en el número de bits, cualquier operación de multiplicación solo debe realizarse en enteros que tengan aproximadamente la magnitud de la precisión actual (y , Podría agregar, deberías intentar multiplicar números que tengan un orden de magnitud similar). Usar enteros más grandes que eso es una pérdida de esfuerzo. Los factores constantes importan, y para los enteros grandes, importan mucho.

Como observación final, dos de las multiplicaciones son de la forma . Claramente es un desperdicio calcular todos los bits de solo para tirar de ellos con un desplazamiento a la derecha. La implementación de un método de multiplicación inteligente que tenga esto en cuenta también se deja como un ejercicio. abcab2cabc

Seudónimo
fuente
Esto es genial. Sin embargo, un comentario: ¿no es la complejidad de bits de la división asintóticamente aproximadamente la misma que la complejidad de bits de la multiplicación? Entonces, estás hablando de algo que proporciona una mejora constante del factor, no una mejora asintótica, ¿verdad? Eso no estaba del todo claro por su respuesta.
DW
Usted dice que la multiplicación de dos números enteros -bit toma operaciones de bits. Creo que la respuesta correcta es algo como (¿verdad?). Es posible que desee indicar que está ignorando los factores de poli-log-log (por ejemplo, colocando una tilde sobre su gran O, o algo así). O ( b lg b ) O ( b lg b ( lg l g b ) O ( 1 ) )bO(blgb)O(blgb(lglgb)O(1))
DW
1
@DW:No, dice que "multiplicar dos enteros de bits requiere operaciones ". La palabra "bit" solo aparece una vez en eso; de lo contrario ya lo habría señalado. O ( b log b )bO(blogb)
Es una cuestión de factores constantes, sí. Los mejores algoritmos de división de enteros grandes utilizan una técnica muy similar a la del algoritmo completo, como la iteración de Newton-Raphson y la duplicación de la precisión efectiva en cada iteración. ¡Un bucle Newton-Raphson dentro de un bucle Newton-Raphson se acumula en los factores constantes! Ricky Demer tiene razón; Estaba pensando en la palabra modelo de RAM. Probablemente debería haber mencionado esto.
Seudónimo