Strict Standards: Declaration of action_plugin_importoldchangelog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/importoldchangelog/action.php on line 8

Strict Standards: Declaration of action_plugin_blog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/blog/action.php on line 154

Strict Standards: Declaration of action_plugin_include::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/include/action.php on line 140

Strict Standards: Declaration of action_plugin_importoldindex::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/importoldindex/action.php on line 57

Strict Standards: Declaration of action_plugin_discussion::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/discussion/action.php on line 955

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 205

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 208

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 389

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 530

Strict Standards: Declaration of cache_instructions::retrieveCache() should be compatible with cache::retrieveCache($clean = true) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/cache.php on line 291

Deprecated: Function split() is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/auth.php on line 154

Strict Standards: Only variables should be passed by reference in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/doku.php on line 71
nex code:c_sharp:fibonacci
 

Fibonacci Generator (fibcsharp)

And once again, a fairly acute Fibonacci sequence generator. This time written in the C# programming language. I wrote this in the first few weeks of my PhD to teach myself C# (as that is the programming language used in the research group I am in). Technically this is again a conversion of the Ada version of the program that I wrote in second year Computing Science. However, since C# is so dang similar to Java, it's actually a conversion of the Java version.

I have to say that C# is much more similar to Java than I had realised. In fact, this code is almost the same as the Java version. That being the case, there are only subtle differences between them. In particular, the way C# deals with deep copying objects is quite different. I think I prefer the C# system of doing that though. Also, the accessability settings for objects are quite different as well, and in that instance I'm not sure I prefer either system. It's also worth saying that this version runs slower than I would have thought. Even my Java Applet version runs quicker than the C# implementation (which is certainly an issue that is important since Microsoft are selling C# as faster than Java).

I should also point out that I have only been learning C# for a day or two now and I'm sure that my previous knowledge of Java has led me to do some not very 'C#-ish' things in my code (which may account for why this version is so slow). You may find that the code on this page will change as I get more experience with the C# language.

Description

The Fibonacci algorithm was invented by an Italian mathematician (Fibonacci) to predict rabbit growth. A lot of assumptions are made, some of which are a bit sillier than others:

Assume that you start with two rabbits.
Assume that once a rabbit is three years old, it is capable of mating.
Assume that all rabbits capable of mating will in fact mate.
Assume that every time two rabbits mate, one offspring is produced without failure; no more, no less.
Assume rabbits can only produce one 'litter' a year.
Assume that there is an almost equal number of male and female rabbits.
Assume rabbits never die.

Anyway, the interesting thing about the Fibonacci algorithm is that it can be implemented recursively, and the numbers get big VERY quickly. The most basic way of expressing the algorithm is shown below:

fib[n] = fib[n-1] + fib[n-2]

where fib[1] = 1, fib[2] = 1

The Source Code

You can download all the source code of the program here or view it below.

fibcsharp.cs:

/*--------------------------------------------------------------------------
----------------------------------------------------------------------------
--                                                                        --
--     Program Title : FibCSharp Version 0.01                             --
--     Author : nex                                                       --
--     Date Last Modified : 13th October 2006                             --
--                                                                        --
--     Description : This program takes in two integers from standard     --
--                   input and uses them as indices to calculate          --
--                   Fibonacci numbers from the lower to upper index.     --
--                                                                        --
--                   This program uses a large integer representation     --
--                   for large integer values produced by the Fibonacci   --
--                   algorithm (to prevent overflow).                     --
--                                                                        --
--     State of Program: The program has worked correctly for all test    --
--                       data.                                            --
--                                                                        --
----------------------------------------------------------------------------
--------------------------------------------------------------------------*/
 
using System;
 
 
// The BigInt class deals with large interger representation.
class BigInt : ICloneable
{
    // The BigIntList is a private class of BigInt.
    private class BigIntList : ICloneable
    {
        // I had to make these public so that they were accessible.
        public int val;
        public BigIntList next;
        public BigIntList prev;
 
