## 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
.
.
847: 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 ?