Jump to content

Adding/working with BIG numbers (Larger than integer limit)


You are about to reply to a thread that has been inactive for 2404 days.

Please take a moment to consider if this thread is worth bumping.

Recommended Posts

So I'm working on a project in which I need to be able to store and work with numbers that exceed the integer size limit.

To try and break-out of the integer limitations, I have written a script that adds two strings instead:

string str1 = "123456789";
string str2 = "123456789123456";

string StringPad(string source, integer number)
{
    string str = "";
    integer x;
    for (x = 0; x < number; x++)
    {
        str += "0";    
    }
    return str + source;
}

string StringLeftTrim(string source)
{
    integer x = 0;    
    string str = llGetSubString(source, 0, 0);
    while (str == "0")
    {
        str = llGetSubString(source, x, x);
        ++x;    
    }
    return llGetSubString(source, x - 1, -1);
}

string StringReverse(string source)
{
    string str;
    integer x;
    integer len = llStringLength(source);
    for (x = 1; x <= len; x++)
        str += llGetSubString(source, len - x, len - x);
    return str;
}

string BigIntAdd(string st1, string st2)
{
    integer carry = 0;
    integer length1 = llStringLength(st1);
    integer length2 = llStringLength(st2);
    string final = "";
    integer dif;
    integer i;
    llSay(0,st1+"+"+st2);
    if(length1 < length2)
    {
        dif = length2-length1;
        st1 = StringPad(st1,dif);
    }
    else if(length1 > length2)
    {
        dif = length1-length2;
        st2 = StringPad(st2,dif);
    }
    else if(length1 == length2)
    {
        dif = length1;
    }
    length1 = llStringLength(st1);
    length2 = llStringLength(st2);

    do
    {
        integer i1 = (integer)llGetSubString(st1,length1,length1);
        integer i2 = (integer)llGetSubString(st2,length2,length2);
        integer i3 = i1 + i2 + carry;
        if(i3 > 9)
        {
            carry = 1;
            i3 = i3 - 10;
        }
        else
        {
            carry = 0;
        }
        final+=(string)i3;
        length1--;
        length2--;
    }
    while(length1 >= 0);
    
    //final+=(string)carry;
    final = StringLeftTrim(final);
    final = StringReverse(final);
    final+=(string)carry;
    //final
    return final;
}

default
{
    state_entry()
    {
        llListen(123,"",llGetOwner(),"");
    }
    
    touch_start(integer total_number)
    {
        llSay(0, BigIntAdd(str1,str2));
    }
    
    listen(integer ch, string n, key id, string msg)
    {
        list tmp = llParseString2List(msg,["+"],[]);
        llSay(0,BigIntAdd(llList2String(tmp,0),llList2String(tmp,1)));
    }
}

 

There are however, a few issues.

  1. The 'carry' integer adds an additional 0 onto the end of the final string when it is not needed, but not when the number actually does end on 0 (from what i've seen.)
  2. Adding two numbers that round up can cause interesting results. (5+5, 555+55555055, 999+999 etc)
  3. I'm sure this could be optimised further.

If anyone could enlighten me as to why this is happening, or have suggestions for optimisation I'd greatly appreciate it!

Link to post
Share on other sites

I'm not sure if this is an exercise or something intended for use. If the latter (and if it's important to do the computation in-world), maybe look at an earlier open LSL bignum implementation.

(A general observation: manipulating LSL strings to do bignum calculations seems doomed to extreme inefficiency, both in memory and especially in speed, but maybe there's a way. If, however, I were forced to use strings, I'd probably investigate using characters other than base ten digits.)

  • Like 2
Link to post
Share on other sites

Thanks for the reply Qie.

The bignum implementation that you linked isn't really suitable for the numeric manipulation i'm working with. What it all boils down to really is just adding 2 numbers that exceed the integer size limit. From there everything else becomes easy.

The current implimentation I have is very basic, and ALMOST works. And isnt too intensive as it stands. I'm guessing there is something wrong with my logic that causes the output to behave in such a strange manner.

Your suggestion to use characters other than base ten is a good one, and could speed things up as numbers get larger and larger. I'll definately look into this after the logic has been fixed!

Link to post
Share on other sites

in your codes the extra 0 is appended bc is not checking for carry > 0 on last. also the other issue is that length1 on start is overflowing

+

if you just want something short and brutal and is not going to be running in a loop or on any fast timer then:

 

