3 ms·
A better example would be the Fibonacci sequence, or some other inductive process.
by philipov 2y ago
A better example would be the Fibonacci sequence, or some other inductive process.
- dragontamer 2y agoLinked Lists and other Tree Traversals are sequential. Raytracing (which is a tree traversal) is a notable exception because there's so many millions of rays that get launched, that it becomes efficient to group them back together and then parallelize the traversals all together. So if you have "enough" of them going at once, its back to GPU Superiority. But a *SINGLE* linked list or *SINGLE* tree search will always be best done on a CPU.
- Legend2440 2y agoGenerally recurrent sequences cannot be computed in parallel, but the Fibonacci sequence is a special case because it's a linear recurrence. There's a closed-form equation to generate the Nth number.