Python functions that calculate first n terms of a given order of Fibonacci sequences

Question

I have written two functions that calculate the first n terms of a given order o of Fibonacci sequence, and return the result as a list of ints.

from en.Wikipedia

Extension to negative integers

Using \$F_{n−2} = F_n − F_{n−1}\$, one can extend the Fibonacci numbers to negative integers. So we get:

  … −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, …

and \$F_{-n} = (−1)^{n+1}F_n\$

Fibonacci numbers of higher order

A Fibonacci sequence of order \$n\$ is an integer sequence in which each sequence element is the sum of the previous \$n\$ elements (with the exception of the first \$n\$ elements in the sequence).
The usual Fibonacci numbers are a Fibonacci sequence of order \$2\$. The cases \$n = 3\$ and \$n = 4\$ have been thoroughly investigated. The number of compositions of nonnegative integers into parts that are at most \$n\$ is a Fibonacci sequence of order \$n\$. The sequence of the number of strings of \$0\$s and \$1\$s of length \$m\$ that contain at most \$n\$ consecutive 0s is also a Fibonacci sequence of order \$n\$.

Tribonacci numbers

The tribonacci numbers are like the Fibonacci numbers, but instead of starting with two predetermined terms, the sequence starts with three predetermined terms and each term afterwards is the sum of the preceding three terms. The first few tribonacci numbers are:

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … 

(sequence A000073 in the OEIS)

Tetranacci numbers

The tetranacci numbers start with four predetermined terms, each term afterwards being the sum of the preceding four terms. The first few tetranacci numbers are:

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, …

(sequence A000078 in the OEIS)

---

A random Fibonacci sequence can be defined by tossing a coin for each position \$n\$ of the sequence and taking \$F(n) = F(n−1) + F(n−2)\$ if it lands heads and \$F(n) = F(n−1) − F(n−2)\$ if it lands tails.
Work by Furstenberg and Kesten guarantees that this sequence almost surely grows exponentially at a constant rate: the constant is independent of the coin tosses and was computed in 1999 by Divakar Viswanath. It is now known as Viswanath's constant.

The two functions support extension to negative integers and random Fibonacci sequences, and take three parameters: o: int, n: int, r: int, o means order (of recursion), n means number of terms and r specifies whether you want the result randomized or not (default False).

o must be no less than 2. If you input 2 you get Fibonacci, 3 to get Tribonacci, 4 -> Tetranacci, 5 -> Pentanacci, and so on.
n must be greater than or equal to o (so that you can always tell the order of the sequence and the function never returns a list consisted solely of 0s),
r should be always an int (bool subclasses from int).

The following are the functions I want reviewed, I choose the iterative approach, their share the same logic, but I implemented one with a list-based approach, the other using variable swapping and variable unpacking:

import random

def h_nacci(o, n, r=False):
    if any(not isinstance(i, int) for i in (n, o, r)):
        raise TypeError('All parameters must be an integer')
    if o < 2 or abs(n) < o:
        raise ValueError('Order is less than 2 or number of terms is less than order')
    positive = True
    if n < 0:
        positive = False
        n = -n
    def worker(n):
        stack = [0] * (o-1) + [1]
        for i in range(n):
            yield stack[0] if positive else (-1)**(i%2+1)*stack[0]
            o_stack = stack
            stack = stack[1:]
            if r and random.randrange(2):
                stack.append(stack[-1] - sum(o_stack[:-1]))
                continue
            stack.append(sum(o_stack))
    series = list(worker(n))
    return series if positive else series[::-1]

def o_nacci(o, n, r=False):
    if any(not isinstance(i, int) for i in (n, o, r)):
        raise TypeError('All parameters must be an integer')
    if o < 2 or abs(n) < o:
        raise ValueError('Order is less than 2 or number of terms is less than order')
    positive = True
    if n < 0:
        positive = False
        n = -n
    def worker(n):
        x, *y, z = [0] * (o-1) + [1]
        for i in range(n):
            yield x if positive else (-1)**(i%2+1)*x
            if r and random.randrange(2):
                x, *y, z = *y, z, z - sum(y) - x
                continue
            x, *y, z = *y, z, x + sum(y) + z
    series = list(worker(n))
    return series if positive else series[::-1]

