question

Mark avatar image
Mark asked

Fibonacci Sequence Calculation

What's the best way to calculate a Fibonacci Sequence in T-SQL? A Fibonacci Sequence is "obtained by adding the two previous Fibonacci numbers together," like so: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... (I'm just curious about this - not a work requirement or urgent in any way.)
t-sqlrecursioncalculations
10 |1200 characters needed characters left characters exceeded

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

KenJ avatar image
KenJ answered
Here's one from [BeyondRelational][1] that is good for the 1st 70 numbers. It succumbs to rounding errors after that, so I limited the output. SELECT FLOOR(POWER(( 1 + SQRT(5) ) / 2.0, number) / SQRT(5) + 0.5) AS fib_number FROM master..spt_values WHERE TYPE = 'p' AND number BETWEEN 1 AND 70 Stumbled across a [list][2] of the first 1001 Fibonacci numbers, while I was out there. [1]: http://beyondrelational.com/blogs/madhivanan/archive/2009/09/01/generate-fibonacci-series-no-loop-no-recursion.aspx [2]: http://www.fullbooks.com/The-first-1001-Fibonacci-Numbers.html
7 comments
10 |1200 characters needed characters left characters exceeded

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

@Mark There's a really good read on Phi and Fibonacci here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/ The whole concept made much more sense to me after a look at it. And it gave me an appreciation of just what a luminary Euclid was.
1 Like 1 ·
Nice one..... :-)
0 Likes 0 ·
Wow - I confess that I have little clue as to how that works. But good one, we may have a winner!
0 Likes 0 ·
The BeyondRelational site you refer to also shows a quirky update method - nice! And these examples actually work without recursion too - another bonus!
0 Likes 0 ·
The master..spt_values is here instead of tally table. It provides only numbers. So if you have a tally, you can use it. The rest of magic is in the math operations. :-) Probably will be the winner one when compared speed.
0 Likes 0 ·
Show more comments
Tim avatar image
Tim answered
This is the easiest way for me. Simply plug in your values into the parameters. I started with 1 and 1 like your example. DELCARE @Y INT DECLARE @Z INT DECLARE @FIB INT SET @Y = 1 SET @Z = 1 SET @FIB = 0 PRINT @Y PRINT @Z WHILE @FIB < 2000 BEGIN SET @FIB = @Y + @Z PRINT @FIB SET @Y = @Z SET @Z = @FIB END
4 comments
10 |1200 characters needed characters left characters exceeded

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Sorry, take it back, you actually limit the value not the argument. Looks like I cannot see straight today :(
2 Likes 2 ·
Using a WHILE was my first thought too. But I think a CTE is better in a way.
1 Like 1 ·
@FIB < 2000? No way, fib(50) blows waaay past the integer limit, and to spell Fib(2000) you will need more than 400 digits which is much bigger than the max value of any available data type
0 Likes 0 ·
@Oleg, no worries.
0 Likes 0 ·
Pavel Pawlowski avatar image
Pavel Pawlowski answered
Here is a very nice solution which uses CTE, not from my head but found it on SQL Server Central: [Fibonacci Sequence CTE][1]. I've only slightly altered it to return the maximum sequence which fits to int data type. WITH Fib(Num, fib, fib2) AS ( SELECT 0 AS Expr1, 0 AS Expr2, 1 AS Expr3 UNION ALL SELECT Num + 1 AS Expr1, fib + fib2 AS Expr2, fib FROM Fib AS fib_2 WHERE (Num <= 44) ) SELECT Num, fib AS Fibonacci_Number FROM Fib AS Fib_1 WHERE Num > 0 [1]: http://www.sqlservercentral.com/Forums/Topic1001759-1291-1.aspx
1 comment
10 |1200 characters needed characters left characters exceeded

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Ha! I searched ASK for this, but not SCC itself.
0 Likes 0 ·
Magnus Ahlkvist avatar image
Magnus Ahlkvist answered
I think Fib(182) is as far as one can go with SQL Server. I used the answer from @Pavel Pawlowski to create a Fib-function to test it. CREATE FUNCTION dbo.Fib(@n int) RETURNS numeric(38,0) AS BEGIN DECLARE @i numeric(38,0); WITH Fib(Num, fib, fib2) AS ( SELECT 0 AS Expr1, cast(0 as numeric(38,0)) AS Expr2, cast(1 as numeric(38,0)) AS Expr3 UNION ALL SELECT Num + 1 AS Expr1, fib + fib2 AS Expr2, fib FROM Fib AS fib_2 WHERE (Num
10 |1200 characters needed characters left characters exceeded

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.

Write an Answer

Hint: Notify or tag a user in this post by typing @username.

Up to 2 attachments (including images) can be used with a maximum of 512.0 KiB each and 1.0 MiB total.