¿Hubo algún procesador que implementara una instrucción de raíz cuadrada entera?

• El punto en discusión no es la común sqrt de punto flotante, sino si hubo casos en que la raíz cuadrada entera se ofreciera como instrucción de CPU o función de hardware; el divider/square-rooter del Nintendo DS es similar, pero no es una instrucción nativa
• El RTX 2000 Forth CPU de Harris y el RTX 2010 de grado militar se mencionan como casos que ofrecían una instrucción de square root en varias etapas; el RTX 2000 obtenía el resultado con una estructura de 1 setup y 15 steps
• Un caso más antiguo, ENIAC, en 1946 usaba una divider/square-rooter unit para controlar acumuladores de enteros decimales y realizar hasta 40 divisiones o 3 operaciones de raíz cuadrada por segundo
• La raíz cuadrada entera requería un multiplicador entero rápido y suficiente precisión, lo que suponía una carga importante para las CPU históricas; también existen enfoques como frsqrte/frsqrts de ARMv8, que separan estimación e iteración para ajustar precisión y velocidad
• La inverse square root al estilo Quake ya no suele tener una ventaja de rendimiento en hardware moderno; búsqueda en tablas, interpolación, iteraciones de la familia de Halley y divide and conquer de punto fijo varían como opciones según el entorno de implementación

---

Alcance de la pregunta y el caso de Nintendo DS

• La pregunta trata sobre si existió algún procesador que implementara realmente una instrucción de raíz cuadrada entera
• Parte de la premisa de que las instrucciones de square root de punto flotante son comunes, pero que quien pregunta no ha visto instrucciones square root dedicadas a enteros
• Nintendo DS tenía un integer divider/square rooter mapeado en memoria
  • Ayudaba en cálculos 3D, ya que el procesador ARM no tenía FPU ni divisor por hardware
  • Sin embargo, el dato clave de la pregunta es que no era una instrucción nativa del procesador

Harris RTX 2000 y RTX 2010

• El RTX 2000 Forth CPU de Harris se menciona como un caso que ofrecía una instrucción de square root en varias etapas
• Su sibling de grado militar, el RTX 2010, también ofrecía funciones de la misma familia
• Como material relacionado se enlaza Stack Computers: RTX 2000
• Según el RTX2000 Family Programmer’s Reference Manual, esta función se parece más a una square root iterativa: ejecuta 1 instrucción de setup y 15 instrucciones step para obtener el valor final
• También se menciona “A Fast Method for Finding an Integer Square Root”, de Ken Lyons, como material que trata la implementación en hardware y ejemplos de programación para la familia RTX2000

La divider/square-rooter unit de ENIAC

• ENIAC, en 1946, también corresponde a un caso de hardware para raíz cuadrada entera
• Según la descripción citada, ENIAC controlaba 4 acumuladores mediante una multiplier unit especial para realizar hasta 385 multiplicaciones por segundo
• Otros 5 acumuladores eran controlados por una divider/square-rooter unit especial, que procesaba hasta 40 divisiones o 3 operaciones de raíz cuadrada por segundo
• Los acumuladores de ENIAC operaban como enteros decimales

Por qué es difícil implementar raíz cuadrada entera

• Una respuesta explica como método eficiente para calcular square root obtener primero la raíz cuadrada inversa mediante iteración de Newton-Raphson y luego multiplicarla por el valor original
• Este enfoque se conoce como “Quake method”, y en CPU y GPU modernas se ha generalizado mediante instrucciones de estimación inicial e instrucciones de iteración
  • Ej.: frsqrte de ARMv8
  • Ej.: frsqrts de ARMv8
• La restricción central de este enfoque es que requiere un multiplier rápido
  • La sqrt de punto flotante requiere un FP multiplier rápido, y las FPU lo tienen
  • La sqrt entera requiere un integer multiplier rápido, pero históricamente la mayoría de las CPU no tenían ese hardware, según la explicación
  • Para lograr suficiente precisión, también se agrega la condición de necesitar un multiplier rápido con el doble del ancho de la entrada
• Como los requisitos de precisión no siempre son iguales, separar estimación e iteración, como hacen frsqrte y frsqrts, permite ajustar la cantidad de iteraciones al compromiso entre velocidad y exactitud deseado

