Era necesario verificar si el número entero es un cuadrado y, de ser así, calcular la raíz. Y quiero hacer esto en aritmética de enteros. Está claro que el método de Newton se puede implementar en enteros, pero requiere división en cada paso. ¿Pero puede ser de otra manera? Encuentre el módulo de raíz cuadrada del poder de dos, y verifique si será una raíz cuadrada ordinaria.
Puede restringirse a números impares: para un número par, si el número de dígitos cero menos significativos es impar, entonces no hay raíz, pero si es par, puede cambiar el número a la derecha, calcular la raíz del impar y volver a la mitad izquierda del número original de cero bits.
Para N y 2
k impares, k> 3, si N ≡ 1 mod 8, entonces hay 4 raíces diferentes módulo 2
k , de lo contrario no hay raíces. Necesitamos la más pequeña de las cuatro raíces de x. Las otras tres raíces son 2
k - x, 2
k-1 + x y 2
k - 2
k-1 - x
Me gustaría algo similar a calcular el
módulo inverso 2 k : duplicar el número de bits válidos por iteración.
Supongamos que ya tenemos una raíz x
0 de N módulo 2
k :
N - x 0 2 = 2 k aY queremos encontrar
x 1 = x 0 + 2 k-1 y tal que en N - x
1 2 haya más bits cero más bajos.
N - (x 0 + 2 k-1 y) 2 = 2 k a - 2 k x 0 * y - 2 2k-2 y 2Dividir por 2
k :
a - x 0 * y - 2 k-2 y 2Y equivale a 0 módulo 2
k-2 :
y = a * x 0 -1 mod 2 k-2Recibido
x 1 = x 0 + 2 k-1 a * (x 0 -1 mod 2 k-2 )Y finalmente
x 1 = x 0 + (N - x 0 2 ) / 2 * (x 0 -1 mod 2 k-2 )De los k bits en la siguiente iteración, obtienes 2 (k-1) bits. Al mismo tiempo, consideramos lo opuesto a la raíz en cada iteración.
Código de prueba:
uint8_t sqr16(uint16_t n) { if (n % 8 != 1) return 0; uint16_t sqr = (n + 1) / 2; //4 bit uint16_t inv = 2 - sqr; sqr += inv * (n-sqr*sqr)/2; //6 bit inv *= 2 - sqr * inv; sqr += inv * (n-sqr*sqr)/2; //10 bit //inv *= 2 - sqr * inv; if (sqr & 256) sqr = 0u - sqr; sqr = (uint8_t)sqr; // lowest root if (n == sqr*sqr) return sqr; return 0; }
Agregando un par de iteraciones, obtenemos la raíz de uint_64