At last! I have been waiting for a built-in BigInteger data type for .NET ever since .NET 1.0 was released. The .NET Framework version 4.0 adds this type in a new System.Numerics namespace. The BigInteger type allows arbitrarily large integers. This is useful for a wide range of mathematical functions including functions which compute the number of permutations of n items, and the number of combinations of n items taken k at a time (where order does not matter) — two fundamental computations in software testing. For example, the number of permutations of n items is just Factorial(n) = n * (n-1) * (n-2) * . . . 1. If you code a naive version of Factorial() using type long, the largest value which can be represented is +9,223,372,036,854,775,807 which seems pretty big but this will only deal with a result of up to Factorial(20). For example:

static long FactorialBad(int n)

{

long answer = 1;

if (n < 0) throw new Exception("xxx");

if (n == 0) return 1;

{

long answer = 1;

if (n < 0) throw new Exception("xxx");

if (n == 0) return 1;

for (int i = 1; i <= n; ++i)

answer *= i;

answer *= i;

return answer;

}

}

will compute Factorial(20) correctly but Factorial(21) returns -4,249,290,049,419,214,848. The function loop hits long.MaxValue and then silently wraps around to long.MinValue (a negative number) and continues and ends up negative. But:

static BigInteger FactoriaBigInt(int n)

{

BigInteger answer = 1;

if (n < 0) throw new Exception("xxx");

if (n == 0) return 1;

{

BigInteger answer = 1;

if (n < 0) throw new Exception("xxx");

if (n == 0) return 1;

for (int i = 1; i <= n; ++i)

answer *= i;

answer *= i;

return answer;

}

}

can deal with very, very large values. By the way, in many cases using a lookup table to perform factorial computations is a much better approach than using the approach I showed here.

Advertisements