Técnica de Quake y debate sobre implementaciones modernas de sqrt

• Otra respuesta refuta la idea de que el truco de Quake sea el más eficiente, señalando que hace mucho dejó de ser cierto y que solo aplica cuando se busca un resultado float de baja calidad en hardware específico
• Explica que en chips modernos las instrucciones sqrt nativas son mucho más rápidas, a menudo del orden de unos pocos ciclos de reloj
• Como método más rápido, se propone almacenar una tabla de valores con intervalos no uniformes, traer rápidamente dos valores para interpolar, desplazar el exponent base-2 y, si hace falta, aplicar una iteración mejor que Newton-Raphson
• La familia de métodos de Halley y varios métodos iterativos pueden converger más rápido que Newton-Raphson, pero la velocidad real depende del costo de cada operación
• Para rangos solo de enteros, por ejemplo 2^32, la misma idea puede aplicarse en punto fijo
  • Como método simple para hardware se propone divide and conquer
  • Cada bloque de 8 bits puede mapearse a una tabla de 256 valores de punto fijo, hacerse una consulta paralela y luego realizar 2 de 3 multiplicaciones en paralelo para obtener un valor de 32 bits y truncarlo
• La investigación sobre optimización de sqrt continúa, y se presenta como ejemplo este material de INRIA HAL

[GN⁺]

Comentarios en Hacker News

• AArch64 NEON tiene la instrucción URSQRTE, así que está más cerca de la pregunta original de lo que parece.
  Si se interpreta un valor de 32 bits como un entero de punto fijo con 32 bits fraccionarios, el rango representable va de 0 a 1-ε en intervalos uniformes, donde ε=2^-32.
  URSQRTE calcula una raíz cuadrada inversa aproximada, luego la divide entre dos y ajusta el resultado al rango de 0 a 1-ε.
  Un entero de punto fijo no es estrictamente un entero, y una raíz cuadrada inversa aproximada tampoco es una raíz cuadrada, pero se puede llegar bastante cerca.
  La instrucción relacionada FRSQRTE es mucho más común y ofrece una raíz cuadrada inversa aproximada para coma flotante de 32 bits.

  • Me da curiosidad qué tipo de trabajo produce suficiente beneficio como para merecer una instrucción así de compleja en AArch64, aun cuando se puede descomponer fácilmente en instrucciones más simples.

• Si la pregunta es si puede hacerse en un solo ciclo de reloj, con una tabla de consulta enorme sí se podría.
  Dependiendo de cuántas compuertas lógicas en serie puedan ejecutarse dentro del ciclo de reloj, quizá también se podría reducir el tamaño.
  Por ejemplo, la raíz cuadrada binaria de 10000 se parece bastante a la raíz cuadrada de 100, y podría decirse que solo cambia la cantidad de ceros.

  • Las instrucciones de estimación de raíz cuadrada inversa en coma flotante (frsqrte) normalmente se implementan justo así, con una búsqueda en tabla indexada por algunos bits de la mantisa y el bit menos significativo del exponente.
    La precisión suele andar más o menos al nivel de bf16 (ARM, RISC-V) o fp16 (x86), así que si hace falta más precisión, luego se hacen unas cuantas iteraciones de Newton-Raphson.
  • Si el número de bits de entrada es n, la raíz cuadrada entera puede calcularse con n/2 iteraciones usando solo desplazamientos y sumas.
    En cada paso se determina si debe encenderse un nuevo bit en el resultado calculando n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2)).
    Luego se compara con el operando original y, si es menor o igual, 1) se activa el bit en el resultado y 2) se actualiza n2_old a n2_new.
    Con un conjunto adecuado de instrucciones microcodificadas y una ALU, esto podría hacerse en n/2 o quizá n ciclos de reloj, y con más optimización se puede reducir n hasta el índice del bit más a la izquierda encendido en el operando.
  • Puede que sea una pregunta tonta, pero ¿de verdad una búsqueda en una tabla grande puede terminar en un solo ciclo de reloj?
    Si la tabla es grande, habría que traerla de memoria, y entonces uno imaginaría latencias de caché y de la jerarquía de memoria, ¿no?
  • Viéndolo así, suena como si cualquier algoritmo del mundo pudiera ejecutarse en 1 ciclo de reloj.
  • La raíz cuadrada entera no está tan mal, porque basta con guardar N^0.5 entradas en una tabla de mayor/menor.
    Básicamente, almacenar N^2 para cada respuesta N.
    Es viable para enteros de 16 bits, quizá también para 32 bits, pero no para 64 bits.

