Ne generalized Fibonacci number in O (log N)

In the course work, it was required to write an algorithm with logarithmic complexity, which will find the Nth number from the Fibonacci sequence.

Algorithm

Found several articles on this topic, all of them dealt with the classic series of Fibonacci numbers. For him, you can apply this formula:

But in my work, generalized series were used, in which the first two numbers are zero and some parameter. After hours of searching, I came across an interesting commentary in which the author gives a formula for the cyclic finding of any linear recurrent sequences (including a series of Fibonacci numbers).

Here Q is a 2x2 matrix whose elements can be easily calculated.

Substituting any several Fibonacci numbers, we find out that the matrix Q = [[0,1], [1,1]].

The final formula of the matrix, which contains the N-th number of the generalized Fibonacci series, can be written as follows:

Fn - the desired Fibonacci number,

C - key,

n - ordinal number

Obviously, for the efficiency of the entire algorithm, it is necessary to use the fastest algorithm to raise the matrix Q to the power n.This article helped me to cope with this. It explains that to raise a matrix to the power of n, you can split n into powers of two and then raise the matrices only to these powers. This approach gives the complexity O (log N).

Then it remains only to multiply by the matrix [[C, C], [C, 0]] and get the element with the index [0,1].

Python implementation

class FiboMatrix:
    key = 0
    matrix_cur = [[0,0], [0,0]]
    matrix_one = [[0,1], [1,1]]

    def __init__(self, key):
        self.key = key
        self.matrix_cur = [[key, key], [key, 0]]
        self.PowsBuffer = {}
        #       

    def MultiplyMatrix(self, M1, M2):
        """ 
          2x2   ."""

        a11 = M1[0][0] * M2[0][0] + M1[0][1] * M2[1][0]
        a12 = M1[0][0] * M2[0][1] + M1[0][1] * M2[1][1]
        a21 = M1[1][0] * M2[0][0] + M1[1][1] * M2[1][0]
        a22 = M1[1][0] * M2[0][1] + M1[1][1] * M2[1][1]
        return [[a11, a12], [a21, a22]]

    def PowMatrix(self, M: list, p: int):
        """   .
          2x2     .
        """

        if p == 1:
            return M
        if p in self.PowsBuffer:
            return self.PowsBuffer[p]

        K = self.PowMatrix(M, int(p / 2))
        R = self.MultiplyMatrix(K, K)
        self.PowsBuffer[p] = R
        return R

    def GetNum(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        #      n   
        powers = []
        p = 0
        for digit in reversed(bin(n)[2:]):
            if digit == '1':
                powers.append(int(pow(2, p)))
            p += 1

        matrices = [self.PowMatrix(FiboMatrix.matrix_one, p)
                    for p in powers]

        #     

        while len(matrices) > 1:
            M1 = matrices.pop()
            M2 = matrices.pop()
            R = self.MultiplyMatrix(M1, M2)
            #   
            matrices.append(R)

        self.matrix_cur = self.MultiplyMatrix(self.matrix_cur, matrices[0])
        #    F1  F2  ,    
        return self.matrix_cur[0][1]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

To compare the efficiency, the simplest analogue of this algorithm was written using a loop:

def Fib(num, key):
    fib_1 = 0
    fib_2 = key

    for dec in range(num):
        fib_1, fib_2 = fib_2, fib_1+fib_2

    return fib_2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Benchmarks confirm our expectations: the classical algorithm takes several times more time already at the 10,000th number.