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

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

En una computadora de 32 bits se pueden calcular números mayores a 32 bits, creo que es un truco de software pero quien me puede explicar como funciona?

8 bits a la vez.
En la escuela aprendiste los dígitos del 0 al 9, pero apuesto a que sabes contar más allá de eso e incluso hacer algunos cálculos básicos. Pregúntese cómo maneja eso, porque los 'dígitos' pueden ser diferentes, pero el método es exactamente idéntico. La magia de la que probablemente no eras consciente es el noveno bit 'oculto' en la unidad aritmética llamada 'carry'-flag.

Respuestas (3)

Ciertamente es posible trabajar con números muy grandes incluso en computadoras de 8 o 4 bits. No es muy eficiente, pero es posible. La forma de hacerlo es operando sobre los números en piezas, 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 juntos. 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 lo haces varias veces. Sin embargo, hay una trampa: el bit de acarreo. Otra instrucción AVR es ADC, para ADd con Carry. Esto hace exactamente lo mismo que ADD, pero también agrega la bandera de acarreo. Tanto ADD como ADC establecerán la bandera de acarreo si la operación de adición se desborda. Digamos, si agrega 128 a 128, obtiene 0 como resultado con la bandera de acarreo establecida. Si llama a ADC con la bandera de acarreo establecida, agregará 1 al resultado. Aquí hay un ejemplo de adición 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 admitir esto: la capacidad de alimentar la bandera de acarreo en el acarreo del sumador.

Se puede usar un proceso similar 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 multiplicar números a mano, un dígito a la vez, excepto que usa bytes en lugar de dígitos. Deberá multiplicar los cuatro pares de bytes posibles y luego sumarlos de acuerdo con sus valores posicionales. Ejemplo en AVR ASM:

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

Notará que así es exactamente como trabaja con 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 usa una CPU que puede trabajar con más bits a la vez, entonces trabajar con números grandes se vuelve más fácil ya que requiere menos instrucciones. Sin embargo, puede usar las mismas técnicas para trabajar con números más grandes que los que admite directamente el conjunto de instrucciones.

Editar: el compilador AVR GCC contiene un código ensamblador que utilizará para varias operaciones comunes, como la multiplicación y la división, que puede ser una buena referencia sobre cómo se hace este tipo de cosas: https://github.com/gcc-mirror /gcc/blob/master/libgcc/config/avr/lib1funcs.S . Creo que mi multiplicación de 16x16 a 32 debería ser equivalente a __umulhisi3.

