answer3.md

the nextFibonacci(fList) takes an array of fibonacci numbers, and tell you all the next fibonacci numbers
Insde it, we use a helper function nextF(f) that find the next fibonacci number of a fibonacci number f

Implementations are written in Python

Code1:Implementation of nextFibonacci(fList)

def nextFibonacci(fList):
"""
a function that takes an array of integers as input. For each integer, output the next fibonacci number.
"""
    try:
        for i in range(len(fList)):
            print(nextF(fList[i]))
    except Exception as err:
        print(str(err))

Code2:Implementation of nextF(f) using dynamic programming

def nextF(f):
"""
a function that finds the next fibonacci number of a integer.
"""
    f1,f2=1,1
    while True:
        f1,f2 = f2,f1+f2
        if(f==f1):return f2
        if(f<f1):
            raise Exception("Not a Fibonacci number")
            break

Space complexity is O(1).
Time complexity is O(n).

Some thoughts and researchs on Faster Methods:

Another way is to use [[1,1],[1,0]]^n=[[F_n+1, F_n], [F_n, F_n-1]]
and calculate the matrix eponentiation by Exponentiation by squaring

Code3:Implementation of nextF(f) using matrix eponentiation

def mat_mul(m1,m2):
    """
    A function to compute the product
    of two 2x2 matrices m1 and m2.
    """
    m=[[0,0],[0,0]]
    m[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]
    m[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]
    m[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]
    m[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]
    return m

def mat_pow(F,n):
    """
    compute F^n of a 2x2 matrix iteratively using binary exponentiation

    since the input n is represented in binary expression
    and looping run through bits in the binary representation of n,
    the number of times of iteration is logn,
    so, the time complexity become O(logn)
    """
    r=[[1,0],[0,1]] #identity
    if n==0:return r
    elif n==1:return F
    else:
        n_bits=bin(n)[2:]#since 0b will be added in front of a binary number in python, we need to slice the list to begain with the 3rd element
        for b in n_bits:
            r=mat_mul(r,r)
            if b=='1':
                r=mat_mul(r,F)
        return r
F=[[1,2],[3,4]]
print(mat_pow(F,5))

def nextF(f):
    """
    a function that find the next fibonacci number of a known fibonacci number f using the matrix formula
    [[1,1],[1,0]]^n=[[Fn+1, Fn], [Fn, Fn-1]]
    """
    F=[[1, 1],
       [1, 0]]
    n,product=1,1
    while (f!=F[0][1]):
        
        print(n)
        print
        F=mat_pow(F,n)
        print(F)
        if(f<F[0][1]):
            raise Exception("Not a Fibonacci number")
            break
        n+=1
    return F[0][0]
#unit testing
print(nextF(2))

The above algorithm is not correct!!!!
After some thoughts on the question, it is not the same as finding a fibonacci number with the index n given.
Normally, faster algorithm for finding a Fibonacci number Fn with n given, can be designed with the help of some formula like the matrix formula above and fast doubling, the matrix exponentiation algorithm with the redundant calculations removed.
Remark: Repeated squaring and fast doubling can reduces time from linear to logarithmic.
Because of the help of those formulas, we don't need to find all fibonacci numbers {Fn} with n less than some N. But to find the next Fibonacci number, I have to compare all the Fibonacci numbers in series{Fn} one by one until I find it,
so that I can tell the next one.
As I realize this situation, I tend to think of finding the index of a given fibonacci numbers, and hence find the next one by fib(n), so I turn to the closed form formula.
However, the closed form formula have a square root of 5, and inverting it also need logarithm operation which also produce floating point number, that will give rise to precision error in finding the index n. Also, the underlying logarithm algorthm maybe time comsuming for large fibonacci number. How to find a binary logarithm very fast? (O(1) at best) So in practice, my first program maybe good enough in general.
For further impovment, I am thinking of using some kind of mathematical facts from number theorey about fibonacci numbers to calculate the exact index n (See reference 3).

The above programs have a probelm that while nextFibonacci() call multiple nextF(), nextF wasted a lot of computation resources in re-computing Fib seq if the fList is long and overlaps.
To solve this, we can compare all the Fibs in fList to the Fib seq at once, when the next Fib of a Fib in fList is found, we don't need to compare it again, and we can pop it out from the fList. And the program generates the Fib seq once only.

Code4:A revised version that combine the function nextFibonacci(fList) and nextF(f)

def nextFibonacci(fList):
    f1,f2=1,1
    nextfList=[None for i in range(len(fList))]
    fDict=dict(enumerate(fList))#creating a dictionary from list with indices as keys
    while len(fDict) != 0:#while fDist is not empty
        f1,f2 = f2,f1+f2
        #print("fDict={0}, nextfList={1}".format(fDict,nextfList))
        for i in list(fDict):
            #print("i={0}, fDict={1}, nextfList={2}".format(i,fDict,nextfList))
            if fDict[i]<f1:
                nextfList[i]="Not a Fibonacci number"
                del fDict[i]
            elif fDict[i]==f1:
                nextfList[i]=f2
                del fDict[i]
    for item in nextfList:print(item)
nextFibonacci([1,21,8])
nextFibonacci([1,22,9])

The revised version should be faster.

Reference:

An interesting article:

Machine learning vs Researching brains: the Fibonacci example

martin-mok/answer3.md