Handling extremely large numbers in a language which can't?

Question

I'm trying to think about how I would go about doing calculations on extremely large numbers (to infinitum - intergers no floats) if the language construct is incapable of handling numbers larger than a certain value.

I am sure I am not the first nor the last to ask this question but the search terms I am using aren't giving me an algorithm to handle those situations. Rather most suggestions offer a language change or variable change, or talk about things that seem irrelevant to my search. So I need a little guideance.

I would sketch out an algorithm like this:

1. Determine the max length of the integer variable for the language.

2. If a number is more than half the length of the max length of the variable split it in an array. (give a little play room)

3. Array order [0] = the numbers most to the right [n-max] = numbers most to the left

   Ex. Num: 29392023 Array[0]:23, Array[1]: 20, array[2]: 39, array[3]:29

Since I established half the length of the variable as the mark off point I can then calculate the ones, tenths, hundredths, etc. Place via the halfway mark so that if a variable max length was 10 digits from 0 to 9999999999 then I know that by halfing that to five digits give me some play room.

So if I add or multiply I can have a variable checker function that see that the sixth digit (from the right) of array[0] is the same place as the first digit (from the right) of array[1].

Dividing and subtracting have their own issues which I haven't thought about yet.

I would like to know about the best implementations of supporting larger numbers than the program can.

Answer 1

You are looking for an arbitrary precision arithmetic (also called "multiple precision" or "big num") library for the language you are working with. For instance, if you are working with C you can use the GNU Bignum Library -> http://gmplib.org/

If you want to understand how it works you can also write your own big num library and use it. The simplest way to handle this is with arrays, where each element is a digit of the number you are working with. After that you need to implement all the functions to add, subtract, multiply, divide, exponentiate and so on.

Answer 2

It is a well known problem: Arbitrary precision arithmetic

When the language you are using doesn't resolve this problem, first try to find a third party library that does. If you don't find it or you are curious, try to implement it; the wikipedia article has a good references to classical implementations.

Answer 3

When dealing with large numbers, probably one of the most fundamental design decisions is how am I going to represent the large number?

Will it be a string, an array, a list, or custom (homegrown) storage class.

After that decision is made, the actual math operations can be broken down in smaller parts and then executed with native language types such as int or integer.

I've included a very rudimentary ADDITION example in C# .Net that stores the resulting large number as a string. Incoming "numbers" are also strings, so one should be able to send in very "large" numbers. Keep in mind that the example is only for whole numbers to keep it simple.

Even with strings there is a limit in the number of characters or "numbers" in the number, as indicated here:

What is the maximum possible length of a .NET string?

But you could add some really big numbers, way beyond int32 or int64 native types for .Net.

Anyway, here's a string storage implementation.

/// <summary>
/// Adds two "integers".  The integers can be of any size string.
/// </summary>
/// <param name="BigInt1">The first integer</param>
/// <param name="BigInt2">The second integer</param>
/// <returns>A string that is the addition of the two integers passed.</returns>
/// <exception cref="Exception">Can throw an exception when parsing the individual parts     of the number.  Callers should handle. </exception>
public string AddBigInts(string BigInt1, string BigInt2)
{
    string result = string.Empty;

    //Make the strings the same length, pre-pad the shorter one with zeros
    int length = (BigInt1.Length > BigInt2.Length ? BigInt1.Length : BigInt2.Length);
    BigInt1 = BigInt1.PadLeft(length, '0');
    BigInt2 = BigInt2.PadLeft(length, '0');

    int remainder = 0;

    //Now add them up going from right to left
    for (int i = (BigInt1.Length - 1); i >= 0; i--)
    {
        //If we don't encounter a number, this will throw an exception as indicated.
        int int1 = int.Parse(BigInt1[i].ToString());
        int int2 = int.Parse(BigInt2[i].ToString());

        //Add
        int add = int1 + int2 + remainder;

        //Check to see if we need a remainder;
        if (add >= 10)
        {
            remainder = 1;
            add = add % 10;
        }
        else
        {
            remainder = 0;
        }

        //Add this to our "number"
        result = add.ToString() + result;
    }

    //Handle when we have a remainder left over at the end
    if (remainder == 1)
    {
        result = remainder + result;
    }

    return result;
}

I hope that gives you some ideas on your own implementation. Please note, that the sample code probably isn't optimized or anything like that. It is meant to give some ideas of how it could be done.

Answer 4

This one works faster for me:

static string Add(string a, string b)
        {
            string c = null;

            if (Compare(a, b) < 0)
            {
                c = a;
                a = b;
                b = c;
            }

            StringBuilder sb = new StringBuilder();

            b = b.PadLeft(a.Length, '0');

            int r = 0;

            for (int i = a.Length - 1; i >= 0; i--)
            {
                int part = a[i] + b[i] + r - 96;

                if (part <= 9)
                {
                    sb.Insert(0, part);

                    r = 0;
                }
                else
                {
                    sb.Insert(0, part - 10);

                    r = 1;
                }
            }

            if (r == 1)
            {
                sb.Insert(0, "1");
            }

            return sb.ToString();
        }