Tuesday, June 3, 2014

Handle Big Integers with the Class BigInteger

As in nearly every programming language also in C# the standard data types are limited in size, they cannot hold numbers of arbitrary size. Today I want to show how to handle numbers of virtually any size. For this we use the datatype BigInteger, which can represent integers. It can be found in the namespace System.Numerics, which we have to include first: For this we chose Project - Add Reference and then select System.Numeric under Assemblies.
Now we can use the desired data type, which is a struct and provides many useful functions.
The following code creates 2 BigInteger numbers and adds them:
System.Numerics.BigInteger A = new System.Numerics.BigInteger(100);
System.Numerics.BigInteger B = new System.Numerics.BigInteger(200);
System.Numerics.BigInteger Result = System.Numerics.BigInteger.Add(A, B);

As you can see BigInteger provides a static function for adding two numbers. Of course there are also functions for multiplication etc. But in C# operators can be overloaded, which is also done here, and thus we can use BigInteger numbers like other standard datatypes. The following code is equivalent to the one above:
System.Numerics.BigInteger A = 100;
System.Numerics.BigInteger B = 200;
System.Numerics.BigInteger Result = A + B;

For exponentiating though there is no overload, because we use for this the static function Math.Pow(), which expects 2 double values. Therefor, we use the function BigInteger.Pow().
Finally some remarks about division: Since, as already mentioned, BigInteger can only represent integers, with this you cannot conduct an exact division. On the one hand you could use the class BigRational, which I will present in the next post.
Often though you can also rearrange the code, so that the numbers first become smaller and then use a double or similiar for divison.
Or, you use the following interesting trick:

double Result = Math.Exp(System.Numerics.BigInteger.Log(A) - System.Numerics.BigInteger.Log(B));

Because of the power laws A / B = Exp(Log(a / b)) = Exp(Log(a) - Log(b)). The logarithms greatly reduces the numbers A and B, the result is a double - so if the range of values is sufficient, this way a floating point division can be conducted.
But of course this way, depending on the numbers, a lot of precision can be lost.

No comments:

Post a Comment