How to do 64 bit multiply on 16 bit machine?

Question

I have an embedded 16 bit CPU. On this machine ints are 16 bit wide and it supports longs that are 32 bits wide. I need to do some multiplications that will need to be stored in 64 bits (e.g. multiply a 32 bit number by a 16 bit number). How can I do that with the given constraints? I do not have a math library to do this.

Answer 1

A suggestion in C. Note that this code probably will be easier to implement with inline assembler as carry detection in C doesn't seem that easy

// Change the typedefs to what your compiler expects
typedef unsigned __int16     uint16   ;
typedef unsigned __int32     uint32   ;

// The 64bit int
typedef struct uint64__
{
    uint32       lower   ;
    uint32       upper   ;
} uint64;

typedef int boolt;

typedef struct addresult32__
{
    uint32      result  ;
    boolt       carry   ;
} addresult32;

// Adds with carry. There doesn't seem to be 
// a real good way to do this is in C so I 
// cheated here. Typically in assembler one
// would detect the carry after the add operation
addresult32 add32(uint32 left, uint32 right)
{
    unsigned __int64 res;
    addresult32 result  ;

    res = left;
    res += right;


    result.result = res & 0xFFFFFFFF;
    result.carry  = (res - result.result) != 0;

    return result;
}

// Multiplies two 32bit ints
uint64 multiply32(uint32 left, uint32 right)
{
    uint32 lleft, uleft, lright, uright, a, b, c, d;
    addresult32 sr1, sr2;
    uint64 result;

    // Make 16 bit integers but keep them in 32 bit integer
    // to retain the higher bits

    lleft   = left          & 0xFFFF;
    lright  = right         & 0xFFFF;
    uleft   = (left >> 16)  ;
    uright  = (right >> 16) ;

    a = lleft * lright;
    b = lleft * uright;
    c = uleft * lright;
    d = uleft * uright;

    sr1 = add32(a, (b << 16));
    sr2 = add32(sr1.result, (c << 16));

    result.lower = sr2.result;
    result.upper = d + (b >> 16) + (c >> 16);
    if (sr1.carry)
    {
        ++result.upper;
    }

    if (sr2.carry)
    {
        ++result.upper;
    }

    return result;
}

Answer 2

You might want to check out Hacker's Delight (it's a book and a website). They have C implementations of Knuth's signed multiword multiplication and unsigned multiword multiplication from The Art of Computer Programming Vol.2.