#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# 8085 program to multiply 20 digits integers

Member Posts: 7
Does anybody know how to multiply 20 digits integers in the 8085? I know that I have to store them in 2 different memory sequences and I can store them in a third one, but I have no idea on how to start it!
Thanx!

• Member Posts: 69
We will need a bit more information from you first. How are the original numbers stored - ASCII, packed BCD or binary? How do you want the product formatted? For decimals, it's just long multiplication in base 10. Multiply by each digit in turn and then add the partial products. You will need a binary multiply routine, as the 8085 doesn't have a MUL instruction. It's easier with binary, because you can extend the binary multiply routine to any number of bits.

: Does anybody know how to multiply 20 digits integers in the 8085? I know that I have to store them in 2 different memory sequences and I can store them in a third one, but I have no idea on how to start it!
: Thanx!
:

• Member Posts: 7
Wow! First of all, thank you very much for replying!

The problem says: "to multiply 2 integers of size 20 digits each (ie: 19837653929987654321 x 90870054781976543975). Let the operands be supplied in 2 sequences of memory locations in any format. The result could be stored in a third sequence of memory. Draw a map of registers and memory space showing changes after the execution of each instruction. Produce machine language of the program."

So, that means that the format doesn't matter. I managed to get a list of the most important instructions and a microprocessor simulator Sim8085... that I don't exacty figured out how to use, as you cannot declare some instructions like "org", or "end". Summarizing: I'm still lost!

: We will need a bit more information from you first. How are the original numbers stored - ASCII, packed BCD or binary? How do you want the product formatted? For decimals, it's just long multiplication in base 10. Multiply by each digit in turn and then add the partial products. You will need a binary multiply routine, as the 8085 doesn't have a MUL instruction. It's easier with binary, because you can extend the binary multiply routine to any number of bits.
:
:
: : Does anybody know how to multiply 20 digits integers in the 8085? I know that I have to store them in 2 different memory sequences and I can store them in a third one, but I have no idea on how to start it!
: : Thanx!
: :
:
:

• Member Posts: 69
: The problem says: "to multiply 2 integers of size 20 digits each (ie: 19837653929987654321 x 90870054781976543975). Let the operands be supplied in 2 sequences of memory locations in any format. The result could be stored in a third sequence of memory. Draw a map of registers and memory space showing changes after the execution of each instruction. Produce machine language of the program."

Ok. The questioner seems to want it done in unpacked BCD, where 19837.. is stored as 01h 09h 08h 03h 07h..

Start by creating two memory arrays of 20 bytes each, for the integers. Then make another array of 40 bytes, for the product. Personally I would arrange the storage little-endian, ie low address has low order digit, which is Intel convention, but that's your choice.

You'll also need a couple of word variables to store addresses, since the 8085 is a bit short of registers.

Next thing you need is a binary multiply routine, 4x4, 8 bit result. This is going to be a bit special, since we're working with BCD, but the basic principal is the same for all multipliers. You start with a zero product. For each bit of the multiplier:
1. Shift the product left one bit
2. If the multiplier bit is 1, add the multiplicand to the product
3. Because this is BCD, after the add operation, do a DAA
4. Do until done
Here's how it looks in practice.

