(Assembly - 8085) Multiply 32 bit numbers

Question

me and my friend are trying to write a code in which we need to multiply two 32 bit numbers resulting in a 64 bit number. We wanted to multiply the numbers using the add method, the problem is that register can only store 8 bits (16 bits a pair) at a time. We've searched for solutions and it has been hard to find anything really helpful to this situation. Could you give us any hint on how to do this?

Answer 1

Addition is addition, we learned addition in grade school.

 99
+ 1
====

9+1 = 0 carry the one, we do that twice, then get 0+1 = 1

 11
  99
+  1
====
 100

Doesnt matter what base, in binary we could have this:

 111
+001
====

same deal, base 2, 1+1 = 0 carry the 1, repeat that until 1+0 = 1

 111
  111
+ 001
=====
 1000

But unlike paper and pencil we have a stronger limit on the number of bits in a computer, but that doesnt in any way change how it works.

I can take the prior problem and divide it into two bit sized registers.

 11 11
  1  11
+ 0  01
===  ==
 10  00

the first one is the low order two bits 11+01 we do the math and get 00 with a carry out of 1. the second operation takes the carry out of the prior operation uses that as a carry in, then we add 01 + 00 with a carry in of 1, and get 10 with a carry out of 0.

Nothing magic there.

Then lets get more fundamental

 01 11 11 10
  0  1  1  1
+ 0  0  0  1
 == == == ==
  1  0  0  0 

we start with the lsbit which is 1+1 with a carry in of 0, so 0+1+1 = 0 with a carry out of 1. That carry out is the carry in of the next column the twos column. Which is the carry in of 1 plus 1 + 0 = 0 with a carry out of 1. the fours column is the same as the twos 1 + 1 + 0 = 0 with a carry out of 1. the eights column is a carry in of 1 + 0 + 0 = 1 with a carry out of 0. Every column works the same three things added together the carry in plus operand a plus operand b then you get a result bit and a carry out bit. You can chain those together as wide as you wish, millions of bits, billions of bits, infinite.

So assembly generally gives you some support here. Your alu tends to have a carry out that tends to go into a carry flag bit in some processor state register. You have your two operands and a result, the intermediate carry outs becoming carry ins are managed in the alu itself and you dont get to see those. Sometimes you have a normal add instruction and another add with carry instruction, where the carry flag is the carry in and then the carry out lands in that carry bit as well so for systems like that you would

add
adc
adc
adc
...

for as wide of a set of values you want usually limited by the amount of memory you have or other similar limitations (number of registers).

If you dont have an add with carry then you have to synthesize that

add
jnc lab0
add #1
lab0:
add
jnc lab1
add #1
lab1:

Some instruction sets only have an add with carry so

clc ; clear carry bit
add
add
add
add
...

I am obviously leaving the registers/operands off of these instructions as they are not important to the "how do I do math greater than the number of bits I have in a register" type of question. As shown above with the 1 and 2 bit math you need to prepare your data and place it in the operands based on the columns you are working on. If you have 8 bit registers and an 8 bit alu then you divide your N bit operands into 8 bit parts, organize them such that you work on the lower bytes first then the next higher order bytes in the second add and so on. Properly chaining your carry out of one stage into the carry in of the next.

Not sure why there was any problem searching for solutions. Grade school math covers the basics of counting and adding and carrying over to the next column, then you take that to the instruction set documentation where it describes the add and if there add with carry. Showing the add operation modifies the carry bit, and the add with carry uses and modifies the carry bit.

Answer 2

Let the two numbers be AA55h and BB22h. We will use the 2nd number as a counter. The ALP is:

LXI B, AA55h LXI D, BB22h; counter LXI H, 0000h; 16bit carry initialization

Start: MOV A,C ADD C MOV C,A

MOV A,B ADC B MOV B,A

JNC Carry INX H Carry: DCX D; decrement counter JNZ Start

;;16 bit carry has been stored in HL pair ;;16 bit result has been stored in BC pair