The Fibonacci sequence number of “1 000 000”?

Most of the people know or at least have heard about the Fibonacci sequence numbers. To be short – Fibonacci sequence numbers is a sum of the previous both numbers.
For example, the 1st and 2nd numbers are 1 and 1.
So, the 3rd = 2.
And 4th = 2 + 1 = 3.
And 5th = 3 + 2 = 5.
And 6th = 5 + 3 = 8, and so on.
So as the result, we have 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ….. Here we can see that the Fibonacci sequence number on the position 10 is equal to 55.
So, how to calculate the Fibonacci sequence number on the position 1 000 000 (1 Million)? Try to find such online service and You will not because the process of calculation is not so easy. The thing is that we cannot represent such long character in any of existing number format (Long, Double, BigInt) whatever. The length of Fibonacci sequence number on the position 1 000 000 is 208 988 digits. it means that if we want to write this number on the wall and the size of 1 digit is 5mm – the wall should be ~ 5.5 square meters.

How to perform the calculation like this one?
The algorithm should be as much optimised as it’s possible. It means that it is impossible to store all the previous values in the array because the size of the array will be extremely huge and it will be impossible to keep the array in memory. The array should self-reducible after adding the new sum of the previous numbers. In this case. Even in the end, the array will be no bigger than ~ 600Kb.

The method of summing two numbers is very simple:
1234
+
_888
——-
2122

But the complexity is growing proportionally to the increasing of number’s size.

If you would like to see the Fibonacci sequence number of 1 million, here it is:

The first 20 numbers: 19532821287077577316  …
The last 20 numbers:  …  68996526838242546875

Now, let’s see the Java solution.

public String getFibonaciDynamic(int arrLength) {
    long startTime = System.currentTimeMillis();
    LinkedList<String> arr = new LinkedList<>();
    arr.add(0, "1"); // Adding the numbers on the 1st and 2nd position
    arr.add(1, "1");

    int i = 0;
    while (i <= arrLength - 3) {
        arr.add(2, bigSum(arr.get(0), arr.get(1)));
        arr.remove(0);
        i++;
        if (i % 10000 == 0) {
            long endTime = System.currentTimeMillis();
            String s1 = "Calculated sequenced number of: " + i + " in " + (endTime - startTime) / 1000 + " sec"; // All the System.out.prinln are needed for watching the progress
            System.out.println(s1);
            String s2 = "Previous number is: " + arr.getFirst();
            System.out.println(s2);
            String s3 = "Last number is: " + arr.getLast();
            System.out.println(s3);
            Utils.writeUsingFileWriter(s1 + "\n" + s2 + "\n" + s3, "fib_" + i);
            System.out.println();
        }
    }

    long endTime = System.currentTimeMillis();
    System.out.println("Fibonacci sequence with length " + arrLength + " took " + (endTime - startTime) / 1000 + " sec");
    return arr.getLast();
}

And calculating of big sum:

public String bigSum(String s1, String s2) {
    int lengthS1 = s1.length();
    int lengthS2 = s2.length();

    int diff = Math.abs(lengthS1 - lengthS2);

    String prefix = repeatString("0", diff);


    if (lengthS1 < lengthS2) {
        s1 = prefix + s1;
    } else if (lengthS2 < lengthS1) {
        s2 = prefix + s2;
    }

    StringBuilder out = new StringBuilder();
    int buf = 0;
    for (int i = s1.length() - 1; i >= 0; i--) {
        int n1 = Integer.parseInt(String.valueOf(s1.charAt(i)));
        int n2 = Integer.parseInt(String.valueOf(s2.charAt(i)));

        int sum = buf + n1 + n2;
        buf = 0;
        if (sum >= 10) {
            sum = sum % 10;
            buf++;
        } else {
            buf = 0;
        }

        if (buf > 0 && i == 0) {
            out.insert(0, "1").insert(1, sum);
        } else {
            out.insert(0, sum);
        }
    }


    return out.toString();
}

I hope this article could inspire the people to start loving a math and numbers 🙂

Enjoy my blog!