Gunnar Peipman's ASP.NET blog

ASP.NET, C#, SharePoint, SQL Server and general software development topics.

Sponsors

News

 
 
 
DZone MVB

Links

Social

.Net Framework 4.0: Introducing BigInteger

My previous posting was about performance of Fibonacci numbers algorithms. In this posting I will introduce you some problems related to limits of our usual integers and introduce you new feature in .Net Framework 4.0 – big integers. Big integers are useful when solving different mathematical problems. Also they are used in cryptography.

As a first thing let’s see the problem we may face when we use our usual integers. Let’s use faster implementation of Fibonacci numbers algorithm so we don’t have to wait a long time to get results we need.

C#
public int Fibonacci(int x)
{
    var previousValue = -1;
    var currentResult = 1;
 
    for (var i = 0; i <= x; ++i)
    {
        var sum = currentResult + previousValue;
        previousValue = currentResult;
        currentResult = sum;
    }
 
    return currentResult;
}

VB.NET


Public Function Fibonacci(ByVal x As Integer) As Integer 
    Dim previousValue = -1 
    Dim currentResult = 1 
     
    For i = 0 To x 
        Dim sum = currentResult + previousValue 
        previousValue = currentResult 
        currentResult = sum 
    Next 
     
    Return currentResult 
End Function

Input Actual Expected
40 102334155 102334155
41 165580141 165580141
42 267914296 267914296
43 433494437 433494437
44 701408733 701408733
45 1134903170 1134903170
46 1836311903 1836311903
47 -1323752223 2971215073
48 512559680 4807526976
49 -811192543 7778742049
50 -298632863 12586269025

Now let’s take some value range where we can expect big numbers as result. Let’s take range from 40 to 50 and compare the results of our algorithm with expected results.

We can see that starting from 47 our results are different. 47 is the point where we go over integer limits and then we go to “next round” in integer scope. Same thing happens also with unsigned integer, long and unsigned long.

If we take some bigger input for our algorithm then we will get even larger numbers. 47 is small number and I am sure that scientific calculations use usually bigger inputs too and breaking over the limits of used type is almost sure.

You may also consider some other algorith that produces faster growth of results. Perfect candidate for this is factorial algorithm. By example 40! = 815915283247897734345611269596115894272000000000.

Introducing BigInteger class

.Net Framework 4.0 solves our problem. New namespace System.Numerics contains class called BigInteger. You can use objects based on this class as usual integers. This class also provides static methods for different mathematical operations on big integers. Let’s move now to BigInteger class with our Fibonacci numbers algorithm.

C#
public BigInteger Fibonacci(int x)
{
    var previousValue = new BigInteger(-1);
    var currentResult = new BigInteger(1);
 
    for (var i = 0; i <= x; ++i)
    {
        var sum = currentResult + previousValue;
        previousValue = currentResult;
        currentResult = sum;
    }
 
    return currentResult;
}

VB.NET


Public Function Fibonacci(ByVal x As Integer) As BigInteger
    Dim previousValue = New BigInteger(-1)
    Dim currentResult = New BigInteger(1)
    
    For i = 0 To x
        Dim sum = currentResult + previousValue
        previousValue = currentResult
        currentResult = sum
    Next
    
    Return currentResult
End Function

When we run this code we get expected results.

Some words about BigInteger structure

BigInteger is structure by its nature. It has bunch of static methods that let you perform different mathematical operations on BigIntegers. There are also many operators and type conversions defined for BigInteger so you can use BigIntegers like usual integers. Take look at the BigInteger members documentation.


kick it on DotNetKicks.com pimp it Progg it Shout it

Comments

Sachin Joseph said:

Although .NET BigInteger provides fewer methods than Java's, the .NET Framework 4 BigInteger is atleast twice faster than Java for the operations like addition, subtraction, multiplication, division, etc in my stress tests on the same machine.

# March 11, 2010 11:17 PM