Multiplying 64-bit number by a 32-bit number in 8086 asm

Question

I have been having problems even initiating the solution for the problem. I have tried considering the multiplication is repeated addition algorithm but whatever algorithm I consider, I seem to be fixated over a single issue- the max register size in 8086 is 16-bit.

data segment
num1 dw 0102h,0304h,0506h,0708h
num2 dw 0102h,0304h
res dw ?,?,?,?,?,?
data ends

code segment
assume CS:CODE, DS:DATA
start:
mov ax,DATA
mov DS,ax

..........fill code..........

At this point I am stuck. Even a slight hint of code or just the algorithm would be appreciated.

Answer 1

For multiplying a 64-bit number by a 32-bit number with a 16-bit CPU:

Step 1: Assume the numbers are in "base 65536". For example, a 64-bit number has 16 digits in hex (e.g. 0x0123456789ABCDEF) and would have 4 digits in "base 65536" (e.g. {0123}{4567}{89AB}{CDEF}); and in the same way a 32-bit number would have 2 digits in "base 65536".

Step 2: To multiply a pair of numbers, multiply each digit from the first number with each digit from the second number, and add this into the right place in the result. The right place depends on the position of each digit in the original numbers. For example (in decimal) for 90 * 30 you'd do "9*3 = 27" and put it in the "hundreds" place (e.g. 2700) because there was one digit to the right in the first number plus another digit to the right in the second number, and that means it needs to go where there's 2 digits to the right in the result.

Example:

    0x0123456789ABCDEF * 0x87654321
  = {0123}{4567}{89AB}{CDEF} * {8765}{4321}

                      {0123}{4567}{89AB}{CDEF}
    *                             {8765}{4321}
    ------------------------------------------
    =                             {3600}{18CF}  (from 4321 * CDEF)
    +                       {6CEA}{484B}{0000}  (from 8765 * CDEF)
    +                       {2419}{800B}{0000}  (from 4321 * 89AB)
    +                 {48CF}{7D77}{0000}{0000}  (from 8765 * 89AB)
    +                 {1232}{E747}{0000}{0000}  (from 4321 * 4567)
    +           {24B4}{B2A3}{0000}{0000}{0000}  (from 8765 * 4567)
    +           {004C}{4E83}{0000}{0000}{0000}  (from 4321 * 0123)
    +     {0099}{E7CF}{0000}{0000}{0000}{0000}  (from 8765 * 0123)
    ------------------------------------------
    =     {009A}{0CD0}{5C28}{F5C1}{FE56}{18CF}
    ------------------------------------------
    = 0x009A0CD05C28F5C1FE5618CF

Note that 8086 has a "16 bit multiplied by 16 bit = 32-bit result" instruction (MUL); and addition can be done 16 bits at a time by using one ADD instruction followed by however many ADC instructions you need.

Also note that you can avoid some additions by merging. For example:

                      {0123}{4567}{89AB}{CDEF}
    *                             {8765}{4321}
    ------------------------------------------
    =                             {3600}{18CF}  (from 4321 * CDEF)
    +                       {6CEA}{484B}{0000}  (from 8765 * CDEF)
    +                       {2419}{800B}{0000}  (from 4321 * 89AB)
    +                 {48CF}{7D77}{0000}{0000}  (from 8765 * 89AB)
    +                 {1232}{E747}{0000}{0000}  (from 4321 * 4567)
    +           {24B4}{B2A3}{0000}{0000}{0000}  (from 8765 * 4567)
    +           {004C}{4E83}{0000}{0000}{0000}  (from 4321 * 0123)
    +     {0099}{E7CF}{0000}{0000}{0000}{0000}  (from 8765 * 0123)
    ------------------------------------------
    =                             {3600}{18CF}  (from 4321 * CDEF)
    +                 {48CF}{7D77}{0000}{0000}  (from 8765 * 89AB)
    +     {0099}{E7CF}{0000}{0000}{0000}{0000}  (from 8765 * 0123)
    +                       {6CEA}{484B}{0000}  (from 8765 * CDEF)
    +           {24B4}{B2A3}{0000}{0000}{0000}  (from 8765 * 4567)
    +                       {2419}{800B}{0000}  (from 4321 * 89AB)
    +           {004C}{4E83}{0000}{0000}{0000}  (from 4321 * 0123)
    +                 {1232}{E747}{0000}{0000}  (from 4321 * 4567)
    ------------------------------------------
    =     {0099}{E7CF}{48CF}{7D77}{3600}{18CF}  (THESE WERE MERGED WITHOUT ADDITION)
    +           {24B4}{B2A3}{6CEA}{484B}{0000}  (THESE WERE MERGED WITHOUT ADDITION)
    +           {004C}{4E83}{2419}{800B}{0000}  (THESE WERE MERGED WITHOUT ADDITION)
    +                 {1232}{E747}{0000}{0000}  (from 4321 * 4567)
    ------------------------------------------
    =     {009A}{0CD0}{5C28}{F5C1}{FE56}{18CF}
    ------------------------------------------
    = 0x009A0CD05C28F5C1FE5618CF

Of course, because it doesn't matter which order you do the multiplication of pairs of ("base 65536") digits; you can do all the multiplications in the optimum order for merging.

For the final code (with merging); you'd end up with 8 MUL instructions, 3 ADD instructions and about 7 ADC instructions. I'm too lazy to write the code. ;)