Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
First thing that comes to mind is Java's BigInteger: docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html –  Ivan Jan 20 '12 at 20:52
    
Is this a language that anyone here might know and be able to make specific recommendations, or is it something obscure and proprietary? –  FrustratedWithFormsDesigner Jan 20 '12 at 21:02
    
I don't know which language I would want this for yet. I know php the most but I don't want to do it in that language. Lisp is attractive since from what I've read it has no limits for length. However my personal flaw of wanting to know how it works makes me want to have the liberty to do it in qbasic if I were stuck on an island. (It's for fun too, I'm always thinking about calculating large numbers and some online calculators are too cumbersome for the task.) –  Mallow Jan 20 '12 at 21:08
add comment

4 Answers

I developed a class in C# to do this. At its core it uses an array of Int32. You can get to the code from this page on my blog.

share|improve this answer
add comment

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.

share|improve this answer
    
Where each element is a digit of the number you are working with!! Woah, you blew my mind, why didn't I think of that? Thank you for the proper vocabulary and the link, I think this is exactly what I want. ^_^ –  Mallow Jan 20 '12 at 20:56
3  
of course "digit" is relative, many bignum libraries use digits in base 256 (unsigned byte[]) to 2^64 (unsigned long[]) –  ratchet freak Jan 20 '12 at 20:57
1  
Just making sure I understood, 'digit' could be an array of base 256 digits? I think I might be mistaken, doing math on base 256 is easier than base 88 but still quite a task... (At least when I did it last night on a sheet of paper haha) –  Mallow Jan 20 '12 at 21:16
    
@Mallow, there are different ways to implement it. I would keep it simple, though, making each digit go from 0 to 9. So you can use an array of ints or even chars to save some memory, and the size of the array is the maximum number of digits on the numbers you want to work with. –  daniels Jan 20 '12 at 21:28
1  
"doing math on base 256 is easier than base 88". False. They're equally easy. –  S.Lott Jan 21 '12 at 0:54
show 4 more comments

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:

http://stackoverflow.com/questions/140468/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.

share|improve this answer
    
Cool!! Thanks it helps clear things up with remainders I would have over complicated that extra bit. –  Mallow Jan 20 '12 at 22:12
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.