To start with, shift the multiplier left 4 bits to lose the unused top 4 bits, zero the product, and set up a counter of 4.
(some Z80 mnemonics may creep into the code - it's been a long time since I used 8085)
; for each of 20 multiplier digits, get the next digit in D
[code]
mov a,d
rla ; shift left 4 places
rla ; to get rid of unused bits
rla
rla
mov d,a ; will be used 20 times
...
; for each of 20 multiplicand digits, get the next digit in E
push d ; save adjusted product
ldi b,4 ; counter
xra a ; clear product
; here is the actual multiply loop
loop:
rla ; left shift product
mov c,a ; save it
mov a,d
rla ; shift next multiplier bit to carry
mov d,a
mov a,c ; get product back
jnc no_add ; skip if bit was 0
daa ; decimal adjust, because this is BCD
dec b
jnz loop
; end of multiply loop
pop d ; don't forget this
(store partial product, see below)
(next multiplicand digit, until 20)
(next multiplier digit, until 20)
[/code]

After each multiply you have a partial product in A, but it's PACKED BCD - eg 06h x 04h = 24H. Add any high-half overflow from the previous multiplication, remembering to decimal adjust after adding, then separate the two halves and store it in the product register, with a second addition and DAA if necessary. I'll use your example numbers - ...4321 * ...3975. Notice at each step I'm adding the 8-bit partial product digit one byte above the last step, then separating the high half of the sum into the next byte up.
[code]
...00 00 00 00 00+ << product store
5*1 = 05 05 << result of multiplication
...00 00 00 00 05+
5*2 = 10 10
...00 00 01 00 05+
5*3 = 15 15
...00 01 06 00 05+
5*4 = 20 20
...02 01 06 00 05 etc
[/code]

If you do the long multiplication by hand, on paper, you'll see how it comes together. Always start at the least significant end and work towards the most. For each successive multiplier digit, save the product one more byte up the product store, eg:
(next multiplier digit pass)
[code]
...02 01 06 00 05+
7*1 = 07 07 << moved up one byte
...02 01 06 07 05+
7*2 = 14 14 << complications!
--
1A << DAA
20 << carry 2
01+
02 << add 2 to previous 1
--
...02 03 00 07 05 << new partial product
[/code]

You'll have several nested loops and need several counters and address stores in memory, since there aren't enough registers.

• Member Posts: 7
Just a huge "thank you". It is clear enough to start and I will be working on that this weekend. If I have any questions I will post it again, of course! :O)
• Member Posts: 69
There are some subtle catches because of the BCD format. Here's a complete routine that should work, though I haven't tried it.

[code]

; numbers stored least significant digit first
multier: ds 20 ; multiplier
multand: ds 20 ; multiplicand
product: ds 40 ; product
mier_ptr: ds 2 ; multiplier pointer
mand_ptr: ds 2 ; multiplicand pointer
prod_ptr: ds 2 ; product pointer
pprod_ptr: ds 2 ; partial product pointer
mier_count: ds 1 ; multiplier count
mand_count: ds 1 ; multiplicand count

multiply_routine:
lxi hl,multier ; set up initial pointers
shld mier_ptr ; for multiplier
lxi hl,product
shld prod_ptr ; and product

ldi b,40 ; clear product to all 00
xra a ; (important)
clr_prod:
stax h
inx h
dec b
jnz clr_prod

mvi a,20 ; set up m'ier digit count
sta mier_count

next_multiplier_digit:
lhld mier_ptr ; address of next digit
ldax h ; get digit
shld mier_ptr
rla ; waste top 4 bits
rla
rla
rla
mov d,a ; save for later

lxi h,multand ; set up m'and pointer
shld mand_ptr
mvi a,20 ; and digit count
sta mand_count

lhld prod_ptr ; init partial product pointer
shld pprod_ptr

next_multiplicand_digit:
lhld mand_ptr
ldax h
inx h
shld mand_ptr
mov e,a ; multiplicand digit
mvi b,4
mvi c,0 ; product
push d
multiply_loop:
mov a,c ; shift product left -
add a,a ; MUST do it this way
daa ; to preserve BCD format
mov c,a

mov a,d ; get next multiplier bit
rla
mov d,a
mov a,e ; else add multiplicand
mov c,a
dcr b
jnz multiply_loop
pop d
; adding the partial product is more complicated than it
; seems, as there could be multiple carries all the way up.
; Imagine if partial product is 09999..9999 and you add 9.
; You carry all the way up and end up with 10000..0008.
lhld pprod_ptr ; get pointer
mov a,c ; product this pass
daa
mov c,a ; save result
ani 0Fh ; extract low half
stax h ; store it
inx h ; step up one
mov a,c ; get result back
ani 0F0h ; extract high digit
jz pp_add_done ; done if no high digit

rra ; there was a high digit
rra ; shift it right 4
rra
rra
jmp add_again ; and propagate until done