• Si ampliamos la definición de “procesador” hasta incluir dispositivos electromecánicos, la Friden SRQ podía calcular raíces cuadradas usando solo suma y desplazamientos, sin un solo componente electrónico aparte del motor.
  Había que ajustar manualmente la posición del punto decimal, así que técnicamente también podría considerarse una operación entera.
  Video: https://youtu.be/o44a1ao5h8w

• ¿No se puede obtener la raíz cuadrada entera de cualquier entero usando la secuencia 1 + 3 + 5 + ... + 2k + 1?
  Básicamente sería encontrar el k del término más cercano que sea menor o igual que mi número.

  • ¿Puedes explicar la idea?
    Como definición del algoritmo está bien, pero si se implementa de forma ingenua es lentísimo incluso para números de 32 bits.
    A ese punto, una búsqueda binaria sería muchísimo más rápida.
  • Una mejor forma quizá sea usar el desarrollo (x+y)^2=x^2+2xy+y^2, junto con la observación de que en cualquier base la raíz cuadrada de un número de 2n dígitos tiene como máximo n dígitos.
    Es lo mismo que el método común para calcular raíces cuadradas a mano con papel y lápiz.
    Si esto se procesa de 8 bits en 8 bits, solo hace falta una tabla de consulta para la raíz cuadrada de números de 8 bits.
  • Si la idea es iterar toda esa secuencia, entonces tomaría tiempo exponencial respecto a la longitud en bits de la entrada.
  • Este es uno de esos trabajos típicos vergonzosamente fáciles de paralelizar.

• Me dio risa esta parte de una respuesta más abajo:

  My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
  Es un buen recordatorio de que, si escribes código demasiado listo, luego puede que ya no recuerdes cómo funciona.

• Hay que bajar un poco más para leerlo, pero que la respuesta sea ENIAC es realmente gracioso.

  • Mucha gente cree que todo lo anterior a su entrada a la escuela era primitivo y apenas funcionaba :)
    Basta leer un poco para ver que es exactamente al revés.
    La mayoría de las ideas inteligentes de hoy ya se usaban en computadoras de los años 1940–60 y ahora se reciclan en nuevos chips semiconductores.
    Ahí entran cosas como el pipeline, la ejecución fuera de orden y los multinúcleo.
    Puede que el hardware antiguo fuera algo “tosco”, pero en arquitectura se usaban técnicas muy ingeniosas.

• 2 ^ (1/2 * Log2(X)) = sqrt(X)
  Si conviertes Log2(x) en contar ceros a la izquierda, obtienes una aproximación realmente burda.
  Si aproximas mejor Log(2), puedes acercarte más a la respuesta.

• Si no necesitas una respuesta exacta al entero más cercano sino una aproximación muy burda, basta con hacer un desplazamiento a la derecha por la mitad de la posición del bit 1 más significativo.
  Casi todos los procesadores tienen instrucciones de desplazamiento, y también parecen bastante comunes instrucciones como FLO (Find Leading One) o FFS (Find First Set).
  Para algunos usos, una aproximación tan burda puede ser tan útil como la respuesta exacta.
  Por ejemplo, cuando solo necesitas un valor inicial razonable para iteraciones posteriores de Newton-Raphson.
  Claro, el truco del desplazamiento a la derecha también sirve como valor inicial para un cálculo más preciso de raíz cuadrada :P

  • ¿Es aquí donde entra la referencia a DOOM?
    Ya es una historia bastante conocida de internet, con Carmack y un número mágico de 32 bits.
  • Como dato curioso, FFS y su generalización FNS están en CUDA: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
    Otro intrínseco de hardware de CUDA que personalmente me gusta es log2.

• Si no recuerdo mal, la mayoría, o quizá todos, los DSP de punto fijo tienen una instrucción de raíz cuadrada o alguna instrucción auxiliar relacionada.

• Un análisis exhaustivo de algoritmos de raíz cuadrada que podría resultar medio relacionado e interesante para fans del 6502: https://github.com/TobyLobster/sqrt_test