Howdy, Stranger!

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

Categories

8085 program to multiply 20 digits integers

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

Comments

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

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

  • peretperet 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
    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)
    [/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.

  • DududuDududu 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)
  • peretperet 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
    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

    [/code]

  • DududuDududu 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
    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.
    :
    : [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
    : 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
    :
    : [/code]
    :
    :

  • peretperet 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:
    [code] ADD A[/code]
    [hr]
    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.
    [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]



Sign In or Register to comment.