Tengo una pregunta tardía con respecto a su respuesta. Por lo tanto, agregar números que resulten en un valor mayor a 255, o desbordar los 8 bits, hará que se establezca la bandera de acarreo y se reinicie el conteo desde cero nuevamente. Entonces, la bandera de acarreo nos dice cuándo el número es mayor que 255, pero ¿cómo almacena estos números más grandes asumiendo registros y memoria de 8 bits?
La bandera de acarreo actúa efectivamente como un noveno bit. Sumar 8 bits más 8 bits da como resultado un resultado de 9 bits, los 8 bits inferiores terminan en el registro de salida y el noveno bit va en la bandera de acarreo. Entonces, cómo almacena eso depende de lo que esté haciendo. En la mayoría de los casos, TBH, en realidad no lo almacena. O usa el bit de acarreo en la siguiente instrucción (agregar con acarreo), o tal vez lo verifica como parte de una verificación de desbordamiento. Si desea almacenarlo, simplemente puede copiar el bit de acarreo en un segundo byte para tener un número de 16 bits.
Ok, sí, esto tiene sentido. Aunque dos preguntas más.......
1- Digamos que haces un cálculo que resultó en un valor de 16 bits, como 42000 y se almacena en 2 bytes secuenciales en la memoria. ¿Cómo sabe el procesador que el número se mantiene en dos bytes y no solo en un byte, ya que es una máquina de 8 bits? O si usa un procesador antiguo basado en RISC y programa en ensamblador, ¿depende del programador saber que hay un número de 16 bits allí y tener cuidado al escribir software para tener eso en cuenta?
2- Lo mismo que cuando se usa la instrucción add-with-carry (ADC). ¿Depende del programador saber cuándo usar esta instrucción en comparación con la instrucción ADD? ¿Supongo que los compiladores modernos hacen esto por nosotros hoy en día?
1: en general, si se trata de una CPU de 8 bits, básicamente, por definición, no tiene forma de saber nada más grande que 8 bits. Así que no importa si están en bytes adyacentes o no, la organización depende del programador y/o del compilador. Lo mismo ocurre con los registros: ni siquiera necesita usar registros adyacentes de 8 bits para valores de 16 bits. Pero, por lo general, las convenciones de llamadas especifican que deben ser adyacentes, ya que eso facilita las cosas.
2 - si estás escribiendo en ensamblador, sí. Si está escribiendo en C, el compilador se encargará de esto. Todo lo que necesita hacer como programador es usar los tipos correctos y el operador +.
Ok, sí, cualquier ubicación de almacenamiento se puede usar para valores de >8 bits siempre que sepa dónde están. Pero a partir de la pregunta 1, los cumplidores también eliminan la necesidad de que el programador tenga que preocuparse por dónde se almacenan en la memoria. En lenguajes de alto nivel como C, el programador puede simplemente declarar un valor de 16 bits y usar el operador + sin pensarlo.
Ejemplo: godbolt.org/z/nvjqbY1vv . El compilador no hizo un muy buen trabajo optimizando el código incluso en O3, lo que parece extraño (parece que hay muchos registros de valor cero). Y la multiplicación llama a __mulsi3 desde github.com/gcc-mirror/gcc/blob/master/libgcc/config/avr/… .
Ah esto es interesante. Gracias Alex, he aprendido mucho de esta discusión.
@alex.forencich FYI/FWIW, y AFAIK: GCC optimiza la representación intermedia (GIMPLE), antes de traducir a la salida final (AVR, etc.). En términos generales, AVR se trata como una máquina de 16 bits (avr-gcc intes de 16 bits), implementada casi con macros que se expanden a instrucciones nativas. De ahí la optimización bastante pobre en la asignación de registros, mezclando cosas (extensión de signo, desplazamiento de bytes) y aritmética (16x16+ mul/div, etc.).
Lo cual es relevante para la conversación actual: las matemáticas "largas" simplemente se realizan con la elección adecuada de encantamientos mágicos. Casi no importa a qué se expandan esas macros, siempre que hagan lo que dice en el cuadro; Da la casualidad de que hacer aritmética de 16 bits en AVR es bastante simple, por lo que tienden a ser breves (un par de instrucciones). En un nivel más general, cualquier computadora universal puede hacer lo mismo, aunque la universalidad no ofrece garantías de tiempo de ejecución (!!).

Como dijiste, las CPU de 32 bits pueden manejar números mayores de 32 bits, entonces, ¿por qué una CPU de 8 bits no debería poder hacer esto?

Si sumas dos números, comienzas con 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 llevado. Si uno o los tres son 1, el resultado es 1. Si dos o todos son 1, nuevamente debe llevar un 1 al cálculo del tercer bit.

Esto generalmente se hace en hardware, es decir, hay puertas lógicas, simplemente coloca los números en las entradas y obtiene la salida. Tenga en cuenta que si tiene un sumador de 8 bits, también obtiene la llamada bandera de acarreo de la suma de los 8 bits.

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

Si tiene números más grandes, ahora comienza a agregar los bits del segundo byte y tiene en cuenta la bandera de acarreo de la adición anterior durante la adición del primer bit de este byte.

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

De esta manera, puede agregar números de cualquier tamaño en cualquier CPU. Todas las demás matemáticas se hacen de manera similar, la CPU más pequeña solo necesita más pasos.

Agregar números de cualquier tamaño está restringido por la memoria RAM disponible. Si tiene 1 KB para un procesador de 8 bits, incluso es posible agregar dos números de 1024 bits, pero para números de 4096 bits necesita más RAM.

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 desbordamiento. Sumar números grandes en una computadora funciona de la misma manera. Cada número está representado por un conjunto de "dígitos" donde cada "dígito" es una palabra de computadora: 8 o 32 bits de ancho en sus dos ejemplos. Cuando se suman dos de esos números, 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 se siente cómodo pensando en términos de bases numéricas, la suma con lápiz y papel funciona en base 10,

¿Cómo puede una CPU de 8 bits calcular números grandes?
RespuestasAquíPolítica de privacidad1y, 0v