¿Cómo puede una CPU de 8 bits calcular números grandes?

Question

Estoy tratando de diseñar un instructivo de CPU de 8 bits en Logisim. Es posible calcular números grandes con una CPU de 8 bits?

En un ordenador de 32 bits se pueden calcular números mayores de 32 bits, creo que es un truco de software pero ¿quién me puede explicar cómo funciona?

Answer 1

Ciertamente, es posible trabajar con números muy grandes incluso en ordenadores de 8 o 4 bits. No es muy eficiente, pero es posible. La forma de hacerlo es operando sobre los números por partes, con el apoyo de instrucciones específicas del procesador.

Un microcontrolador común de 8 bits es la serie Atmel AVR. Para sumar números de 8 bits, utiliza una instrucción llamada ADD. Esta instrucción se utiliza para sumar dos valores de registro. Por ejemplo, puedes hacer

LDI R16, 5
LDI R17, 10
ADD R16, R17
; R16 = 15

para sumar R16 y R17 y poner el resultado en R16. Para sumar números de 16 bits, básicamente se hace esto varias veces. Sin embargo, hay una trampa: el bit de acarreo. Otra instrucción del AVR es ADC, para ADd con carry. Esto hace exactamente lo mismo que ADD, pero también añade la bandera de acarreo. Tanto ADD como ADC activarán la bandera de acarreo si la operación de suma se desborda. Por ejemplo, si suma 128 a 128, obtendrá 0 como resultado con la bandera de acarreo activada. Si llama a ADC con la bandera de acarreo activada, añadirá 1 al resultado. Este es un ejemplo de suma de 16 bits:

LDI R16, 232
LDI R17, 3
; R17:R16 = 1000
LDI R18, 208
LDI R19, 7
; R19:R18 = 2000
ADD R16, R18
ADC R17, R19
; R16 = 184
; R17 = 11
; R17:R16 = 3000

Esto se puede repetir tantas veces como sea necesario para sumar números grandes. Tenga en cuenta que se requiere una pequeña cantidad de lógica para apoyar esto: la capacidad de alimentar la bandera de acarreo en la entrada de acarreo del sumador.

Un proceso similar puede utilizarse para multiplicar números. Realizar multiplicaciones de 16 bits en un procesador de 8 bits requiere 4 multiplicaciones de 8 bits y varias sumas. El procedimiento es exactamente el mismo que el de multiplicar números a mano un dígito cada vez, excepto que se utilizan bytes en lugar de dígitos. Tendrá que multiplicar los cuatro pares de bytes posibles y luego sumarlos según sus valores de posición. Ejemplo en el ASM del AVR:

LDI R16, 232
LDI R17, 3
; R17:R16 = 1000
LDI R18, 208
LDI R19, 7
; R19:R18 = 2000
MUL R16, R18
; R1:R0 = R16*R18 (1s place product)
MOVW R3:R2, R1:R0
; R3:R2 = R16*R18
MUL R16, R19
; R1:R0 = R16*R19 (256s place product #1)
CLR R4
ADD R3, R0
ADC R4, R1
; R4:R3:R2 = R16*R18 + 256*R16*R19
MUL R17, R18
; R1:R0 = R17*R18 (256s place product #2)
ADD R3, R0
ADC R4, R1
; R4:R3:R2 = R16*R18 + 256*(R16*R19+R17*R18)
MUL R17, R19
; R1:R0 = R17*R19 (65536s place product)
CLR R5
ADD R4, R0
ADC R5, R1
; R5:R4:R3:R2 = R16*R18 + 256*(R16*R19+R17*R18) + 65536*R17*R19
; R5:R4:R3:R2 = 2000000

Te darás cuenta de que es exactamente como se trabaja con los números a mano en papel, pero en lugar de trabajar con dígitos de base 10, la CPU trabaja con bloques de bits del tamaño de una palabra, en este caso, 8 bits.

Si se utiliza una CPU que puede trabajar con más bits a la vez, el trabajo con números grandes resulta más fácil, ya que requiere menos instrucciones. Sin embargo, se pueden utilizar las mismas técnicas para trabajar con números más grandes que los que admite el conjunto de instrucciones directamente.

Answer 2

Como has dicho, las CPUs de 32 bits pueden manejar números mayores de 32 bits, así que ¿por qué no podría hacerlo una CPU de 8 bits?

Si se suman dos números, se empieza por el último bit de ambos. Si uno de ellos es 1, el resultado es 1, si ambos son 1, el resultado es 0, y hay que llevar un 1 al cálculo del segundo bit.

Para el segundo bit, tienes los dos bits de los números y el bit transportado. Si uno o los tres son 1, el resultado es 1. Si dos o todos son 1, de nuevo hay que llevar un 1 al cálculo del tercer bit.

Esto se suele hacer en hardware, es decir, hay puertas lógicas, sólo hay que poner los números en las entradas y obtener la salida. Ten en cuenta que si tienes un sumador de 8 bits, también obtienes el llamado bandera de arrastre de la adición de los 8 bits.

Si sólo estás sumando dos números de 8 bits, la bandera de acarreo sólo indica si el resultado es mayor que 255, el mayor número que puede contener un entero de 8 bits (sin signo).

Si tienes números más grandes, ahora empiezas a sumar los bits del segundo byte, y tienes en cuenta la bandera de acarreo de la suma anterior durante la suma del primer bit de este byte.

La única diferencia es que una CPU de 32 bits puede sumar 32 bits de una sola vez, por lo que sumar números de 64 bits consta de dos pasos, mientras que una CPU de 8 bits necesita 8 pasos.

De esta manera, puedes añadir números de cualquier tamaño en cualquier CPU. El resto de las matemáticas se hacen de forma similar, la CPU más pequeña sólo necesita más pasos.

Answer 3

Cuando sumas dos números con lápiz y papel, trabajas de derecha a izquierda, sumando dos dígitos, registrando el resultado y llevando cualquier exceso. La suma de números grandes en un ordenador funciona de la misma manera. Cada número está representado por un conjunto de "dígitos" donde cada "dígito" es una palabra de ordenador: 8 o 32 bits de ancho en tus dos ejemplos. Cuando se suman dos números de este tipo, es exactamente el mismo proceso: sumar dos "dígitos", registrar el resultado y llevar cualquier desbordamiento. La diferencia es que cada dígito representa un valor entre 0 y 2^8 (para un procesador de 8 bits), o un valor entre 0 y 2^32 (para un procesador de 32 bits). Si te sientes cómodo pensando en términos de bases numéricas, la suma con lápiz y papel funciona en base 10, y la suma con ordenador de alta precisión funciona en base 2^8 o 2^32 (o lo que mejor se adapte al procesador).