Program to Compute Large Fibonacci Numbers in Hex

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: 2
2: 3
3: 5
.
.
244: 3144535de4cae86ae251b1971896d58bf961e6b9d48
245: 4fb72becbf73267006f65a3aa504c57b1e9930e392d
246: 80fb7f4aa43e0edae9480bd1bd9b9b0717fb179d675
.
.
846: bc35110da32840cce42425afddfe8fde936030e7fda1d532615324be2a410804acef43394c0b512d5e34a2f5e77fbe0e82d80580f4fb592de0232add6f7e6f34127e8eb43165d008fe5
847: 130869a782cc70170bd47e47fb3034ecbbce810b2e7dce2a56c30baa1f3bc359eb13f26ed83e0f4357dbed6c374b79dfcf303e52c94a3996b1dfff19229baa1c0194727a75d25313cd62
.
.
Can go upto zillions of numbers.