An introduction to lockless algorithms

Posted Feb 21, 2021 12:29 UTC (Sun) by Wol (subscriber, #4433)
In reply to: An introduction to lockless algorithms by pebolle
Parent article: An introduction to lockless algorithms

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)