Sample output:

In [2]: h_nacci(2, 10)
Out[2]: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

In [3]: o_nacci(2, 10)
Out[3]: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

In [4]: h_nacci(3, 10)
Out[4]: [0, 0, 1, 1, 2, 4, 7, 13, 24, 44]

In [5]: o_nacci(3, 10)
Out[5]: [0, 0, 1, 1, 2, 4, 7, 13, 24, 44]

In [6]: h_nacci(3, -10)
Out[6]: [44, -24, 13, -7, 4, -2, 1, -1, 0, 0]

In [7]: o_nacci(3, -10)
Out[7]: [44, -24, 13, -7, 4, -2, 1, -1, 0, 0]

In [8]: h_nacci(2, 10, 1)
Out[8]: [0, 1, 1, 2, 3, 1, 4, 3, -1, 2]

Performance:

In [9]: %timeit o_nacci(2, 256)
149 µs ± 3.73 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [10]: %timeit h_nacci(2, 256)
123 µs ± 4.25 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [11]: %timeit h_nacci(2, -256)
220 µs ± 4.21 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [12]: %timeit o_nacci(2, -256)
256 µs ± 35.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [13]: %timeit o_nacci(2, 256, 1)
331 µs ± 40 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [14]: %timeit h_nacci(2, 256, 1)
305 µs ± 33.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [15]: %timeit h_nacci(3, 256)
133 µs ± 6.14 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [16]: %timeit o_nacci(3, 256)
169 µs ± 4.71 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

I want to know how to improve their performance, I have implemented every idea I can think of and yet they are still too slow...

Below are some functions posted for comparison only:

def fibonacci(n):  
    positive = True
    if n < 0:
        positive = False
        n = -n              
    def worker(n):         
        a, b = 0, 1
        for i in range(n):
            yield a if positive else (-1)**(i%2+1)*a
            a, b = b, a + b
    series = list(worker(n))
    return series if positive else series[::-1]

def tribonacci(n):
    positive = True
    if n < 0:
        positive = False
        n = -n
    def worker(n):
        a, b, c = 0, 0, 1
        for i in range(n):
            yield a if positive else (-1)**(i%2+1)*a
            a, b, c = b, c, a + b + c
    series = list(worker(n))
    return series if positive else series[::-1]

def random_fibonacci(n):
    def worker(n):
        a, b = 0, 1
        for i in range(n):
            yield a
            c = random.randrange(2)
            if c == 0:
                a, b = b, a + b
            else:
                a, b = b, b - a
    return list(worker(n))

In [18]: %timeit fibonacci(256)
33.2 µs ± 2.71 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [19]: %timeit fibonacci(-256)
130 µs ± 5.54 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [20]: %timeit tribonacci(256)
45.2 µs ± 5.26 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [21]: %timeit tribonacci(-256)
148 µs ± 4.27 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [22]: %timeit random_fibonacci(256)
210 µs ± 5.57 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

How can I implement the same idea more efficiently? How can the two big functions be optimized further?

Answer 1

I can't see much in terms of ways to improve this. A deque (from collections) is a little faster than a list for adding to both ends:

def deque_nacci(o, n, r=False):
    if any(not isinstance(i, int) for i in (n, o, r)):
        raise TypeError('All parameters must be an integer')
    if o < 2 or abs(n) < o:
        raise ValueError('Order is less than 2 or number of terms is less than order')
    positive = True
    if n < 0:
        positive = False
        n = -n
    def worker(n):
        stack = deque([0] * (o-1) + [1])
        for i in range(n):
            if r and random.randrange(2):
                last = stack.pop()
                new_last = last - sum(stack)
                stack.append(last)
                stack.append(new_last)
            else:
                stack.append(sum(stack))
            yield stack.popleft() if positive else (-1)**(i%2+1)*stack.popleft()

    series = list(worker(n))
    return series if positive else series[::-1]

That gives a slight improvement: