undefined | Better HN

0 pointsexikyut7y ago0 comments

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.

0 comments

userbinator7y ago

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.

leghifla7y ago

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.

j / k navigate · click thread line to collapse