Jump to content

Big Integer addition/subtraction


Mollymews
 Share

Recommended Posts

a conversation here

peaked me so I had a go at doing this.  I haven't tested every combination but it seems to be ok. If not let me know and I fix it

 

edit delete code: problem with really long numbers when a is positive and b is negative and b is really long

edit fixed: issue with BigIntCompare return codes. Should be ok now

//  Sum two strings of integer characters
//
//  simulate arithmetic, right to left addition and subtraction
//  example usage:
//    ( "100",   "10") =  "110"
//    ( "100",  "-10") =   "90"
//    ("-100",   "10") =  "-90"
//    ("-100",  "-10") = "-110"
//    (  "10",  "100") =  "110"
//    (  "10", "-100") =  "-90"
//    ( "-10",  "100") =   "90"
//    ( "-10", "-100") = "-110" 
//  
//  - strings can be bignums > 32 bits
//  - it doesn't do floats 
//  - there is no input error checking
//
//  like all my posts in Scripting Library this code is public domain   

string BigIntSum(string a, string b)
{    
    // get negative sign if any
    integer signa = (llOrd(a, 0) == 45); // 45 is "-"
    integer signb = (llOrd(b, 0) == 45);
    // strip the sign char if any
    if (signa) a = llDeleteSubString(a, 0, 0);
    if (signb) b = llDeleteSubString(b, 0, 0);
    // get length of longest string
    integer orda = llStringLength(a);
    integer ordb = llStringLength(b);
    integer len = orda;
    if (ordb > orda) len = ordb;   
    // do swap when neccessary
    string result;
    integer swap;
    if (signa != signb)  // one is positive, the other is negative
    {   // so swap when abs(a) < abs(b)
        swap = !BigIntCompare(a, b);
        if (swap) 
        {
           result = a; a = b; b = result;               
        }            
    }
    // sum
    result = "";
    integer carry;
    integer i; 
    // Note: this could be done more efficiently by stopping when length(shortstring) is reached        
    for (i = -1; i >= -len; i--)
    {
        orda = (integer)llGetSubString(a ,i ,i);
        ordb = (integer)llGetSubString(b ,i ,i);
        if (signa == signb)  // both positive or both negative
        {   // so do addition
            orda += ordb + carry;
            result = (string)(orda % 10) + result;
            carry = (orda > 9);
        }
        else // one is positive, the other is negative
        {   // so do subtraction
            ordb += carry;
            result = (string)(10 * (orda < ordb) + orda - ordb) + result;
            carry = (orda < ordb);                          
        }
    }
    // finally
    if (signa == signb)
    {   // preppend carry and do sign
        if (carry) result = (string)carry + result;
        if (signb) result = "-" + result;
    }
    else
    {   // strip any leading zeros and do sign
        while (((llOrd(result, 0) == 48)) & (llStringLength(result) > 1))  // 48 = "0"
            result = llDeleteSubString(result, 0, 0); 
        if (signb == swap) result = "-" + result;
    }
    return result;
}

integer BigIntCompare(string a, string b)
{   // return 0 when b > a, 1 when a > b, 2 when a == b
    // get negative sign if any
    integer signa = (llOrd(a, 0) == 45); // 45 is "-"
    integer signb = (llOrd(b, 0) == 45);
    if (signa == signb)  // both positive or both negative
    {
        // insert leading 0s when neccessary
        integer len = llStringLength(a) - llStringLength(b);
        if (len < 0)
            while (len++) a = llInsertString(a, signa, "0");
        else if (len > 0)
            while (len--) b = llInsertString(b, signa, "0");
        // compare ordinals left to right, break when different 
        len = llStringLength(a);
        integer i;
        for (i = signa; i < len; i++)
        {
            integer orda = llOrd(a, i);
            integer ordb = llOrd(b, i);            
            if (orda != ordb)
                return (orda > ordb) ^ signa; 
        }   
        return 2;  // a == b 
    }
    // one is positive, the other is negative
    return (signa < signb); 
} 

default
{
    touch_start(integer total_number)
    {           
        string a = (string)(((integer)llFrand(1000) - 500));
        string b = (string)(((integer)llFrand(1000) - 500));        
        string result = BigIntSum(a, b);        
        llOwnerSay(llDumpList2String(["sum:", a, b, "=", result], " "));
        
        a = llList2String(["-", ""], (integer)llFrand(2)) + (string)((integer)llFrand(9) + 1);
        integer len = (integer)llFrand(16) + 1;
        while(~--len) a += (string)((integer)llFrand(10));
        b = llList2String(["-", ""], (integer)llFrand(2)) + (string)((integer)llFrand(9) + 1);
        len = (integer)llFrand(16) + 1;
        while(~--len) b += (string)((integer)llFrand(10));
        result = BigIntSum(a, b);                
        llOwnerSay(llDumpList2String(["sum:", a, b, "=", result], " "));       
        
        integer compare = BigIntCompare(a, b);                
        llOwnerSay(llDumpList2String(["cmp:", a, b, "=", compare], " "));   
    }
}

 

Edited by Mollymews
tiny efficiency and a typo in the test
  • Like 1
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...