pp_add_done: ; there are no more carries
lhld pprod_ptr ; inc partial product pointer
inx h ; for next time
shld pprod_ptr

lxi h,mand_count ; count this digit
dcr m
jnz next_multiplicand_digit

lhld prod_ptr ; inc product pointer
inx h ; for next time
shld prod_ptr

lxi h,mier_count ; count this digit
dcr m
jnz mext_multiplier_digit

ret
; end routine

[/code]

• Member Posts: 7
Hi, there!

After a long summer, I've tried to compile that. I got some errors (pasted) that I still cannot solve. Do you have a clue what is causing them?

Thanks!

0001 0000
0002 0000 multier: ds 20 ;multiplier
0003 0014 multand: ds 20 ;multiplicand
0004 0028 product: ds 40 ;product
0005 0050 mier_ptr: ds 2 ;multiplier pointer
0006 0052 mand_ptr: ds 2 ;multiplicand pointer
0007 0054 prod_ptr: ds 2 ;product pointer
0008 0056 pprod_ptr: ds 2 ;partial product pointer
0009 0058 mier_count: ds 1 ;multiplier count
0010 0059 mand_count: ds 1 ;multiplicand count
0011 005A
0012 005A multiply_routine:
0013 005A 21 00 00 lxi h,multier ;set up initial pointers
0014 005D 22 50 00 shld mier_ptr ;for multiplier
0015 0060 21 28 00 lxi h,product
0016 0063 22 54 00 shld prod_ptr ;and product
0017 0066
0018 0066 01 28 00 lxi b,40 ;ldi = clear product to all 00
0019 0069 AF xra a ;(important)
0020 006A
0021 006A clr_prod:
0022 006A stax HL
0022 Error: Unrecognized instruction.
0023 006A 24 inr h
0024 006B 05 dcr b
0025 006C C2 6A 00 jnz clr_prod
0026 006F
0027 006F 3E 14 mvi a,20 ;set up m'ier digit count
0028 0071 32 58 00 sta mier_count
0029 0074
0030 0074 next_multiplier_digit:
0031 0074 2A 50 00 lhld mier_ptr ;address of next digit
0032 0077 ldax hl ;get digit
0032 Error: Unrecognized instruction.
0033 0077 23 inx h ;bump address
0034 0078 22 50 00 shld mier_ptr
0035 007B 17 ral ;waste top 4 bits
0036 007C 17 ral
0037 007D 17 ral
0038 007E 17 ral
0039 007F 57 mov d,a ;save for later
0040 0080
0041 0080 21 14 00 lxi h,multand ;set up m'and pointer
0042 0083 22 52 00 shld mand_ptr
0043 0086 3E 14 mvi a,20 ;and digit count
0044 0088 32 59 00 sta mand_count
0045 008B
0046 008B 2A 54 00 lhld prod_ptr ;init partial product pointer
0047 008E 22 56 00 shld pprod_ptr
0048 0091
0049 0091 next_multiplicand_digit:
0050 0091 2A 52 00 lhld mand_ptr
0051 0094 ldax h
0051 Error: Unrecognized instruction.
0052 0094 23 inx h
0053 0095 22 52 00 shld mand_ptr
0054 0098 5F mov e,a ;multiplicand digit
0055 0099 06 04 mvi b,4
0056 009B 0E 00 mvi c,0 ;product
0057 009D D5 push d
0058 009E
0059 009E multiply_loop:
0060 009E 79 mov a,c ;shift product left -
0061 009F add a,a ;MUST do it this way
0061 Error: Unrecognized instruction.
0062 009F 27 daa ;to preserve BCD format
0063 00A0 4F mov c,a
0064 00A1
0065 00A1 7A mov a,d ;get next multiplier bit
0066 00A2 17 ral
0067 00A3 57 mov d,a
0068 00A4 D2 AB 00 jnc no_add ;no add if no carry
0069 00A7 7B mov a,e ;else add multiplicand
0070 00A8 81 add c ;to product
0071 00A9 27 daa ;and decimal adjust
0072 00AA 4F mov c,a
0073 00AB
0075 00AB 05 dcr b
0076 00AC C2 9E 00 jnz multiply_loop
0077 00AF D1 pop d
0078 00B0
0079 00B0 ;adding the partial product is more complicated than it seems
0080 00B0 ;as there could be multiple carries all the way up.
0081 00B0 ;Imagine if partial prodcut is 09999...9999 and you add 9.
0082 00B0 ;You carry all the way up and end up with 10000...0008.
0083 00B0
0084 00B0 2A 56 00 lhld pprod_ptr ;get pointer
0085 00B3 79 mov a,c ;product this pass
0086 00B4
0089 00B5 27 daa
0090 00B6 4F mov c,a ;save result
0091 00B7 E6 0F ani 0Fh ;exract low half
0092 00B9 stax h ;store it
0092 Error: Unrecognized instruction.
0093 00B9 23 inx h ;step up one mov a,c ;get result back
0094 00BA E6 F0 ani 0F0h ;extract high digit
0095 00BC jz pp_add_done ;done if no high digit
0095 Error: Invalid argument of the instruction.
0096 00BF
0097 00BF 1F rar ;there was a high digit
0098 00C0 1F rar ;shift it right 4
0099 00C1 1F rar
0100 00C2 1F rar
0101 00C3 C3 B4 00 jmp ad_d_again ; and propagate until done
0102 00C6
0103 00C6 pp_adddone: ;there are no more carries
0104 00C6 2A 56 00 lhld pprod_ptr ;inc partial product pointer
0105 00C9 23 inx h ;for next time
0106 00CA 22 56 00 shld pprod_ptr
0107 00CD
0108 00CD 21 59 00 lxi h,mand_count ;cont this digit
0109 00D0 35 dcr m
0110 00D1 C2 91 00 jnz next_multiplicand_digit
0111 00D4
0112 00D4 2A 54 00 lhld prod_ptr ;inc product pointer
0113 00D7 23 inx h ;for next time
0114 00D8 22 54 00 shld prod_ptr
0115 00DB
0116 00DB 21 58 00 lxi h,mier_count ;count this digit
0117 00DE 35 dcr m
0118 00DF C2 74 00 jnz next_multiplier_digit
0119 00E2
0120 00E2 C9 ret
0121 00E3
0122 00E3 ;end routine
0123 00E3
Number of errors = 6

