Tiene dos números binarios de tamaño n cada uno, ¿cuántas operaciones se necesitan para sumarlos?

Depende de lo que quiere decir con “operación”. En todas las arquitecturas de procesador, hay soporte de hardware para agregar números hasta el tamaño de palabra de la máquina. Además, puede haber sumadores especializados para algunos múltiplos del tamaño de la palabra. AMD [1], por ejemplo, proporciona ADC primitivo y ADD para agregar con y sin transporte, respectivamente, para operandos de tamaño mixto de 8, 16, 32 y 64 bits. También hay instrucciones especiales extendidas que funcionan en los tipos de vector 128b y 256b.

Un sumador de hardware, que se invoca mediante estas instrucciones, funciona de manera efectiva instantáneamente: es un conjunto de puertas lógicas paralelas que acepta todos los bytes de ambos operandos simultáneamente, y por la operación de la lógica booleana, no puede ayudar de inmediato (sujeto a un retraso físico de carga propagación en los transistores constituyentes) hace que la suma aparezca en el estado de salida.

La forma más rápida de sumar un número de longitud arbitraria es dividir la operación en adiciones que pueden llevarse a cabo mediante instrucciones de hardware en su procesador, realizar esas adiciones y combinarlas de acuerdo con el algoritmo [2] que utilizó para obtener su resultado final . En cualquier caso, la operación compuesta no dependerá de la cantidad de bits, sino de la cantidad de “fragmentos” en los que necesita dividir la suma. En ningún caso agregará iterativamente bits individuales.

Notas al pie

[1] https://support.amd.com/TechDocs …

[2] ¿Cómo usar números grandes?

La forma más rápida de sumarlo es mediante un sumador de suma condicional o un sumador de prefijo paralelo (AKA carry-lookahead adder). El CSA se puede explicar mejor usando una boda. Imagine que tiene dos cónyuges potenciales, pero no sabrá con cuál se casa hasta poco antes del día de la boda. Obviamente, para cuando sepa con quién se casará, será demasiado tarde para planificar la boda, escribir las invitaciones, etc.

Entonces, ¿Qué haces? Prepara ambas bodas mientras aún espera la decisión. Luego, cuando sepa con cuál de los dos se casará, simplemente tira las invitaciones de la otra boda.

Un CSA funciona de la misma manera: agrega la mitad superior de los números una vez con un acarreo de 1, una vez con un acarreo de 0, y una vez que obtiene el acarreo de la mitad inferior de los números (calculados en paralelo) arroja lejos el cálculo que usó el carry incorrecto.

Un sumador de prefijo paralelo es un poco más complicado, pero utiliza la observación de que puede calcular si un índice tiene un acarreo en función de si siempre genera un acarreo (si agrega 1 y 1) o si propaga un acarreo (si está agregando 1 + 0 o 0 + 1, una transferencia de 0 da una transferencia de 0 y una transferencia de 1 da una transferencia de 1) y una transferencia viene desde abajo. Ahora calcula en paralelo si cada bit se genera o propaga utilizando un circuito de prefijo paralelo.

Ambos solo requieren un número logarítmico de capas. En el CSA, cada capa es un multiplexor, más una capa de sumadores completos en la parte superior;
en el PPA, cada capa es un circuito de anticipación un poco más complejo.

Dependiendo de su modelo de puerta, uno u otro será un factor constante más rápido.

La clara ventaja del PPA sobre el CSA es su costo lineal; la CSA está más cerca de la cuadrática. Esto se debe al hecho de que en cada nivel de recursión, el CSA usa 3 CSA más pequeños: dos para las mitades superiores y uno para la mitad inferior.

Si desea ir por el circuito que requiere la menor cantidad de operaciones, debe usar el sumador de cadena de transporte. Este se construye simplemente conectando un sumador completo para cada bit de las entradas y encadenando los acarreos.

Es lineal en retraso, pero también solo utiliza una cantidad lineal de puertas. El número de puertas utilizadas es, si mal no recuerdo, aproximadamente la mitad del número de puertas del PPA. El número de puertas es exactamente 5 veces el número de bits, entonces $5n$. Que yo sepa, este es también el número mínimo de operaciones para la adición (en un modelo de hardware básico con y, o, nand, etc.).

Si está interesado en una explicación detallada sobre cómo construir estos sumadores y cómo saber que realmente funcionan, asegúrese de consultar Arquitectura del sistema: una disciplina de ingeniería ordinaria. Va desde las puertas hasta su pequeño sistema operativo, incluido el diseño de un lenguaje tipo C con ensamblador en línea y un compilador para ese lenguaje.

No puede sumar dos números [math] n [/ math] -bit en operaciones menores que [math] n [/ math], ya que debe leer al menos cada bit. Si una operación básica es agregar tres bits (dos de las entradas y una posible transferencia) y producir una suma y una transferencia, entonces realmente necesita exactamente operaciones [matemáticas] n [/ matemáticas].