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

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  = the numbers most to the right [n-max] = numbers most to the left

Ex. Num: 29392023 Array:23, Array: 20, array: 39, array: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 is the same place as the first digit (from the right) of array.

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.

• 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

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.

• 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
• 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
• "doing math on base 256 is easier than base 88". False. They're equally easy. – S.Lott Jan 21 '12 at 0:54
• @S.Lott: um... when you have bitwise operations available, doing math on base 256 is definitely easier than base 88. – Jason S Jan 21 '12 at 15:17
• Building your own add/subtract/multiply is fairly straightforward. Division is difficult, though, unless you're implementing it in binary, where it becomes an exercise in conditional subtraction and bit-shifting. – Jason S Jan 21 '12 at 15:18

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.

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);

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());

int add = int1 + int2 + remainder;

//Check to see if we need a remainder;
{
remainder = 1;
}
else
{
remainder = 0;
}

}

//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.

• Cool!! Thanks it helps clear things up with remainders I would have over complicated that extra bit. – Mallow Jan 20 '12 at 22:12

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();

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();
}
``````
• This site is about conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler – gnat Apr 30 '17 at 6:40
• This site is EXCHANGE, so we try to help each other as much has we can. Maybe I should do such comments in StackOverflow, but I tried to help with my approach. If someone still needs an explanation, he will ask for it. I do here a standard mathematical addition digit by digit, starting from the end. – Andranik Sargsyan May 1 '17 at 10:51
• Agree with gnat. At least explain the algorithm before dumping code. – Frank Hileman May 1 '17 at 18:51
• Just dumping code with no explanation is like encouraging the copy-past-and-go. I don't see how that could be useful in SoftwareEngineering. Maybe at StackOverflow is, but both sites actually have totally different purposes. – Laiv May 24 '17 at 6:40