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!

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!
:

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!
: :
:
:

: 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

	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
	add	a,e	; else add multiplicand digit
	daa		; decimal adjust, because this is BCD
no_add:
	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)

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.

               ...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

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)

               ...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

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

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)

There are some subtle catches because of the BCD format. Here's a complete routine that should work, though I haven't tried it.

; 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
	jnc	no_add		; no add if no carry
	mov	a,e		; else add multiplicand
	add	c		; to product
	daa			; and decimal adjust
	mov	c,a
no_add:
	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
add_again:
	add	m		; add PP at (hl)
	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

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
0074 00AB no_add:
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
0087 00B4 ad_d_again:
0088 00B4 86 add m ;add PP at (hl)
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.
:
:

: 
: ; 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
: 	jnc	no_add		; no add if no carry
: 	mov	a,e		; else add multiplicand
: 	add	c		; to product
: 	daa			; and decimal adjust
: 	mov	c,a
: no_add:
: 	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
: add_again:
: 	add	m		; add PP at (hl)
: 	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
: 
: 

:
:

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?

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.

---

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

My mistake. This should have been

 MVI B,40     ; not "LDI B,40"

Your substitution "LXI B,40" sets C to 40 and B to ZERO, which would give you a count of 256.

---

0022 006A stax HL
0022 Error: Unrecognized instruction.

My mistake, You "STAX B" and "STAX D", but for HL it should be

 MOV M,A

---

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.

---

0024 006B 05 dcr b

You're right, it's "DCR B" not "DEC B"

---

0032 0077 ldax hl ;get digit
0032 Error: Unrecognized instruction.

My mistake, You "LDAX B" and "LDAX D", but for HL it should be

 MOV A,M 

---

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

---

0051 0094 ldax h
0051 Error: Unrecognized instruction.

Like line 32, it should be

 MOV A,M

---

0061 009F add a,a ;MUST do it this way
0061 Error: Unrecognized instruction.

My mistake. Destination A is implied. Should be:

 ADD A

---

0087 00B4 ad_d_again:

You got an extra underline in that label, but you matched it up in line 101 so that's ok.

---

0092 00B9 stax h ;store it
0092 Error: Unrecognized instruction.

Like line 22. Should be:

 MOV M,A

---

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:

 INX H
 MOV A,C

---

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.

---