        // Constructors
        // I had to make this public so that it was accessible.
        // Clearly there is a difference in the default privacy
        // levels of contructors in C# compared to Java.
        public BigIntList(int v)
        {
            val = v;
        }
        // end Constructors
 
 
        // Supply the cloneable method so that we can deep copy
        // objects of this class.
        public object Clone()
        {
            BigIntList temp = new BigIntList(val);
            if (this.next != null)
            {
                temp.next = (BigIntList) this.next.Clone();
            }
            if (this.prev != null)
            {
                temp.prev = (BigIntList) this.prev.Clone();
            }
            return temp;
 
        } //Clone
 
 
    } //class BigIntList
 
 
 
    // Private variables which allow BigInt to be a linked list 
    // representation of big integers.
    private BigIntList head;
    private BigIntList tail;
 
 
    // Constructors
    public BigInt(int v)
    {
        head = new BigIntList(v);
        tail = head;
    }
 
    public BigInt()
    {
        head = null;
        tail = null;
    }
    // end Constructors
 
 
    // Just a little function in case we want to change the output
    // style later on.
    private static void output(string forOut, bool LineFeed)
    {
        if (LineFeed)
        {
            Console.WriteLine(forOut);
        }
        else
        {
            Console.Write(forOut);
        }//end if
 
    } //output
 
 
    // Overloaded version of above function so that the
    // default behaviour is to include a line feed. I 
    // suppose this is technically bad coding style, but
    // it saves me a bit of typing.
    private static void output(string forOut)
    {
        Console.WriteLine(forOut);
 
    } //output
 
 
    // Supply the cloneable method so that we can deep copy
    // objects of this class.
    public object Clone()
    {
        BigInt temp = new BigInt();
        if (this.head != null)
        {
            temp.head = (BigIntList) this.head.Clone();
        }
        if (this.tail != null)
        {
            temp.tail = (BigIntList) this.tail.Clone();
        }
        return temp;
 
    } //Clone
 
 
    // Calculates x + y (both of type 'BigInt') and returns as type 
    // 'BigInt'. This method is specifically designed for the BigInt type 
    // of this program.
    public BigInt add(BigInt y)
    {
        BigInt xTemp, yTemp, r, rTemp;
        int c, s, p, q;
 
        // Clear variables of data.
        c = s = p = q = 0;
 
        // Initialise variables.
        xTemp = (BigInt) this.Clone();
        yTemp = (BigInt) y.Clone();
        r = new BigInt();
 
        // If 'this' or y have no values, return r (which will equal null).
        if ((this.head != null) || (y.head != null))
        {            
            // If there is still data in the current xTemp or yTemp or 
            // there is a carry, get intermediate values for use in 
            // equations.
            while((xTemp.head != null) || 
                 (yTemp.head != null) || (c == 1))
            {
                if ((xTemp.head == null) && (yTemp.head != null))
                {
                    q = yTemp.head.val;
                    yTemp.head = yTemp.head.next;
                    p = 0;
                }
                else if ((xTemp.head != null) && (yTemp.head == null))
                {
                    p = xTemp.head.val;
                    xTemp.head = xTemp.head.next;
                    q = 0;
                }
                else if ((xTemp.head == null) && (yTemp.head == null))
                {
                    p = q = 0;
                }
                else
                {
                    p = xTemp.head.val;
                    xTemp.head = xTemp.head.next;
                    q = yTemp.head.val;
                    yTemp.head = yTemp.head.next;
                }//end if
 
                // Use intermediate values to calculate sum and carry.
                if (r.head == null)
                {
                    s = ((p + q) % 1000);
                    c = ((p + q) / 1000);
                }
                else
                {
                    s = ((p + q + c) % 1000);
                    c = ((p + q + c) / 1000);
                }//end if
 
                // Add new nodes containing correct values to doubly linked 
                // list.
                if (r.head == null)
                {
                    r.head = new BigIntList(s);
                    r.tail = r.head;
                }
                else
                {
                    r.tail.next = new BigIntList(s);
                    rTemp = (BigInt) r.Clone();
                    r.tail = r.tail.next;
                    r.tail.prev = rTemp.tail;
                }//end if                
            }//end loop            
        }//end if
        return r;
 
    } //add
 
 
    // Returns the boolean expression 'x = y', where x = 'this', and y 
    // and x are both BigInt objects.
    public bool isEqual(BigInt y)
    {
        BigInt xTemp, yTemp;
        xTemp = (BigInt) this.Clone();
        yTemp = (BigInt) y.Clone();
 
        // Tests all possible cases in which x == y (or x != y),
        // using recursion to call all nodes.
        if ((xTemp.head != null) && (yTemp.head != null))
        {
            if (xTemp.head.val == yTemp.head.val)
            {
                xTemp.head = xTemp.head.next;
                yTemp.head = yTemp.head.next;    
                return (xTemp.isEqual(yTemp));
            }
            else
            {
                return false;
            }//end if
        }
        else if ((xTemp.head != null) && (yTemp.head == null))
        {
            return false;
        }
        else if ((xTemp.head == null) && (yTemp.head != null))
        {
            return false;
        }
        else if ((xTemp.head == null) && (yTemp.head == null))
        {
            return true;
        }
        else 
        {
            return false;
        }//end if
 
    } //isEqual
 
 
    // Outputs the value of the 'BigInt' type, 'x', to standard output.
    public void writeBig()
    {
        BigInt xTemp;
 
        xTemp = (BigInt) this.Clone();
 
        if (this.tail != null)
        {            
            // Extra zeros will need to be printed if current node value
            // is less than 100.
            if (this.tail.next != null)
            {
                if (this.tail.val < 100)
                {
                    if (this.tail.val <10)
                    {
                        output("00", false);
                    }
                    else
                    {
                        output("0", false);
                    }//end if
                }//end if
            }//end if
 
            // Output current node value then recursively call other node
            // values for output.
            output(Convert.ToString(this.tail.val), false);
            xTemp.tail = this.tail.prev;
            xTemp.writeBig();
 
        }//end if
 
    } //writeBig
 
 
} //class BigInt
 
 
 
