THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Peter Larsson

Thinking outside the box

Simple Fibonacci calculation

I have listened to the critique in the comments and removed the advanced version where you can calculate virtually any Fibonacci number. Contact me if you have the need for it again. I won't bother non-interested people with the algorithm here.

Instead, I am concentrating on how this easy example of how to use recursive CTE for calculating the Fibonacci series is constructed.

This is done as an easy exercise for students how to implement a recursive CTE, because the results can be confirmed visually.
Understanding recursive queries is not natural for many people.

For those of you not familiar with Fibonacci series and wonder what uses does it have, I can tell that Fibonacci series is used in a number of areas

  • Run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers (the worst case input for this algorithm is a pair of consecutive Fibonacci numbers
  • The Fibonacci numbers and principle is also used in the financial markets. It is used in trading algorithms, applications and strategies.
  • Fibonacci numbers are used by some pseudorandom number generators.
  • Fibonacci numbers are used in a polyphase version of the merge sort algorithm in which an unsorted list is divided into two lists whose lengths correspond to sequential Fibonacci numbers.
  • The Fibonacci cube is an undirected graph with a Fibonacci number of nodes that has been proposed as a network topology for parallel computing.
  • A one-dimensional optimization method, called the Fibonacci search technique, uses Fibonacci numbers.
  • The Fibonacci number series is used for optional lossy compression in the IFF 8SVX audio file format used on Amiga computers

So how is the Fibonacci series built?

The matemathical formula is F(n) = F(n-1) + F(n-2), which in plain english is that any Fibonacci number (greater than 2) is the sum of the two previous numbers.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 etc..

So how do we solve this using a recursive CTE (CTE is an acronym for Common Table Expression which was introduced with Microsof SQL Server 2005)?
Can we solve it at all? A recursive query is nested only one level, right? And the Fibonacci series is "nested" two level?

Yes, we can solve it by using a complementary "sideways" translation, a sort of intermediate storage. First thing, all recursive CTE need an anchor part, a fixed part from which the recursion is expanded from. I do this by using the values {0, 1} which per definition are the two first values of the Fibonacci series.

How is then the recursive part done? I use the two values from the previous iteration and sum them together for the next Fibonacci value. I store that value in a column, shift the columns, and use the previous value in the same recursion level. Easy, huh?

;WITH Fibonacci(n, f, f1)
AS (
        -- This is the anchor part
        -- Initialize level to 1 and set the first two values as per definition
        SELECT  CAST(1 AS BIGINT),
                CAST(0 AS BIGINT),
                CAST(1 AS BIGINT)

        UNION ALL

        -- This is the recursive part
        -- Calculate the next Fibonacci value using the previous two values
        -- Shift column (place) for the sum in order to accomodate the previous
        -- value too because next iteration need them both
        SELECT  n + 1,
                f + f1,
                f
        FROM    Fibonacci
        -- Stop at iteration 93 because we than have reached maximum limit
        -- for BIGINT in Microsoft SQL Server
        WHERE   n < 93
)
-- Now the easy presentation part
SELECT  n,
        f AS Number
FROM    Fibonacci

Published Sunday, October 18, 2009 3:08 PM by Peso
Filed under: , ,

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

Paul Nielsen said:

very cool. well done.

-Pn

October 18, 2009 10:16 AM
 

John Meriweather said:

What's the point of calculating the Fibonacci series in T-SQL? And why would anyone use t-SQL for that calculation?

October 19, 2009 1:53 PM
 

Jason said:

@Peter: This is a great example of a bad post.  

First of all, you only provide a heap of code with no explanation as to why it is interesting (thanks Peso) or how you might use it.

Second, your code essentially implements the addition operator for strings instead of just using the built in "+", which is just stupid.  

@Paul: This post is neither cool nor well done.

October 20, 2009 11:00 AM
 

Linchi Shea said:

I don't think John was questioning the significance of the Fibonacci series, but rather why one would do it with T-SQL. For classroom exercises and seminar demos, it's fine. It's also fine if one just wants to kill some time. But I'd agree that people should probably be cautioned not to actually end up writing production T-SQL code to do Fibonacci searies. Well, maybe there is a real case where writing it in T-SQL is justified. But it is certianly difficult to come up with one.

October 20, 2009 1:25 PM
 

Peso said:

New content posted.

October 20, 2009 2:54 PM
 

Jason said:

Hi Peter,

I like the revisions you made to this article.  Much more interesting.  

As an alternative to BIGINT, you could use DECIMAL(38,0) and calculate up to the 184th number in the sequence.

Thanks, Jason

October 21, 2009 9:51 AM
 

Joe Celko said:

Wouldn't it be faster to use the constant phi and the closed form?

Fibonacci(@n INTEGER)

AS

RETURN

EOUND (((POWER (1.6190339887, @n)- POWER (1.0 - 1.6190339887, @n))/

SQRT (5.0)), 0);

untested.

October 25, 2009 9:49 AM
 

Peso said:

It would be great if it worked! However, the golden ration is the ration for which division of Fibonacci number converges to, when sufficiently large.

However, the formula you displayed above gives wrong answer very early, and after step 12, the error is larger and larger

n Peso Celko

-- ---- -----

1 0 0

2 1 1

3 1 1

4 2 2

5 3 3

6 5 5

7 8 8

8 13 13

9 21 21

10 34 34

11 55 55

12 89 90

13 144 145

October 25, 2009 12:28 PM
 

RBArryYoung said:

This one is accurate up to n=62:

FLOOR(POWER(1.61803398874989, n)/SQRT(5) +.5)

:-)

October 26, 2009 2:27 AM
 

Peso said:

Much better.

October 26, 2009 2:52 AM

Leave a Comment

(required) 
(required) 
Submit
Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement