Fastest Fibonacci sequence generator

Community Support
,
1

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:

 

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

 

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:

 

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

 

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?

2

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.

3

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
4

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

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

 

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]

 

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

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

 

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-

 

 

5

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?