[Mauzen]

Ive always been trying to script close to PAWNs limits. This idea made it into my mind when I thought about a stone-old basic program that fascinated me ages ago, as it could calculate floats with any precision, while that "qbasic" just had 16 bit variables. Heres a lesson about the limit called "maximum integer size".

As most of you will know PAWN is typefree, means all variables got the same size: 32 bits. This also means that variables always are signed (+/-). So for integers theres the limit of about -2^31 to +2^31 (+-1 for 0, but I dont wanna go into detail about that). In numbers thats about +-2,1 billion. The normal way you cant calculate with any numbers bigger or smaller than this. But what to do if you have to? I know thats a rare case, and I cant think of anything that really needs that right now, but despite of that I thought about ways how to calculate with bigger numbers.
I thought back to my computer architecture lecture, ignored what I learned there, and created this ugly solution. It uses arrays of numbers and "merges" them to big numbers. One field of those arrays represents 9 digits, and they are ordered in blocks right to left.
So e.g. {999999999, 123} = 123999999999, {0, 10} = 10000000000
This is ugly, because it uses decimal representation. Just half of a variables capacity is used, as the max number is 999999999. Normally you would calculate with their binary values, the same way computers calculate internally, so you could use a variables full capacity. But this version is easier to understand, and faster to create
For the beginning I experimented with simple addition. This is the result:

pawn Код:

#define OVERFLOW        (-1)        // Calculated number is too big for the result array
#define SUCCESS         (1)         // Addition successful
#define MAX_PART_NUM    (999999999)
#define PART_VALUE      (1000000000)

// Basically this just loops through all number blocks in the
// arrays, adds them, eventually adds the carry of the last step,
// and stores the result in another array at the right position
stock addBigNumber(n1[], n2[], result[], l1 = sizeof(n1), l2 = sizeof(n2), lr = sizeof(result)) {
    // Check validity of partial numbers (optional)
    for (new i = 0; i < l1; i++) {
        if (n1[i] > MAX_PART_NUM) return 0;
    }
    for (new i = 0; i < l2; i++) {
        if (n2[i] > MAX_PART_NUM) return 0;
    }
    
    if (l1 > l2) {
        // l1 got more partial numbers than l2
        new carry = 0;
        for (new i = 0; i < l1; i++) {
            if (i + 1 > lr) return OVERFLOW;
            if (i >= l2) {
                // if n2 got no more numbers, just add the carry
                result[i] = n1[i] + carry;
            } else {
                // else add both number blocks and the carry of the last step
                result[i] = n1[i] + n2[i] + carry;
            }
            
            carry = 0;
            if (result[i] > MAX_PART_NUM) {
                // Calculate carry, it will always be 1 for sums of course
                                // but this calculation is more general for other operations
                carry = (result[i] - PART_VALUE) / PART_VALUE + 1;
                // limit the result to 9 digits
                result[i] = result[i] - PART_VALUE;
            }

            if (carry > 0) {
                if (l1 + 1 > lr) return OVERFLOW;
                result[l1] = carry;
            }
        }
    } else if (l2 > l1) {
        // l2 got more partial numbers than l1
        new carry = 0;
        for (new i = 0; i < l2; i++) {
            if (i + 1 > lr) return OVERFLOW;
            if (i >= l1) {
                result[i] = n2[i] + carry;
            } else {
                result[i] = n1[i] + n2[i] + carry;
            }
            
            carry = 0;
            if (result[i] > MAX_PART_NUM) {
                // Calculate carry
                carry = (result[i] - PART_VALUE) / PART_VALUE + 1;
                result[i] = result[i] - PART_VALUE;
            }

            if (carry > 0) {
                if (l1 + 1 > lr) return OVERFLOW;
                result[l1] = carry;
            }           
        }
    } else {
        // l1 and l2 got the same amount of partial numbers
        
        // Start with the last partial number for easier carry calculation
        new carry = 0;
        for (new i = 0; i < l1; i++) {
            if (i + 1 > lr) return OVERFLOW;
            result[i] = n1[i] + n2[i] + carry;
            carry = 0;
            if (result[i] > MAX_PART_NUM) {
                // Calculate carry
                carry = (result[i] - PART_VALUE) / PART_VALUE + 1;
                result[i] = result[i] - PART_VALUE;
            }           
        }
        if (carry > 0) {
            if (l1 + 1 > lr) return OVERFLOW;
            result[l1] = carry;
        }
    }
    return SUCCESS;
}

// Creates a human-readable string of an array-number
stock formatBigNumber(n1[], res[], l1 = sizeof(n1), lr = sizeof(res)) {
    // First partial number without trailing 0
    new firstnotnull;
    // Find first number != null
    for (new i = l1 - 1; i >= 0; i--) {
        if (n1[i] != 0) {
            firstnotnull = i;
            break;
        }
    }
    format(res, lr, "%d", n1[firstnotnull]);
    for (new i = firstnotnull - 1; i >= 0; i--) {
        format(res, lr, "%s%09d", res, n1[i]);
    }
}

addBigNumber accepts 2 number-arrays, adds them and puts the result in a third array. If the target array is too small to hold the full result, the function will return OVERFLOW to signalize that the result is not accurate. This basic example really works as it should, and can theoretically add two unlimited big numbers.
Of course this is a LOT slower than the normal +, as + is a native processor operation and so takes just a few ticks, but it is still fast enough to be used in normal scripts (250000 additions/sec with 27-digit numbers).
Also any other operation (* / - ^ < > ...) can be implemented the same or at least a similar way.

Example:

pawn Код:

// These big numbers are aligned in 9-digit blocks right-to-left
new n1[] = {356363461, 346452359, 993673499, 921945436, 934776456, 231543675, 135798642, 111111111};
new n2[] = {946783486, 124869357, 934569257, 123456789, 987654321, 165776555, 999999999, 999999999};
new result[10];     
new w1[96], w2[96], res[96];        

addBigNumber(n1, n2, result);
        
formatBigNumber(n1, w1);
formatBigNumber(n2, w2);
formatBigNumber(result, res);
printf("%s + %s = %s", w1, w2, res);

/* Output:
   111111111135798642231543675934776456921945436993673499346452359356363461
+  999999999999999999165776555987654321123456789934569257124869357946783486
= 1111111111135798641397320231922430778045402226928242756471321717303146947
*/

Long post again.. but mostly code
What do you think about this way of calculation? Is it worth talking about it, or has even anyone else already thought about it?

[Joe Staff]

I actually like that, the method I had thought of using was just doing manual math with stringed numbers. Unfortunately it would be hugely limited to comparison, addition and subtraction without doing too much to the CPU.