## Sunday, December 27, 2009

Here's a Java program that calculates the n'th Fibonacci number in hexadecimal format, where n could be infinitely long. For those who don't know, Fibonacci series is a series which is calculated by summing up the last two numbers of the series. It starts from 1, 1, 2, 3, 5, 8, 13, 21...

Large Fibonacci numbers are particularly useful to calculate the Golden Ratio, which can be calculated by using the ratio of the last 2 infinitely large terms of the Fibonacci series. The approximation of the ratio improves as you progress farther in the series. For more interesting mathematical properties read the Wikipedia entry for Golden Ratio.

In this program, the hex values are stored in string because of the restrictions posed by the conventional data types. The series is calculated by summing up the last 2 numbers of the series using carry and adding digit by digit. Eg. 8 & 13 can be added by adding 8+3 and have one in unit's place and carry 1 to the ten's place, then adding 1+1 = 2; thus, the answer 21.

`public class FibonacciNumber {    public static void main(String[] args) {        String h1 = "1";    // First Fibonacci Number        String h2 = "1";    // Second Fibonacci Number        String h3 = "";     // Next Fibonacci Number        String tempResult = "";        int i1=0, i2=0, i3;        Long ctr = new Long(0);        try {            // Loop till maximum value of Long            // Each run calculates the next number            while (ctr < Long.MAX_VALUE) {                i3 = 0;                h3 = "";                ctr++;                // This loop calculates the sum of the previous numbers digit by digit                for (int i = h1.length(), j = h2.length(); j > 0; i--, j--) {                    if (i > 0) {    // If a digit is left in i                        i1 = Integer.parseInt(h1.substring(i - 1, i), 16);                        i2 = Integer.parseInt(h2.substring(j - 1, j), 16);                        i3 += i1 + i2;                    } else if (h2.length() > h1.length()) {                    // When h1 is shorter than h2. Eg. h1=8 h2=11                         i2 = Integer.parseInt(h2.substring(j - 1, j), 16);                        i3 += i2;                    }                    tempResult = Integer.toHexString(i3);                    if (tempResult.length() == 2)   // Handling carry digit                    {                        i3 = Integer.parseInt(tempResult.substring(0,1), 16);                        h3 = tempResult.substring(1,2) + h3;                    }                    else    // No carry digit                    {                        i3 = 0;                        h3 = tempResult.substring(0,1) + h3;                    }                }                if (i3 != 0)                    h3 = tempResult.substring(0,1) + h3;                System.out.println(ctr + ": " + h3);                h1 = h2;                h2 = h3;            }        } catch (Exception ex) {            System.out.println(ex.toString());        }    }}`

The output of the program will look like:

`1: 22: 33: 5..244: 3144535de4cae86ae251b1971896d58bf961e6b9d48245: 4fb72becbf73267006f65a3aa504c57b1e9930e392d246: 80fb7f4aa43e0edae9480bd1bd9b9b0717fb179d675..846: bc35110da32840cce42425afddfe8fde936030e7fda1d532615324be2a410804acef43394c0b512d5e34a2f5e77fbe0e82d80580f4fb592de0232add6f7e6f34127e8eb43165d008fe5847: 130869a782cc70170bd47e47fb3034ecbbce810b2e7dce2a56c30baa1f3bc359eb13f26ed83e0f4357dbed6c374b79dfcf303e52c94a3996b1dfff19229baa1c0194727a75d25313cd62..Can go upto zillions of numbers.`