# How do you do operations on large numbers using a small fixed-width ALU?

I am wanting to design a simple calculator like what you would find in the dollar store. Something like this:

This little guy can display a number 8 digits long, meaning 99999999 is the largest number that can be displayed in this format.

I am familiar with how a simple ALU works with two registers as input.

Now, if I where to use a 32bit register for calculations, then everything would be OK since the register can hold 99999999 just fine. However, I want to understand the process of using two smaller registers to hold bigger numbers and how that works with an ALU?

• Do you want it to be able to handle floating point calculations, or only fixed point, or only integers? – Jerry Coffin Nov 3 '14 at 15:01
• Long run, floating point, but for this question just integers would be fine. I know with decimal points and binary there is an endless number of ones and zeros that could be had, depending on how accurate you want to be. ALUs that support decimals is not something I am familiar with yet. – Jake Robinson Nov 3 '14 at 15:35
• The general term for a number larger than your ALU, especially one of variable length, is a "bignum". Some programming languages implement this for you. – pjc50 Nov 3 '14 at 16:20
• It's just like doing arithmetic with pencil and paper: work on one digit at a time and keep track of the carries/borrows. – Pete Becker Nov 3 '14 at 16:21
• Yep, just like with a pencil and paper. Divide can get ugly, but the rest is fairly straight-forward. (You do, of course, need some extra storage to store the full-sized numbers, plus intermediate results.) – Hot Licks Nov 3 '14 at 18:39

You can manipulate arbitrarily wide numbers using a finite width ALU. However, multiple operations are required when the number is wider than the ALU.

To illustrate this, I'll use a PIC 18 as example. This architecture can manipulate only 8 bit numbers directly. To add the 8 bit quantities VAR1 and VAR2 and put the result into SUM would take code like this (assuming banking isn't needed or the bank is already properly set up):

         movf    var1, w     ;get VAR1 into accumulator
movwf   sum         ;save the result

If instead VAR1, VAR2, and SUM were 32 bit variables, the code would be:

         movf    var1+0, w   ;make byte 0 (low byte)
movwf   sum+0
movf    var1+1, w   ;make byte 1
movwf   sum+1
movf    var1+2, w   ;make byte 2
movwf   sum+2
movf    var1+3, w   ;make byte 3 (high byte)
movwf   sum+3

Each byte is handled separately. Note the use of ADDWFC instead of ADDWF for all but the first byte. This instruction adds the two bytes but also adds the carry from the previous ALU operation.

Hopefully you can see that this approach can be used to add two arbitrarily large numbers. Wide arithmetic is possible, just that it takes longer and requires multiple trips thru the ALU to perform the whole operation.

Operations like AND, OR, XOR, etc, are bit-wise independent. Each output bit can be computed given only the corresponding input bits. Such operations scale linearly with the width of the values being processed. Addition requires the two input bits but also the result of the carry from the next lower bit. That requires one bit of state to be kept between successive operations, but still scales linearly with the width of the number.

Multiply scales with the square of the width of the number since each chunk of one number must be multiplied by all chunks of the other number. Multiplying two 32 bit numbers, which can produce up to a 64 bit result, takes a lot longer than 8 x 8 on a 8 bit ALU, but it's all possible.

You would generally make such a calculator with a 4-bit ALU (one BCD digit) and do all calculations in BCD one digit at a time, so your storage register would be 8 digits x 4 bits = 32 bits total.

Even with a low clock frequency, that's more than fast enough for human interaction, and it will minimize the hardware.

To add you just add one digit at a time, from right to left, until you have done all 8 (taking carries into account). Subtraction is similar.

Multiplication and division are basically repeated addition or subtraction and can be done similarly (you might have to add 9 * 9 * 8 times with a 4-bit ALU to do 8 digit x 8 digit multiplication- worst case - 99999999 * 1, for example.

The result, being in BCD, can be sent almost directly to the LCD display (7-segment coding and perhaps triplex LCD driving notwithstanding).

Of course you can do this sort of thing more easily these days by using a 32-bit ALU and writing code using assembler hand coding of the math, doubles in C etc. but that's not how the cheap calculators work.