JavaScript function that generates Fibonacci like sequences of given order

Question

Generalizations of Fibonacci numbers

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)

---

The function is simple, you give it two arguments, the first argument is an array of numbers, the second argument is the number of terms.

The length of the array is the order of the generated sequence, the elements of the array are the first order terms of the generated sequence, the function uses iterative approach and generates the required sequence.

Examples:

> console.log(fiblike([0, 1], 16))
[
    0,   1,   1,   2,  3,  5,
    8,  13,  21,  34, 55, 89,
  144, 233, 377, 610
]
undefined
> console.log(fiblike([0, 0, 1], 16))
[
     0,   0,   1,   1,   2,
     4,   7,  13,  24,  44,
    81, 149, 274, 504, 927,
  1705
]
undefined
> console.log(fiblike([0, 0, 0, 1], 16))
[
     0,   0,   0,   1,   1,
     2,   4,   8,  15,  29,
    56, 108, 208, 401, 773,
  1490
]
undefined
> console.log(fiblike([1, 2, 3], 16))
[
     1,   2,    3,    6,   11,
    20,  37,   68,  125,  230,
   423, 778, 1431, 2632, 4841,
  8904
]
undefined
> console.log(fiblike([9, 21, 1986], 16))
[
        9,      21,    1986,
     2016,    4023,    8025,
    14064,   26112,   48201,
    88377,  162690,  299268,
   550335, 1012293, 1861896,
  3424524
]
undefined
>

---

Code

function fiblike (array, terms) {
    if (isNaN(terms) || !(array instanceof Array)) {
        throw 'Arguments have incorrect types'
    }
    if (array.some(isNaN)) {
        throw 'Array should only contain numbers'
    }
    var result = []
    for (let i=0; i<terms; i++) {
        array.push(array.reduce((s, n) => s + n, 0))
        let first = array.shift()
        result.push(first)
    }
    return result
}

console.log(fiblike([0, 1], 16))
console.log(fiblike([0, 0, 1], 16))
console.log(fiblike([0, 0, 0, 1], 16))
console.log(fiblike([1, 2, 3], 16))
console.log(fiblike([9, 21, 1986], 16))

The last example is the birth date of my favorite Youtuber and I am not gonna tell you her name

So how is the code? How can it be improved?

P.S. I really don't know why 1 instanceof Number fails.

Answer 1

Your algorithm for an n element Fibbonacci series order k is O(N*K) Your JavaScript implementation may be inefficient. I revised your algorithm to become O(N). I revised your JavaScript implementation to become more efficient. I used JSBench.me to compare the original and the revised versions.

---

Original version:

function fiblike (array, terms) {
    if (isNaN(terms) || !(array instanceof Array)) {
        throw 'Arguments have incorrect types'
    }
    if (array.some(isNaN)) {
        throw 'Array should only contain numbers'
    }
    var result = []
    for (let i=0; i<terms; i++) {
        array.push(array.reduce((s, n) => s + n, 0))
        let first = array.shift()
        result.push(first)
    }
    return result
}

---

Revised version:

function fiblike(a, n) {
    const aLen = a.length;
    if (aLen === 0 || aLen >= n) {
        return a;
    }
    const like = new Array(n);
    const likeLen = like.length;
    like[aLen] = 0;
    for (let i = 0; i < aLen; i++) {
        let ai = a[i];
        like[i] = ai;
        like[aLen] += ai;
    }
    for (let i = aLen + 1; i < likeLen; i++) {
        like[i] = 2*like[i-1] - like[i-aLen-1];
    }
    return like;
}

---

Examples:

console.log(fiblike([0, 1], 16));
console.log(fiblike([0, 0, 1], 16));
console.log(fiblike([0, 0, 0, 1], 16));
console.log(fiblike([1, 2, 3], 16));
console.log(fiblike([9, 21, 1986], 16));

---

This benchmark uses your examples.

// benchmark
fiblike([0, 1], 16);
fiblike([0, 0, 1], 16);
fiblike([0, 0, 0, 1], 16);
fiblike([1, 2, 3], 16);
fiblike([9, 21, 1986], 16);

The original version is about 89% slower than the revised version. The revised version is about 9 times faster than the original version.

---

These benchmarks measure the effect of increasing the Fibbonacci series order k.

For the original version, each element is the sum of k values, O(K) or linear time. For the revised version, each element is the sum of 3 values, O(1) or constant time.

// benchmark setup - k = 2
let a = new Array(2);
a[a.length - 1] = 1;

// benchmark
fiblike(a, a.length+100);

For k = 2, the original version is about 94% slower than the revised version. The revised version is about 16 times faster than the original version.

// benchmark setup - k = 10
let a = new Array(10);
a[a.length - 1] = 1;

// benchmark
fiblike(a, a.length+100);

For k = 10, the original version is about 97% slower than the revised version. The revised version is about 33 times faster than the original version.

---

Algorithm:

For an element a(n) of a Fibbonacci series order k,

a(n) = a(n-1) + ... + a(n-k)

and

a(n+1) = a(n) + a(n-1) + ... + a(n-(k+1))

Substituting for a(n) and simplifying,

a(n+1) = [a(n-1) + ... + a(n-k)] + [a(n-1) + ... + a(n-(k+1))]

       = a(n) + a(n) - a(n-k-1)

The time complexity for an element is constant or O(1).

For the n element Fibbonacci series order k the time complexity is linear or O(N).