2
\$\begingroup\$

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?

\$\endgroup\$
5
  • 1
    \$\begingroup\$ By the way, a series extending to the left shouldn't have randomized signs, the negative n and truthy r were supposed to be exclusive to each other, I could just add some checks and throw an exception if they appear at the same call, but decided against editting the code. \$\endgroup\$ Feb 19 at 14:24
  • 1
    \$\begingroup\$ How do you use the results, what is the acid test telling fast enough from still too slow? (microbench source code welcome…) What about higher orders - 9, 42, 1984? \$\endgroup\$
    – greybeard
    Feb 20 at 11:47
  • 1
    \$\begingroup\$ @greybeard I use these functions in my super hacky and convoluted script to encode plain text and I need them to be fast, beyond this I can't divulge any more information. \$\endgroup\$ Feb 20 at 11:56
  • 1
    \$\begingroup\$ Rosetta stone: Python generator & anamorphic \$\endgroup\$
    – greybeard
    Feb 21 at 8:24
  • \$\begingroup\$ Generally, with non-compiled environments (did you give PyPy&Cython a spin?), move conditional execution as far out as you can. (FWIW, my best unrolled stabs at 2&3-term Fibonacci-like were just 5&3 time faster than h_nacci.) \$\endgroup\$
    – greybeard
    Apr 19 at 8:30

1 Answer 1

2
\$\begingroup\$

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:

benchmarks

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Not much improvement in performance, still improvement nonetheless. \$\endgroup\$ Feb 20 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.