Most ordinary-scale programs don’t use very large numbers, but today I’ll show you how to use Java to do some more serious calculating, with the Fibonacci numbers as an example:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …
The numbers in this sequence always get larger, so you don’t need to be a software engineer to see that int and long wont be big enough. Just to highlight the problem, here is a naive approach to listing the Fibonacci numbers:
class FibonacciLong {
static long solutions = 0;
public static void main(String[] args) {
long num1 = 0;
long num2 = 1;
long tmp;
solution(num1);
solution(num2);
while(true) {
tmp = num1 + num2;
solution(tmp);
num1 = num2;
num2 = tmp;
}
}
static void solution(long number) {
solutions++;
System.out.println(solutions + "t" + number);
}
}The output of this program overflows after the 93rd term. Java only uses signed integer types, so we end up with a negative number:
1 0
2 1
3 1
4 2
5 3
6 5
....
92 4660046610375530309
93 7540113804746346429
94 -6246583658587674878
To find larger values, we can use the BigInteger class, under java.math. They are constructed like this:
BigInteger num1 = new BigInteger("0");They don’t really work like the primitive types. They are manipulated with methods like .add() and .subtract(), rather than the operators that we are accustomed to: + - * / %.
The below code has been written with BigInteger instead of long. It will return the nth term of the Fibonacci sequence, or enumerate solutions until the cows come home.
import java.math.BigInteger;
class FibonacciBigInteger {
static long solutions = 0;
static long find = 0;
public static void main(String[] args) {
if(args.length >= 1) {
find = Long.parseLong(args[0]);
}
BigInteger num1 = new BigInteger("0");
BigInteger num2 = new BigInteger("1");
BigInteger tmp;
solution(num1);
solution(num2);
while(true) {
tmp = num1.add(num2);
solution(tmp);
num1 = num2;
num2 = tmp;
}
}
static void solution(BigInteger number) {
solutions++;
if(find == 0 || solutions == find) {
System.out.println(number.toString());
if(find != 0) { System.exit(0); }
}
}
}The good news is that this program is now capable of working with numbers too large to say aloud. So today is a good day to start using Unix’s wc program to appreciate how big these numbers actually are:
mike~$ java FibonacciBigInteger 420000 | wc -m
87776Subtract one character because there is an end-of-line in the output— and this means that the 420,000th Fibonacci number is 8775 digits long. We have discovered a new fact!
Note: There is still one variable in the program above that will overflow eventually, so you should also convert that to a BigInteger if you are hoping to calculate past about the nine quintillionth Fibonacci number (which you would be crazy to do with this method).