string SumStrs(string a, string b){  integer length = llStringLength(a);  if (llStringLength(b) > length)    length = llStringLength(b);   integer carry;  string result;    integer i;  for (i = -1; i >= -length; i--)  {    integer sum =       (integer)llGetSubString(a, i, i) +      (integer)llGetSubString(b, i, i) +      carry;    carry = (sum > 9);    if (carry)      sum -= 10;    result = (string)sum + result;  }  if (carry)     result = (string)carry + result;  return result; }default{  touch_start(integer total_number)  {    string a = "900909";    string b = "999";    llOwnerSay(a + " + " + b + " = " + SumStrs(a, b));  }  }

 

i havent done any exhaustive tests on it. Have just done off the top of my head. I think is ok but best to check tho

is no pre-validation either in this example code. like checking for valid inputs 0..9 or trimming leading 0s. you would have to add that

can use or not as you like and mod/do whatever you like also

  • Like 1
Link to post
Share on other sites

should add that if in production you find that is lots of inputs of substantial dif lengths like:

12345678901234567890 + 987654321

then be best to optimise by tracking the shortest length and break out of the loop after end of the shorter when carry = 0. Copy any remainder of the longer string in one pass rather than single stepping all the way to the end

 +

edited to try explain the logics better

  • Like 1
Link to post
Share on other sites


Titty Luv wrote:

How much of a hastle would it be to alter this to do subtractions? I'm guessing that the same basic prinipal stays the same, but the carry is treated differently?

you now getting into building a library (:

if so then you maybe best in that case to go with Qie's suggestion

+

but if just doing yourself to learn and/or just want go down the string way then be best to read up a bit on the wiki how LSL string handling works. How negative indexing (right-to-left) works. Why you get a empty string when the index under or over flows. And other stuff like that

+

on the sub algo (like add, mul, div also) is the same as if you were doing on paper. For sub is a borrow instead of a carry. For example some pcode

 

borrow = 0do (right-to-left){  bottom += borrow  borrow = (top < bottom) // will be either 1 or 0  if (borrow) top += 10  sum = top-bottom  prefix sum to result}if (borrow) prefix "-" to result

 

 

 

 

  • Like 1
Link to post
Share on other sites

Follow Qie's advice; irihapeti's approach doesn't take into account the signs of the addends and, if one of them is negative, you are doing a subtraction and may end up with a negative number.

 

Though BigNum has a lot more features than you think you require, a study of it will show exactly what you need to extract out of it to implement what you need. The list and integer manipulations there will be far better than anything cobbled together using strings. 

  • Like 1
Link to post
Share on other sites


LepreKhaun wrote:

Follow Qie's advice; irihapeti's approach doesn't take into account the signs of the addends and, if one of them is negative, you
are
doing a subtraction and may end up with a negative number.
 

yes agree

OP asked about summing positive numbers encoded in strings and then follow up with asking about subtracting them. So show the general algo for that. If OP did want to work with negative inputs then would probably have raised it in the convo before now

 

Link to post
Share on other sites

Exactly- when the specifications begin changing, then one just goes with the wheel that's already been invented. Otherwise, we may end having to explore multiplication next.

 

No harm in that except any possible string manipulation is going to prove inferior to the list and integer manipulations given in BigNum, especially the effect working with long strings under Mono has on heap memory usage.

Link to post
Share on other sites

 

one of the problems that newbie scripters of any language have is they don't always know/understand the basic algorithms. They sometimes/often view it as a tools/language problem/difficulty. Can see this in this OPs codes. pad, trim, reverse. When see this then can also know that they likely to have some experience in Basic, Pascal or similar. OP is applying their tools knowledge to the problem

OP then ask about using carry in a subtraction. Is a clear indicator this of their level of algo understanding at this time in their development

So. Take them back to the beginning. Algo 101. Have them learn the basics of addition and subtraction by showing/giving algo examples. When they got this worked out then they can more easy move on to other bases. Like base 65536 or whichever

if dump newbie straight into base 65536 without any, or little, algo knowledge/understanding then they will come back with: I have no idea what those codes are doing. Which is what happened here. OP has no idea bc OP need to learn the algos first

yes agree that LSL strings are more inefficient than LSL lists, but thats a tool thing. For me algos are far more important. Can always read/write/optimise/refactor codes a lot faster and easier change to other tools/languages when got a good understanding of algo construction

 

Link to post
Share on other sites
You are about to reply to a thread that has been inactive for 2404 days.

Please take a moment to consider if this thread is worth bumping.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...