## 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.`

Kevin Rodrigues said...

That is a cool program to calculate the fibonacci series for large numbers.

Was wondering if the same can be done for the factorial of numbers as that series expands exponentially.

Gurpreet Singh Modi said...

Yes, it can be done for factorial numbers too. You will need to multiply all the first number with all the digits of the second number and then add them. This will require 2 for loops, the outer loop will maintain the sum and the inner loop (similar to the current for loop) will compute the multiplications digit by digit.

Anonymous said...

Hiii, Gurpreet

me and some of my frnds hv started an E-magazine called Reader's Quotient it is totally for a noble cause, I came across ur blog in my quest to search excellent writers and felt worth inquire if u shall be willing to come along us ?