class FibCSharp
{
    // Just a little function in case we want to change the output
    // style later on.
    private static void output(string forOut, bool LineFeed)
    {
        if (LineFeed)
        {
            Console.WriteLine(forOut);
        }
        else
        {
            Console.Write(forOut);
        }//end if
 
    } //output
 
 
    // Overloaded version of above function so that the
    // default behaviour is to include a line feed. I 
    // suppose this is technically bad coding style, but
    // it saves me a bit of typing.
    private static void output(string forOut)
    {
        Console.WriteLine(forOut);
 
    } //output
 
 
    // 'helpFib' is used to speed up the 'fib' method by preventing 
    // repeated calculations. In truth, I only ever briefly understood how
    // this works. I didn't come up with it, and I understood it just long 
    // enough to program it in the original Ada version of this program.
    private static BigInt helpFib(int n, int k, BigInt fibk, BigInt fibk1)
    {        
        if (n == k) 
        {
            return fibk;
        }
        else 
        {
            return (helpFib(n, k+1, fibk.add(fibk1), fibk));
        }//end if
 
    } //helpFib
 
 
    // The 'fib' method calculates the value of the Fibonacci number with
    // index 'n'.
    private static BigInt fib(int n)
    {
        BigInt one = new BigInt(1);
        BigInt zero = new BigInt(0);
 
        // For values less than 3, the Fib number is 1;
        if (n < 3) 
        {
            return one;         
        }
        // For Fibonacci indices smaller than 21, use a simple recursive 
        // Fib function as this seems to produce the most optimal 
        // performance.
        else if (n < 21) 
        {
            return (fib(n-2)).add(fib(n-1));
        }
        // For indices larger than 20, use the helpFib function to
        // speed things up.
        else
            return(helpFib(n, 1, one, zero));
        //end if
 
    } //fib
 
 
    // The verify method tests to see if the Fibonacci number calculated
    // is accurate by trying to find it by a different algorithm (which,
    // incidentally, uses the same algorithm as the 'main program' as it
    // were) and then comparing it to the originally found value.
    private static bool verify(int n)
    {
        BigInt test;
 
        if (n != 2) 
        {
            test = fib(n);
 
            // The 'add' method is required to add numbers represented 
            // using the 'BigInt' class.
            test = (test.add(test)).add(test);
 
            // The 'isEqual' method is required to compare numbers 
            // represented using the 'BigInt' class.
            if (test.isEqual((fib(n+2)).add(fib(n-2)))) 
            {
                return true;
            }
            else 
            {
                return false;
            }//end if
        }
        else 
        {
            return true;
        }//end if
 
    } //verify
 
 
    public static void Main(string[] args) 
    {     
        // Check that arguments were given at command line, if not display
        // help message.
        if (args.Length > 0)
        {
            int l, u;
 
            // Check to see if there were two arguements or one so that 
            // program displays appropriate behaviour.
            l = int.Parse(args[0]);
            if (args.Length < 2)
            {
                u = l;
            }
            else
            {        
                u = int.Parse(args[1]);
            }//end if
 
            // Check that numbers are in the correct range.
            if ((l < 1) || (u < 1))
            {
                output("Fibonacci Indices must be positive ", false);
                output("integers greater than zero");
            }
            else
            {
                // Check that Lower Limit is less than the Upper Limit and
                // swap if appropriate.
                if (l > u)
                {
                    int swap = u;
                    u = l;
                    l = swap;
                }//end if
 
                // Find, validate and output requested Fibonacci sequence.
                for (int i = l; i <= u; i++)
                {
                    output("\nFib("+i+") = ", false);
                    (fib(i)).writeBig();
                    //output(Convert.ToString(fib(i)), false);
 
                    if (verify(i)) 
                    {
                        output("  Valid", false);
                    }
                    else
                    {
                        output("  Invalid", false);
                    }//end if
                }//end loop
            }//end if
        }
        else
        {
            // Display help message if program is used without arguements.
            output("Hi there.");
            output("To use this program please type:\n");
            output("    java javafib i j\n");
            output("Where 'i' is an integer number corresponding");
            output("to the Fibonacci index you want to find the");
            output("Fibonacci numbers from, and 'j' is an integer");
            output("corresponding to the Fibonacci index you want");
            output("to find the Fibonacci numbers to.\n");
            output("If you only want to know the Fibonacci number");
            output("for one Fibonacci index, then enter:\n");
            output("    java javafib i\n");
            output("Where 'i' is an integer number corresponding");
            output("to the Fibonacci index you want to find the");
            output("Fibonacci number for.");
        }//end if
 
    } //Main
 
 
} //class FibCSharp

Example of Use

To use the program enter the low number you want the Fibonacci sequence to start from then the high number you want it to finish with at the command line (assuming you have in fact compiled the program source code).

Input:

fibcsharp 100 600

Output:

Fib(n) = fibnumber Valid OR Invalid
Fib(n + 1) = next_fibnumber Valid OR Invalid

Assumptions

None, but for large Fibonacci indices, the computer may crash from running out of memory. It is also assumed that you have the .NET framework installed (and a C# compiler). If not, you can probably find them at one of the sites below:
Microsoft's free version of Visual Studio
Microsoft's .NET framework
Mono - An open source implementation of .NET (includes a C# compiler)
DotGNU - Another open source implementation of .NET (includes a C# compiler)

Nexami Engeo 2007/07/05 19:05


Strict Standards: Only variables should be passed by reference in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/doku.php on line 79