# Fastest Fibonacci sequence generator

**URL:** <https://forum.kx.com/t/fastest-fibonacci-sequence-generator/13751>\
**Category:** Community Support\
**Tags:** imported, kdb-and-q\
**Created:** [February 12, 2024, 12:00am UTC](https://forum.kx.com/t/fastest-fibonacci-sequence-generator/13751 "2024-02-12T00:00:00Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![albin](https://avatars.discourse-cdn.com/v4/letter/a/6de8d8/32.png) [@albin](https://forum.kx.com/u/albin)\
**Post date:** [February 12, 2024, 12:00am UTC](https://forum.kx.com/t/fastest-fibonacci-sequence-generator/13751/1 "2024-02-12T00:00:00Z")

</div>

[https://learninghub.kx.com/forums/topic/fastest-fibonacci-sequence-generator](https://learninghub.kx.com/forums/topic/fastest-fibonacci-sequence-generator)

Hello,

I’ve been playing around with generating Fibonacci sequences with the goal of learning how to write performant q code.

First, the solution given in the docs, while elegant, is hardly performant:

&nbsp;

```
fib:{x,sum -2#x} 
ts 1000 fib/0 1 / 0 16768 
ts 10000 fib/0 1 / 7 262528 
ts 100000 fib/0 1 / 875 2097536 
ts 1000000 fib/0 1 / 226615 16777600
```

&nbsp;

In particular, there are many unnecessary allocations.

At the expense of some elegance (and pre-calculating the output list), we can speed things up significantly:

&nbsp;

```
zeros: {[t; n] n#t$0} 
fibn:{[s; n] @[s; 0 1; :; 0 1]; f: {[s; i]; @[s; i; :; @[s; i-2] + @[s; i-1]]; i+1}; (f[s]/)[n-2; 2]; s} 
x: zeros[`long; 1000] 
ts fibn[`x; 1000] / 0 928 
x: zeros[`long; 10000] 
ts fibn[`x; 10000] / 3 928 
x: zeros[`long; 100000] 
ts fibn[`x; 100000] / 30 928 
x: zeros[`long; 1000000] 
ts fibn[`x; 1000000] / 307 928
```

&nbsp;

Now, my question is whether anyone knows of an even faster way to do it? Alternatively, whether there’s a more elegant way to do it with similar performance.

The lack of lexical scoping and having function arguments always be copied seems unfortunate from a performance point of view. Is my approach (i.e., to allocate data structures in the global scope and then pass around the symbol name) the standard approach?

---

<div class="post-metadata">

**Author:** ![albin](https://avatars.discourse-cdn.com/v4/letter/a/6de8d8/32.png) [@albin](https://forum.kx.com/u/albin)\
**Post date:** [February 12, 2024, 12:00am UTC](https://forum.kx.com/t/fastest-fibonacci-sequence-generator/13751/2 "2024-02-12T00:00:00Z")

</div>

It’s perhaps nicer to always fill the entire input array instead of taking the number of values to generate as an argument.

fibn:{[s] n: count get s; @[s; 0 1; :; 0 1]; f: {[s; i]; @[s; i; :; @[s; i-2] + @[s; i-1]]; i+1}; (f[s]/)[n-2; 2]; s} x: zeros[`long; 1000000] ts fibn[`x] / 319 576

Interestingly, this reduces the number of bytes allocated by 352, but seems to be slightly slower.

---

<div class="post-metadata">

**Author:** ![jfealy](https://avatars.discourse-cdn.com/v4/letter/j/50afbb/32.png) [@jfealy](https://forum.kx.com/u/jfealy)\
**Post date:** [February 13, 2024, 12:00am UTC](https://forum.kx.com/t/fastest-fibonacci-sequence-generator/13751/3 "2024-02-13T00:00:00Z")

</div>

Arthur’s K solution for first n+1 numbers

```
k)n(|+) 1 fib:{x,sum -2#x}/[;0 1] // first n+2 aq:{first flip x(reverse sums::) 1} 
// first n+1 
q)ts fib 100000 1359 2097392 
q) 
q) 
q)ts aq 100000 14 6345952
```

---

<div class="post-metadata">

**Author:** ![jfealy](https://avatars.discourse-cdn.com/v4/letter/j/50afbb/32.png) [@jfealy](https://forum.kx.com/u/jfealy)\
**Post date:** [February 16, 2024, 12:00am UTC](https://forum.kx.com/t/fastest-fibonacci-sequence-generator/13751/4 "2024-02-16T00:00:00Z")

</div>

`(reverse sums::)` is another method of generating a function composition [https://code.kx.com/q/ref/compose/](https://code.kx.com/q/ref/compose/")

```
q)'[reverse;sums]~(reverse sums::) 1b
```

&nbsp;

The definition you see for `reverse` is the monad form of the K verb `|` . The colon is an aid to the interpreter, as unless immediately used, the verb always denotes it’s dyad.

e.g. you can see the difference here, where the first item returned is the reverse of the list, and the second item is a projection of the OR dyad.

```
q)(|:;|)@:1 2 3 3 2 1 |[1 2 3]
```

&nbsp;

You can examine these in the `.q` namespace & there is further reading here [https://code.kx.com/q/basics/exposed-infrastructure/#unary-forms](https://code.kx.com/q/basics/exposed-infrastructure/#unary-forms")

```
q)5#.q | :: neg | -: not | ~: null | ^: string| $:
```

&nbsp;

In terms of the colons & their meanings, you can find more info & examples on this (and much more) in this excellent link [https://github.com/quintanar401/DCoQ?tab=readme-ov-file#mystery-of-](https://github.com/quintanar401/DCoQ?tab=readme-ov-file#mystery-of-")

&nbsp;

&nbsp;

---

<div class="post-metadata">

**Author:** ![albin](https://avatars.discourse-cdn.com/v4/letter/a/6de8d8/32.png) [@albin](https://forum.kx.com/u/albin)\
**Post date:** [February 16, 2024, 12:00am UTC](https://forum.kx.com/t/fastest-fibonacci-sequence-generator/13751/5 "2024-02-16T00:00:00Z")

</div>

Thank you for the suggestion . That’s an elegant solution.

I’m struggling to understand it though. Could you please help explain the following?

q) reverse sums 1 2 3 6 3 1 / This makes sense. q) (reverse sums) 1 2 3 1 3 6 / Why did we lose the reverse? q) (reverse sums::) 1 2 3 6 3 1 / Why did this recover the reverse? q) q) sums + / Makes sense. q) reverse |: / Reverse is a combination of the max and assignment operators? q) reverse sums + / Reverse was lost. q) reverse sums:: |+ / Max operator combined with sums?

I suspect the issue is I don’t understand the meaning of | and ::. I had thought | was just the max operator but maybe is also has other meanings? I know :: has at least these meanings:

- Defining a view.
- Assignment in-place.
- Assignment to a global variable.
- The generic null.
- The identity function.
- An elided index used to select everything.

Does :: have yet another meaning here or does one of the above apply?
