An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 21, 2021 12:13 UTC (Sun) by pebolle (guest, #35204)
In reply to: An introduction to lockless algorithms by ballombe
Parent article: An introduction to lockless algorithms

> [...] recursion *does not* work for computing Fibonacci numbers...

I just double checked - I was afraid that my memory let me down again - but recursion does work for Fibonacci. At least, that's what the web and the only introductory programming book I have on my shelves tells me.

Perhaps we disagree on the meaning of "recursion" and "work"?

to post comments

An introduction to lockless algorithms

Posted Feb 21, 2021 12:29 UTC (Sun) by Wol (subscriber, #4433) [Link] (6 responses)

int fibonacci( int f)
{
if (f <= 1)
return f;
else
return fibonacci( f-1) + fibonacci( f-2);
}

Which will blow your stack for large values of f :-)

I hope I've got it right ... :-)

Cheers,
Wol

An introduction to lockless algorithms

Posted Feb 21, 2021 13:08 UTC (Sun) by dtlin (subscriber, #36537) [Link]

With that implementation, there's a good chance you'll experience integer wraparound (and thus wrong results) before you blow the stack. fib(92) = 7540113804746346429, fib(93) = 12200160415121876738 which doesn't fit in a 64-bit signed integer.

The problem with the recursive solution is the exponential runtime; the stack usage is linear.

An introduction to lockless algorithms

Posted Feb 21, 2021 15:24 UTC (Sun) by Wol (subscriber, #4433) [Link] (1 responses)

I knew I should have checked it ...

The start of the conditional should be

if (f <= 2) return 1;

Cheers,
Wol

An introduction to lockless algorithms

Posted Feb 21, 2021 16:16 UTC (Sun) by yann.morin.1998 (guest, #54333) [Link]

> The start of the conditional should be
> if (f <= 2) return 1;

Not necessarily. The generalised Fibonacci sequence starts with F(0) = 0 and F(1) = 1 [0]. So your initial condition was (not in)correct.

[0] https://en.wikipedia.org/wiki/Fibonacci_number

An introduction to lockless algorithms

Posted Feb 21, 2021 17:10 UTC (Sun) by matthias (subscriber, #94967) [Link]

This will definitely not blow the stack. Even for quite small numbers of f, the runtime will be longer than the age of the universe.

An introduction to lockless algorithms

Posted Feb 21, 2021 23:41 UTC (Sun) by neilbrown (subscriber, #359) [Link]

> Which will blow your stack for large values of f :-)

Only if you try to implement it on a computer.
As a mathematical abstraction, this is perfectly fine and well defined for all f.

An introduction to lockless algorithms

Posted Mar 5, 2021 0:13 UTC (Fri) by qzPhUZ7af5M6kjJi3tDgMaVq (guest, #140267) [Link]

Recursive definitions work just fine in certain programming languages.

https://wiki.haskell.org/The_Fibonacci_sequence

In a Haskell interpreter:

Prelude> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Prelude> fibs !! 100000

(20,899 digit number omitted... it took about 2 seconds to compute it)

An introduction to lockless algorithms

Posted Feb 22, 2021 9:49 UTC (Mon) by ballombe (subscriber, #9523) [Link] (1 responses)

To compute fibo(50) the naive sequential algorithm needs 50 additions, the naive recursive algorithm needs
12586269025 additions. That is what I call 'not working'.

An introduction to lockless algorithms

Posted Feb 22, 2021 10:04 UTC (Mon) by pebolle (guest, #35204) [Link]

I'll file this under 'Disagreeing what "work" means' too.