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.

Break up your numbers into 16 bit chunks, use the 16x16=>32 multiplication of your cpu and accumulate the partial results as appropriate. Remember you can easily multiply by powers of 2 using shifting, or in this case simply indexing your words. — Jester, Apr 03 '19 at 01:27
@Jester I am pretty much a beginner at assembly programming but will be exploring it further. If you would be able to explain your answer to me in a more dumbed down language possibly with some fragments of code, I would be really thankful. — Jack Morton, Apr 03 '19 at 01:42
`(a*2^48+b*2^32+c*2^16+d) * (e*2^16+f)`. All letters are 16 bit numbers. Perform the multiplications and group the result. — Jester, Apr 03 '19 at 01:46
@Jester Sorry for troubling you again but it is still going over my head as to how do I implement the multiplications in code — Jack Morton, Apr 03 '19 at 02:23
@JackMorton - Although the max register size is 16 bit, the multiply instruction produces a 32 bit product in dx:ax. A basic algorithm for extended precision multiply is similar to doing a long hand multiply. First see if you can figure out how to multiply a 32 bit number by a 16 bit number, then a 64 bit number by a 16 bit number, then a 64 bit number by a 32 bit number. — rcgldr, Apr 03 '19 at 02:45

Brendan · Answer 1 · 2019-04-03T04:18:29.837

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

[multiply two 32-bit numbers to get a 64-bit number, on a 8086 (32x32 => 64-bit with 16-bit multiplies)](https://stackoverflow.com/q/13451628) shows real code where adc is needed. https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf shows 512x512-bit multiplication using 64-bit chunks, both traditional and with mulx (mul not affecting CF) and with mulx + adcx/adox (separate dependency chains for carries) — Peter Cordes, Jun 08 '21 at 08:42

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

1 Answers1

Linked