Gunnar Peipman's ASP.NET blog : Algorithms

.Net Framework 4.0: Introducing BigInteger

DigiMortal — Sat, 23 May 2009 08:28:00 GMT

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.

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.

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.

Performance of Fibonacci numbers algorithms

DigiMortal — Sat, 23 May 2009 00:19:00 GMT

Performance of algorithms is important topic if you want to write programs that work fast and doesn’t eat too much resources. In this example I will show you two implementations of famous Fibonacci numbers algorithm and let you compare how these two implementations perform. This posting will be also introduction to my next posting to keep it smaller and to keep focus on point.

You can read more about Fibonacci numbers from Data Structures and Algorithms with Object-Oriented Patterns in C#, chapter Example-Fibonacci Numbers.

Recursive implementation

Our first implementation of Fibonacci numbers uses recursive algorithm. Recursive algorithm is very short and also easy to read.

public int FibonacciRecursive(int x)

    if (x == 0 || x == 1)

        return x;

    return FibonacciRecursive(x - 1) +

           FibonacciRecursive(x - 2);

VB.NET

Public Function FibonacciRecursive(ByVal x As Integer) As Integer
   If x = 0 OrElse x = 1 Then
       Return x
   End If

   Return FibonacciRecursive(x - 1) + FibonacciRecursive(x - 2)
End Function

Experienced programmers should see here two dangers. First of them gets clear to others at the end of this posting. Second of them is simple: recursive code is harder to debug than flat code.

Flat implementation

The other implementation is not so short but it doesn’t call our algorithm again and again. It is also not so easy to read as first implementation.

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

Before I say anything else let’s compare performance of those implementations.

Performance

Now let’s see how these implementations perform. I am sure that less experienced programmers will check if these implementations give same results and they will try them with pretty small inputs. But… look at the results.

Performance results of recursive and flat implementations of
Fibonacci numbers algorithm.

Horizontal axis shows input integers. Vertical axis shows us time in seconds that calculation took. For smaller inputs both implementations perform very well. Near 30 performance of recursive implementations starts going worse. For the time of last input (that is 41) we are sure that recursive implementation is a highway to hell. But performance of flat implementation is still okay.

This example is good illustration why we must test all the implementations we have before making decision which implementation to use.

Update: Bart Czernicki asked in his comment about F# performance when using recursive calls. I tried it out and F# performs very well in this scenario. In F# you can use recursive calls without any problems as my tests showed me.