: There are some subtle catches because of the BCD format. Here's a complete routine that should work, though I haven't tried it.
:
: [code]
:
: ; numbers stored least significant digit first
: multier: ds 20 ; multiplier
: multand: ds 20 ; multiplicand
: product: ds 40 ; product
: mier_ptr: ds 2 ; multiplier pointer
: mand_ptr: ds 2 ; multiplicand pointer
: prod_ptr: ds 2 ; product pointer
: pprod_ptr: ds 2 ; partial product pointer
: mier_count: ds 1 ; multiplier count
: mand_count: ds 1 ; multiplicand count
:
: multiply_routine:
: lxi hl,multier ; set up initial pointers
: shld mier_ptr ; for multiplier
: lxi hl,product
: shld prod_ptr ; and product
:
: ldi b,40 ; clear product to all 00
: xra a ; (important)
: clr_prod:
: stax h
: inx h
: dec b
: jnz clr_prod
:
: mvi a,20 ; set up m'ier digit count
: sta mier_count
:
: next_multiplier_digit:
: lhld mier_ptr ; address of next digit
: ldax h ; get digit
: inx hl ; bump address
: shld mier_ptr
: rla ; waste top 4 bits
: rla
: rla
: rla
: mov d,a ; save for later
:
: lxi h,multand ; set up m'and pointer
: shld mand_ptr
: mvi a,20 ; and digit count
: sta mand_count
:
: lhld prod_ptr ; init partial product pointer
: shld pprod_ptr
:
: next_multiplicand_digit:
: lhld mand_ptr
: ldax h
: inx h
: shld mand_ptr
: mov e,a ; multiplicand digit
: mvi b,4
: mvi c,0 ; product
: push d
: multiply_loop:
: mov a,c ; shift product left -
: add a,a ; MUST do it this way
: daa ; to preserve BCD format
: mov c,a
:
: mov a,d ; get next multiplier bit
: rla
: mov d,a
: mov a,e ; else add multiplicand
: add c ; to product
: daa ; and decimal adjust
: mov c,a
: dcr b
: jnz multiply_loop
: pop d
: ; adding the partial product is more complicated than it
: ; seems, as there could be multiple carries all the way up.
: ; Imagine if partial product is 09999..9999 and you add 9.
: ; You carry all the way up and end up with 10000..0008.
: lhld pprod_ptr ; get pointer
: mov a,c ; product this pass
: daa
: mov c,a ; save result
: ani 0Fh ; extract low half
: stax h ; store it
: inx h ; step up one
: mov a,c ; get result back
: ani 0F0h ; extract high digit
: jz pp_add_done ; done if no high digit
:
: rra ; there was a high digit
: rra ; shift it right 4
: rra
: rra
: jmp add_again ; and propagate until done
:
: pp_add_done: ; there are no more carries
: lhld pprod_ptr ; inc partial product pointer
: inx h ; for next time
: shld pprod_ptr
:
: lxi h,mand_count ; count this digit
: dcr m
: jnz next_multiplicand_digit
:
: lhld prod_ptr ; inc product pointer
: inx h ; for next time
: shld prod_ptr
:
: lxi h,mier_count ; count this digit
: dcr m
: jnz mext_multiplier_digit
:
: ret
: ; end routine
:
: [/code]
:
:

