6
\$\begingroup\$

I'm trying to design an instructable 8-bit CPU in Logisim. Is it possible to calculate big numbers with an 8-bit CPU?

In a 32-bit computer, you can calculate numbers bigger than 32-bit, I think it's a software trick but who can explain to me how it works?

\$\endgroup\$
  • 8
    \$\begingroup\$ 8 bits at a time. \$\endgroup\$ – Ignacio Vazquez-Abrams Apr 23 '15 at 5:36
  • 16
    \$\begingroup\$ In school you learned the digits 0-9, but I bet you know how to count further than that and even do some basic calculations top of mind. Ask yourself how you manage that, because the 'digits' may be different, but the method is exactly identical. The magic that you were probably not aware of is the 'hidden' 9th bit in the arithmetic unit called 'carry'-flag. \$\endgroup\$ – jippie Apr 23 '15 at 6:56
15
\$\begingroup\$

It's certainly possible to work with very large numbers even on 8 bit or 4 bit computers. It's not very efficient, but it's possible. The way this is done is by operating on the numbers in pieces, with the support of specific processor instructions.

A common 8 bit microcontroller is the Atmel AVR series. To add 8-bit numbers, it uses an instruction called ADD. This instruction is used to add two register values together. For example, you can do

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

to add R16 and R17 and put the result in R16. To add 16-bit numbers, you basically just do this multiple times. However, there is a catch: the carry bit. Another AVR instruction is ADC, for ADd with Carry. This does exactly the same thing as ADD, but it also adds the carry flag. Both ADD and ADC will set the carry flag if the addition operation overflows. Say, if you add 128 to 128, you get 0 as a result with the carry flag set. If you call ADC with the carry flag set, it will add 1 to the result. Here is an example 16-bit addition:

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

This can be repeated as many times as necessary to add large numbers. Note that a small amount of logic is required to support this: the ability to feed the carry flag into the carry in of the adder.

A similar process can be used to multiply numbers. Performing 16-bit multiplications on an 8-bit processor requires 4 8-bit multiplications and several additions. The procedure is exactly the same as multiplying numbers by hand one digit at a time, except you use bytes instead of digits. You will need to multiply all four possible byte pairings, then add them according to their place values. Example in 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

You'll notice that this is exactly how you work with numbers by hand on paper, but instead of working with base 10 digits, the CPU works with word sized blocks of bits - in this case, 8 bits.

If you use a CPU that can work with more bits at a time, then working with large numbers gets easier as it requires fewer instructions. However, you can use the same techniques to work with larger numbers than the instruction set supports directly.

|improve this answer|||||
\$\endgroup\$
6
\$\begingroup\$

As you said, 32bit CPUs can handle numbers larger than 32 bit, so why shouldn't a 8bit CPU be able to do this?

If you add two numbers, you start with the last bit of both. If one of them is 1, the result is 1, if both are 1, the result is 0, and you have to carry a 1 to the calculation of the second bit.

For the second bit, you have the two bits of the numbers and the carried bit. If one or all of the three are 1, the result is 1. If two or all are 1, you again have to carry a 1 to the calculation of the third bit.

This is usually done in hardware, i.e. there are logic gates, you just put the numbers on the inputs and get the output. Note that if you have an 8 bit adder, you also get the so called carry flag from the addition of the 8th bits.

If you're just adding two 8bit numbers, the carry flag just indicates if the result is larger that 255, the largest number a 8 bit (unsigned) integer can hold.

If you have larger numbers, you now start to add the bits of the second byte, and take into account the carry flag from the previous addition during the addition of the first bit of this byte.

The only difference is that a 32bit CPU can add 32bits in one go, so adding 64 bit numbers consists of two steps, while a 8bit CPU needs 8 steps.

This way, you can add numbers of any size on any CPU. All the other math is done similar, the smaller CPU just needs more steps.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Adding numbers of any size is restricted by the available RAM. If you have 1 KB for a 8 bit processor even adding two 1024 bit numbers is possible, but for 4096 bit numbers you need more RAM. \$\endgroup\$ – Uwe Aug 3 '16 at 10:21
2
\$\begingroup\$

When you add two numbers with pencil and paper you work from right to left, adding two digits, recording the result, and carrying any overflow. Adding large numbers on a computer works the same way. Each number is represented by a set of "digits" where each "digit" is a computer word: 8 or 32 bits wide in your two examples. When two such numbers are added, it's exactly the same process: add two "digits", record the result, and carry any overflow. The difference is that each digit represents a value between 0 and 2^8 (for an 8-bit processor), or a value between 0 and 2^32 (for a 32-bit processor). If you're comfortable thinking in terms of number bases, pencil-and-paper addition works in base 10, and high-precision computer addition works in base 2^8 or 2^32 (or whatever else suits the processor best).

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.