An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Mar 11, 2021 9:56 UTC (Thu) by anselm (subscriber, #2796)
In reply to: An introduction to lockless algorithms by dtlin
Parent article: An introduction to lockless algorithms

It has a closed-form solution but that does not make it O(1).

If your platform only supports integers up to a certain maximum (say 2^64-1), it is O(1) because it is straightforward to create a lookup table for all n where F(n) < 2^64 and use that rather than the recursive definition.

to post comments

An introduction to lockless algorithms

Posted Mar 11, 2021 19:28 UTC (Thu) by nybble41 (subscriber, #55106) [Link] (3 responses)

> … it is O(1) because it is straightforward to create a lookup table for all n where F(n) < 2^64 and use that rather than the recursive definition.

If you strict permissible inputs to a predetermined finite range then every algorithm becomes O(1). That's not a very useful definition, though. And while a 93-entry table suffices to represent all Fibonacci numbers less than 2^64, many languages have built-in arbitrary-precision integer types limited only by available memory.

An introduction to lockless algorithms

Posted Mar 12, 2021 10:49 UTC (Fri) by anselm (subscriber, #2796) [Link] (1 responses)

Obviously. I think the point here is that Fibonacci numbers are often used as a prime example for the use of recursion, but in practice, calculating Fibonacci numbers through a 1:1 implementation of their recursive definition is not what one would actually ever do. As such it gives people silly ideas. It would be better to come up with examples where there are more compelling arguments for using recursion in the first place, or at the very least put a big health warning on the Fibonacci example.

An introduction to lockless algorithms

Posted Mar 13, 2021 8:54 UTC (Sat) by neilbrown (subscriber, #359) [Link]

I recall in first year CompSci, recursion was introduced using the Towers of Hanoi game. I think that is an excellent vehicle, much better than Fibonacci.

An introduction to lockless algorithms

Posted Mar 16, 2021 20:49 UTC (Tue) by nix (subscriber, #2304) [Link]

The canonically crazy example of this is the wonderful Hutter search: https://arxiv.org/abs/cs/0206022. The title describes it well: it is, in fact, the fastest and shortest general algorithm possible if you want one single algorithm that can solve all well-defined problems -- but given that it involves searching for and then executing all possible programs until it finds the one that solves the problem you asked about, it is somewhat impractical. You might find it useful if you are looking for something for your hypercomputer to run when you are bored of having it work out all the busy beaver numbers up to 10^100...