How to find the first k digit a fibonacci number without generating the whole number?

Question

I have to find the first k digit for all Fibonacci number up to fibonacci sequence 2*10^6.

It is clear that we can not store the value of the fibonacci number in any variable. Even calculating all the fibonacci number itself take huge computational time. So, is there any way just to get the first k digit of fibonacci number without generating the whole number?

Answer 1

Since you only need the leading digits, an approximation to the Fibonacci number is sufficient. Thus, you can use the closed-form formula for the nth Fibonacci number, which is

F_n = (φⁿ − (−φ)⁻ⁿ) / √5, where φ = (1 + √5) / 2 ≈ 1.6180339887

... then round to the desired precision.

Answer 2

Here's an approach which does not generate all numbers. When it comes to finding Fibonacci numbers fast there is a O(k log n) procedure where O(k) is the time it takes to multiply F(n) with F(n-1). It exploits the fact that F(n) is exactly the a[0][1] element of the matrix a which is the n-th power of the simple matrix [[1, 1], [1, 0]] (reference). So you can use exponentiation by squaring. Here is a sample python implementation:

def matrix_mult(a, b):
    return ((a[0][0]*b[0][0] + a[0][1]*b[1][0], 
             a[0][0]*b[0][1] + a[0][1]*b[1][1]),
            (a[1][0]*b[0][0] + a[1][1]*b[1][0], 
             a[1][0]*b[0][1] + a[1][1]*b[1][1]))


def matrix_pow(a, k):
    if k == 0:
        return ((1, 0), (0, 1))
    t = matrix_pow(a, k//2)
    t2 = matrix_mult(t, t)
    if k % 2 == 0:
        return t2
    return matrix_mult(t2, a)


def fib(n):
    a = ((1, 1), (1, 0))
    return matrix_pow(a, n)[0][1]


def get_first_k(n, k):
    return str(fib(n))[:k]

for n in range(10 ** 2, 10 ** 2 + 10):
    print(get_first_k(n, 3))

#output
#first 3 digits   actual number
354               #354224848179261915075
573               #573147844013817084101
927               #927372692193078999176
150               #1500520536206896083277
242               #2427893228399975082453
392               #3928413764606871165730
635               #6356306993006846248183
102               #10284720757613717413913
166               #16641027750620563662096
269               #26925748508234281076009

For n = 2 * 10 ** 5 it takes around 5s to calculate F_n which is reasonable given the nature of the problem.

Here's Java alternative

package stackoverflow;

import java.math.BigInteger;

public class Fibonacci {

    public static class Matrix {
        BigInteger[][] a;

        public Matrix(BigInteger n0, BigInteger n1, BigInteger n2, BigInteger n3) {
            a = new BigInteger[][]{{n0, n1}, {n2, n3}};
        }

        public BigInteger get(int i, int j) {
            return a[i][j];
        }

        @Override
        public String toString() {
            return String.format("%s %s\n%s %s", a[0][0], a[0][1], a[1][0], a[1][1]);
        }
    }

    Matrix matrixMult(Matrix a, Matrix b) {
        return new Matrix(a.get(0, 0).multiply(b.get(0, 0)).add(a.get(0, 1).multiply(b.get(1, 0))),
                          a.get(0, 0).multiply(b.get(0, 1)).add(a.get(0, 1).multiply(b.get(1, 1))),
                          a.get(1, 0).multiply(b.get(0, 0)).add(a.get(1, 1).multiply(b.get(1, 0))),
                          a.get(1, 0).multiply(b.get(0, 1)).add(a.get(1, 1).multiply(b.get(1, 1))));
    }

    Matrix power(Matrix a, int k) {
        if (k == 0)
            return new Matrix(new BigInteger("1"), new BigInteger("0"),
                              new BigInteger("0"), new BigInteger("1"));
        Matrix t = power(a, k / 2);
        Matrix t2 = matrixMult(t, t);
        if (k % 2 == 0)
            return t2;
        return matrixMult(t2, a);
    }

    BigInteger get(int n) {
        Matrix a = new Matrix(new BigInteger("1"), new BigInteger("1"),
                              new BigInteger("1"), new BigInteger("0"));
        return power(a, n).get(0, 1);
    }

    String getFirstK(int n, int k) {
        return get(n).toString().substring(0, k);
    }

    public static void main(String[] args) {
        Fibonacci f = new Fibonacci();

        System.out.println(f.getFirstK(200000, 10));
    }
}