Fibonacci Generator (javafib)

A fairly acute Fibonacci sequence generator written in the Java programming language. I wrote this in the Christmas period of 2004 to get some practice in Java for University. As with my 'C' version of this program, this is really just a conversion of the Ada version I had done in second year Computing Science.

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

To see the algorithm at work, I've knocked up a quick java applet of it below (note, the actual version has no graphical user interface, and it can also do a 'from' and 'to', but I just knocked it up quickly so you could get the idea.):

Silly rabbit, get a java enabled browser...

If you would like a copy of the applet code, you can find it here. If the applet doesn't work, get a java enabled browser and the appropriate java runtime plug in. I have also been led to believe that you need at least the 1.5.0 java runtime plug-in or the applet will not display properly. You may find these two links useful to help you with that:

http://java.sun.com
http://www.getfirefox.com

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

javafib.java:

/*--------------------------------------------------------------------------
----------------------------------------------------------------------------
--                                                                        --
--     Program Title : JavaFib Version 0.9                                --
--     Author : nex                                                       --
--     Date Last Modified : 22nd December 2004                            --
--                                                                        --
--     Description : This program takes in two integers from standard     --
--                   input and uses them as indices to calculate          --
--                   Fibonacci numbecrs 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.                                            --
--                                                                        --
----------------------------------------------------------------------------
--------------------------------------------------------------------------*/
 
// The BigInt class deals with large interger representation.
class BigInt implements Cloneable {
 
 
 
    // The BigIntList is a private class of BigInt.
    private class BigIntList {    
	int val;
	BigIntList next;
	BigIntList prev;
 
	// Constructor
	BigIntList(int v) {
	    val = v;
	}
    } //class BigIntList
 
 
 
    BigIntList head;
    BigIntList tail;
 
    // Constructors
    BigInt(int v) {
	head = new BigIntList(v);
	tail = head;
    }
 
    BigInt() {
	head = null;
	tail = null;
    }
    // end Constructors
 
 
    // Calculates x + y (both of type 'BigInt') and returns as type 'BigInt'.
    // This method is specifically designed for the BigInt type of this
    // program.
    BigInt add(BigInt y) throws CloneNotSupportedException {
	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.
    boolean isEqual(BigInt y) throws CloneNotSupportedException {
	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.
    void writeBig() throws CloneNotSupportedException {
	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) {
			System.out.print("00");
		    }
		    else {
			System.out.print("0");
		    }//end if
		}//end if
	    }//end if
 
	    // Output current node value then recursively call other node
	    // values for output.
	    System.out.print(this.tail.val);
	    xTemp.tail = this.tail.prev;
	    xTemp.writeBig();
 
	}//end if
 
    } //writeBig
 
 
} //class Big
 
 
 
class javafib {
 
    // '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) 
                throws CloneNotSupportedException {
 
	if (n == k) {
	    return fibk;
	}
	else {
	    return (helpFib(n, k+1, fibk.add(fibk1), fibk));
	}
 
    } //helpFib
 
 
    // The 'fib' method calculates the value of the Fibonacci number with
    // index 'n'.
    private static BigInt fib(int n) throws CloneNotSupportedException {
	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 boolean verify(int n) throws CloneNotSupportedException {
 
	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[]) throws CloneNotSupportedException {
 
	// 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 = Integer.parseInt(args[0]);
	    if (args.length < 2) {
		u = l;
	    }
	    else {	    
		u = Integer.parseInt(args[1]);
	    }//end if
 
	    // Check that numbers are in the correct range.
	    if ((l < 1) || (u < 1)) {
		System.out.println("Fibonacci Indices must be positive 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++) {
		    System.out.print("\nFib("+i+") = ");
		    (fib(i)).writeBig();
 
		    if (verify(i)) {
			System.out.print("  Valid");
		    }
		    else {
			System.out.print("  Invalid");
		    }//end if
		}//end loop
	    }//end if
	}//end if
 
	// Display help message if program is used without arguements.
	else {
	    System.out.println("Hi there.");
	    System.out.println("To use this program please type:\n");
	    System.out.println("    java javafib i j\n");
	    System.out.println("Where 'i' is an integer number corresponding");
	    System.out.println("to the Fibonacci index you want to find the");
	    System.out.println("Fibonacci numbers from, and 'j' is an integer");
	    System.out.println("corresponding to the Fibonacci index you want");
            System.out.println("to find the Fibonacci numbers to.\n");
	    System.out.println("If you only want to know the Fibonacci number");
            System.out.println("for one Fibonacci index, then enter:\n");
	    System.out.println("    java javafib i\n");
	    System.out.println("Where 'i' is an integer number corresponding");
	    System.out.println("to the Fibonacci index you want to find the");
            System.out.println("Fibonacci number for.");
	}//end if
 
    } //main
 
 
} //class javafib

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:

java javafib 100 600

Output:

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

None, but for large Fibonacci indices, the computer may crash from running out of memory. It is also assumed that you have a java runtime environment (and a java compiler). If not, you can probably find one here.

— Nexami Engeo 2007/07/06 10:17