• Member Posts: 69
[italic]After a long summer, I've tried to compile that. I got some errors (pasted) that I still cannot solve. Do you have a clue what is causing them?[/italic]

Yes (see below). Some are my mistakes trying to do 8080 from memory, though you caught and corrected most of them. One or two are copying errors.

[hr]
0018 0066 01 28 00 lxi b,40 ;ldi = clear product to all 00

My mistake. This should have been
[code] MVI B,40 ; not "LDI B,40"[/code]
Your substitution "LXI B,40" sets C to 40 and B to ZERO, which would give you a count of 256.
[hr]
0022 006A stax HL
0022 Error: Unrecognized instruction.

My mistake, You "STAX B" and "STAX D", but for HL it should be
[code] MOV M,A[/code]
[hr]
0023 006A 24 inr h

Your assembler doesn't like "INX HL", apparently, but this isn't the right correction. You must "INX H" (double register). "INR H" only incs the H register, not the HL pair.
[hr]
0024 006B 05 dcr b

You're right, it's "DCR B" not "DEC B"
[hr]
0032 0077 ldax hl ;get digit
0032 Error: Unrecognized instruction.

My mistake, You "LDAX B" and "LDAX D", but for HL it should be
[code] MOV A,M [/code]
[hr]
0035 007B 17 ral ;waste top 4 bits

You're right, it's RAL not RLA. Just make sure it's the rotate that DOESN'T go through the carry
[hr]
0051 0094 ldax h
0051 Error: Unrecognized instruction.

Like line 32, it should be
[code] MOV A,M[/code]
[hr]
0061 009F add a,a ;MUST do it this way
0061 Error: Unrecognized instruction.

My mistake. Destination A is implied. Should be:
[hr]

You got an extra underline in that label, but you matched it up in line 101 so that's ok.
[hr]
0092 00B9 stax h ;store it
0092 Error: Unrecognized instruction.

Like line 22. Should be:
[code] MOV M,A[/code]
[hr]
0093 00B9 23 inx h ;step up one mov a,c ;get result back

Here's a copying error - you have two instructions on that line.
Change to:
[code] INX H
MOV A,C[/code]
[hr]
0095 00BC jz pp_add_done ;done if no high digit
0095 Error: Invalid argument of the instruction.

You made a copying error in line 103 - pp_adddone. The assembler can't find the label pp_add_done.
[hr]