Multiplying two 32-bit integers together and getting a 64-bit result

Okay, I'm trying to work with numbers using LSL's 32-bit integers, however I've hit a small snag. Basically; I want to multiply two 32-bit integers of any size (actually 31-bit since I don't allow negative values) together, however, this could actually produce a result up to 64-bits in size. In other languages you can get around this by converting both numbers (A and B) to 64-bit values, a multiply them together to get a result then deal with it accordingly. LSL can't do this unfortunately =(

So what I'm looking for is anyone who knows how to perform a multiplication of two 32-bit integers, and get the answer as two integers, one the upper half of the 64-bit value, the other the lower half of the 64-bit value.

I know this can be done by laboriously shifting through one-bit at a time, but I'm hoping there's a faster way of doing this, as languages such as Java and C have supported 64-bit operations on 32-bit hardware for a while now but I have no idea what I'd google for to find out how they do it =(

Yes. I did that here: /54/df/140261/1.html

The relevant function is:

// Returns the full product of two unsigned integers. The first (index 0)
// integer is the most significant integer of the product. The second
// (index 1) integer is the least significant integer of the product.
list u_intProd(integer i1, integer i2)
{
   ...
}

You'll have to modify it if you want it to work for signed numbers, but it should give you a decent starting point.

Ah, just arrived at a solution after managing to find this article in Google:
http://developer.apple.com/hardwaredrivers/ve/algorithms.html#Multiply32

I seem to have arrived at pretty much exactly what you have, except I can't tell, are your results as two 31-bit unsigned integers, or as the most-significant and least-significant bits of a 63-bit integer?

Here's my code for comparison:

list 64mul32x32(integer aVal, integer bVal) {
    integer aUpper;
    integer aLower;
    integer bUpper;
    integer bLower;
    integer temp;

    aUpper = ((aVal >> 16) & 0x00007FFF);
    aLower = (aVal & 0x0000FFFF);
    bUpper = ((bVal >> 16) & 0x00007FFF);
    bLower = (bVal & 0x0000FFFF);

    owerWord = aLower * bLower;
    if ((upperWord = lowerWord & 0x80000000) != 0) {
        upperWord = 1;
        lowerWord = lowerWord & 0x7FFFFFFF;
    }
    temp = aUpper * bLower;
    lowerWord += (temp << 16) & 0x7FFFFFFF;
    if ((lowerWord & 0x80000000) != 0) {
        ++upperWord;
        lowerWord = lowerWord & 0x7FFFFFFF;
    }
    upperWord += (temp >> 15) & 0x0001FFFF;

    temp = aLower * bUpper;
    lowerWord += (temp << 16) & 0x7FFFFFFF;
    if ((lowerWord & 0x80000000) != 0) {
        ++upperWord;
        lowerWord = lowerWord & 0x7FFFFFFF;
    }
    upperWord += (temp >> 15) & 0x0001FFFF;
    upperWord += ((aUpper * bUpper) << 1) & 0x7FFFFFFF;

    return [upperWord, lowerWord];
}

In my actual implementation though I don't return a list, I actually a two global variables which hold the arguments, and later the results.

...and then program it to do the multiplication on its toes.

Yes, my results were two 31-bit integers (most significant word and least significant word, with the sign bits unused) in a list. There's no such thing as a 64-bit integer in LSL.

if you store more than 64 bits you should consider using some base64 strings for the bitfields instead of integers or lists of them.
Strings are smaller and in base64 you automatically have a compressed string for communication and an option to compress even further; 5 letters that store 6 bits each (base64) into 2 letters that store 15 bit each (integer2utf.

The base64 procedures of sl are still slower than any procedure that you write in sls, that will convert 100 to 500 letters per second, but theyre small in bytecode and will get much better in mono.
there are also procedures to XOR two base64 strings and wiki has libraries for more logical operations on base64 strings, i bet they have multiplication, too.

I know, I just wasn't sure from your code if it was giving one integer with 32-bits of the answer, and one with the remaining 30 bits I suppose it'd be. Okay, thanks for your help, seems to be all working as required!