Java program to print Very Large Fibonacci numbers by simulating addition in software

FibonacciInteger.java

package com.yuktix.test.fib;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
 * The Java program to print Large Fibonacci numbers by simulating addition 
 * of 2 integers using stacks to keep individual digits. Trivial 
 * implementations using native INT type will overflow because even F(100) 
 * is 21 digits long!! 
 * 
 * This is the slowest possible implementation done just for fun to 
 * print F(n) beyond native INT limits on my machine. It takes about 400 ms
 * to print F(1000) on my laptop. 
 * 
 * 
 * @author Rajeev Jha ([email protected])
 * 
 * 
 */

public class FibonacciInteger {
	
	Stack<Integer> stack = new Stack<Integer>();
	
	// public methods 
	public FibonacciInteger(int value) {
		this.init(value);
	}
	
	public int getNumberOfDigits() {
		return this.stack.size();
	}
	
	public void show() {
		
		int size = this.stack.size() -1;
		for(int j = size; j >= 0; j--) {
			System.out.print(this.stack.get(j));
		}
		
		System.out.print("\r\n");
		
	}
	
	public static FibonacciInteger add(FibonacciInteger a, FibonacciInteger b) {
		
		FibonacciInteger result = new FibonacciInteger(0);
		// get LSB first representation 
		List<Integer> al = a.getLSBFirst();
		List<Integer> bl = b.getLSBFirst();
		
		int al_size = al.size();
		int bl_size = bl.size();
		
		int diff_size = 0;
		int loop_size = 0;
		
		// pad with zeros to make the lists 
		// the same size.
		if(al_size >= bl_size) {
			
			loop_size = al_size;
			diff_size = al_size - bl_size;
			for(int i=0; i < diff_size; i++) {
				bl.add(0);
			}
			
		} else {
			
			loop_size = bl_size;
			diff_size = bl_size - al_size;
			for(int i=0; i < diff_size; i++) {
				al.add(0);
			}
		}
		
		int column_sum = 0;
		int carry = 0;
		
		
		for(int i = 0; i < loop_size; i++) {
			
			column_sum = al.get(i) + bl.get(i) + carry;
			switch(column_sum) {
				case 0:
				case 1:
				case 2:
				case 3:
				case 4:
				case 5:
				case 6:
				case 7:
				case 8:
				case 9:
					carry = 0;
					break;
					
				case 10:
				case 11:
				case 12:
				case 13:
				case 14:
				case 15:
				case 16:
				case 17:
				case 18:
				case 19:
					carry = 1;
					column_sum = column_sum - 10;
					break;
				default:
					System.out.println(String.format("foo int column sum: %d", column_sum));
					throw new RuntimeException("foo int column add error");
					
				
			}
			
			result.addLSBDigit(column_sum);
			
		}
		
		if(carry > 0) {
			result.addLSBDigit(carry);
		}
		
		return result;
		
	}
	
	// private methods 
	// 
	private void init(int value) {
		
		// value is - MSB first
		while (value > 0) {
			stack.push(value % 10);
			value = value / 10;
		}
		
	}
	
	private List<Integer> getLSBFirst() {
		
		List<Integer> buffer = new ArrayList<Integer>();
		for(Integer x: stack) {
			buffer.add(x);
		}
		
		return buffer;
		
	}
	
	private void addLSBDigit(Integer digit) {
		
		// check that digit is 0-9 
		if((digit.intValue() > 9) || (digit.intValue() < 0)) {
			System.out.println(String.format("foo int lsb digit: %d", digit));
			throw new RuntimeException("foo int add LSB digit error");
		}
	
		this.stack.push(digit);
		
	}
	
	public static void main(String[] args) throws Exception {
		
		long t1 = System.currentTimeMillis();
		// initialize 
		FibonacciInteger f1 = new FibonacciInteger(1);
		FibonacciInteger f2 = new FibonacciInteger(1);
		
		f1.show();
		f2.show();
		
		FibonacciInteger sum = new FibonacciInteger(0);
		
		for(int i = 0 ; i < 998; i++) {
			sum = FibonacciInteger.add(f1, f2);
			sum.show();
			
			f1 = f2;
			f2 = sum;
		}
		
		long t2 = System.currentTimeMillis();
		System.out.println("number of digits: " + sum.getNumberOfDigits());
		System.out.println("time spent: " + (t2-t1));
		
	}
	
}