## วันพุธที่ 19 ธันวาคม พ.ศ. 2550

### BigInteger, an integer with unbounded length

Usaully, when you think of number, Int32 almost covers all requirements. Its maximum value is 2,147,483,647. It almost never overflow. Int32 is not enough? That's very rare case. But you can using Int64 which its maximum value is 9,223,372,036,854,775,807 which considers an extreamly large number. Is it possible that an operation will make Int64 be overflown? It is possible. In mathematics and cryptography, large precision calculation is needed, and data length of an integer can be extended indefinitely.

Which type shall we use next to Int64? If your answer is Int128, the answer is wrong. Next class we gonna use has no length limitation. It is an integer with unbounded length. This type is called BigInteger.

BigInteger is not included in current C# package. But now you can find BigInteger in Silverlight package. Once you install Silverlight, BigInteger can be found in [drive]:\Program Files\Microsoft Silverlight\Microsoft.Scripting.dll under the namespace Microsoft.Scripting.Math.

Let's play around BigInteger (question from projecteuler.net) :)
Find the sum of digits in 100!

BigInteger bigInt = 1;
100.DownTo(2).ForEach(x => bigInt *= x);    //Factorial 100!
Console.WriteLine(bigInt.ToString(10).Sum(c => (int)(c - '0')));    //Sum of Digit
//648

More question :)
What is the sum of the digits of the number 21000?

BigInteger bi = 1;
1000.Times(x => bi *= 2);    //21000
Console.WriteLine(bi.ToString(10).Sum(c => (int)(c - '0')));    //Sum of Digit
//1366

Factorial of 100 and 2 power by 1000, Int64 is generally unable to handle above questions. But BigInteger can handle it easily and fast.

As a bonus, I had written some Extensions for BigInteger. First method is for getting sum of a list of BigInteger.

public static BigInteger Sum(this IEnumerable<BigInteger> source) {
BigInteger num = BigInteger.Zero;
foreach (BigInteger num2 in source)
num += num2;
return num;
}
public static BigInteger Sum<T>(this IEnumerable<T> source, Func<T,BigInteger> selector) {
return source.Select(selector).Sum();
}

Usage:

var list = new BigInteger[] { 1, 2, 3 };
Console.WriteLine(list.Sum());
//6

Next method is for parsing string into BigInteger:

public static BigInteger Parse(string s) {
char[] buffer = new char[10];
int startIndex = 0;
uint[] multiplier = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };

BigInteger ret = int.Parse(new string(buffer, 0, count));
if (ret.IsNegative())
startIndex = 1;

while (count == 9) {
ret *= multiplier[count];
ret += int.Parse(new string(buffer, 0, count + startIndex));
}
return ret;
}
}
public static bool TryParse(string s, out BigInteger result) {
try {
result = Parse(s);
return true;
} catch {
result = null;
return false;
}
}

Usage

BigInteger i = BigIntegerExtension.Parse("1234567890");
Console.WriteLine(i);
//1234567890

Next post, I will show you somethings bigger than BigInteger :)