General multiplication

[c64]

Hi,

This is a general MCU question, and not really addressed to a particular architecture. Say you have an 8-bit MCU that can do 8-bit x 8-bit unsigned integer multiplication, with the result being 16 bits. Would it be possible to use that built-in arithmetic routine to perform a multiplication of M x N bit unsigned integers, where M and N are larger than 8. For instance, would it be possible to perform an 18 x 16 bit unsigned integer multiplication? Not directly of course, but by writing a procedure for it. If so, does anyone have a link to a website describing these algorithms?

Thanks!

[c64]

Hey guys,

Thanks so much for the replies and sample codes! I really appreciate it!

[tonyp]

And here's a 9S08 assembly language re-entrant routine that multiplies any size (up to 127 bytes) numbers.  For parameter passing simplicity both operands must be of the same size.

[bigmac]

Hello,

The attached code contains functions for 16 x 16 multiply, and 32 x 32 multiply, plus some other division functions.  It extensively makes use of inliine assembly for speed, so is restricted to HC908 and HCS08 devices.

Regards,

Mac

[kef · Accepted solution]

Of course 8x8->16bits MUL instructtion can be used to multiply as many bits as you wish. Procedure? Sure you know how to multiply for example 3 decimal digits number by 2 decimal digits number. This algorithm is the same, just replace decimal digits with bytes.

     03 FF FF

x        FF FF

     ---------

         FE 01   - first MUL

     03 FF FF

x        FF FF

     ---------

         FE 01 

+   FE 01        - second MUL

     03 FF FF

x        FF FF

     ---------

         FE 01 

+  FE 01

02 FD              - 3rd MUL

... do another 3 MULs with higher order byte of 2nd multiplier and final picture will be this

            03 FF FF

x               FF  FF

            ---------

                FE 01 

+         FE 01

       02 FD              - 3rd

           FE 01 

+     FE 01

  02 FD              - 6th

--------------------

  03 FF FB 00 01 - 18+16 = 34bits product

Hope this helps