[exikyut]

FWIW, the article mentions a possible followup "using ... MMX, XMM or SIMD". (To clarify, XMM is SSE.) SIMD is noted last as though it's the newest development, when that would arguably be is at least AVX, and AVX-512 to be specific.

[willvk]

Thanks for that. I didn't intend for it to be a chronological list but will add AVX to it. Cheers.

[exikyut]

Oh, okay, my bad!

And wow, fibonacci using hand-rolled AVX :) that would definitely be a sight to see.

...although, I should explicitly point out, AVX is a set of vector streaming/processing instructions. Fibonacci is inherently a single-step operation, with no lookahead.

Okay, so I googled "fibonacci avx". The results were quite a mess but some careful wading found me http://www.insideloop.io/blog/2014/10/14/arrays-part-iii-vec..., which states: "A a consequence, the following code that computes the sequence of Fibonacci can’t get vectorized."

So, forgive my own (bullish!) naivete. AVX, and _possibly_ SIMD, SSE, etc _may not_ be applicable to/usable for Fibonacci computation.

[userbinator]

Vector instructions are certainly usable for scalar computation, although it doesn't make much sense --- you basically just use one piece of one vector and throw away all the other results.

Fibonacci is a toy example but illustrates where the vector instructions do become useful: if you want to compute the n'th term of various Fibonacci-like sequences with different starting conditions but the same recurrence, then you could do them in parallel using those instructions.

[leghifla]

Unrolling the computation of the series, it is possible to compute f(n) using only f(n-4) and f(n-8):

f(n) = 7*f(n-4)-f(n-8)

So, using 4-vector operations, you can compute 4 numbers in one step.