SQLServerCentral.com / SQL Server 2012 / SQL Server 2012 - T-SQL / Fibonacci numbers using a function. / Latest PostsInstantForum.NET v2.9.0SQLServerCentral.comhttp://www.sqlservercentral.com/Forums/notifications@sqlservercentral.comMon, 06 Jul 2015 04:14:28 GMT20RE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]Jeff Moden (2/25/2013)[/b][hr][quote]Who's got a CLR arbitrary precision library for SQL Server?[/quote]BWAAAA-HAAAA!!! SQL Server is a very small park for these types of things. That brings me back to what I said earlier... I believe that if you need Fibonacce numbers larger than 70 or even the max in SQL Server, then you're probably using the wrong tool. ;-)[/quote]If you need any Fibonacci numbers, SQL is the wrong tool. It's the wrong tool for 1, it's the wrong tool for 10, it's the wrong tool for 100. It's always the wrong tool.That's not the point - the point* is whether or not we can do it, and do it as efficiently as possible, as you already did for your constrained set :).I just want to remove the arbitrary limit! Regrettably, I've never so much as tried any CLR.*With a secondary point of poking fun at homework questions in a fun and constructive manner.Tue, 26 Feb 2013 08:42:05 GMTNadrekRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote]Who's got a CLR arbitrary precision library for SQL Server?[/quote]BWAAAA-HAAAA!!! SQL Server is a very small park for these types of things. That brings me back to what I said earlier... I believe that if you need Fibonacce numbers larger than 70 or even the max in SQL Server, then you're probably using the wrong tool. ;-)Mon, 25 Feb 2013 17:13:28 GMTJeff ModenRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]Jeff Moden (2/16/2013)[/b][hr]If we're going to do this, let's knock the problem right out of the park....We also come to the understanding that we can't directly calculate more than the 70th Fib number using this method because the FLOAT data-type returned by the SQRT function induces rounding errors after the precision of the return reaches just 15 digits....[/quote]Agreed! Out of the park 1) Blazing speed, small maximum - Jeff did that!Out of the park 2) Hardware resource limited maximumWho's got a CLR [url=http://www.mpir.org/]arbitrary precision library[/url] for SQL Server?ETA: A [url=http://www.codeplex.com/Wikipage?ProjectName=sine].NET arbitrary precision library[/url], though in alpha stage.And an [url=http://www.codeplex.com/Wikipage?ProjectName=IntX]integer only .NET arbitrary precision library[/url]Maybe even the .NET 4.0+ native [url=http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx]System.Numerics.BigInteger[/url]Mon, 25 Feb 2013 14:35:25 GMTNadrekRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxUsing DECIMALs with Binet's formula you can get the first 92 in the series[code="sql"]WITH Constants(one,half,root5,phi,phi2,phi4,phi8,phi16,phi32,phi64) AS (SELECT CAST(1.0 AS DECIMAL(38,20)), CAST(0.5 AS DECIMAL(38,20)), CAST(2.2360679774997896964091736687313 AS DECIMAL(38,20)), CAST(1.6180339887498948482045868343656 AS DECIMAL(38,20)), CAST(2.6180339887498948482045868343656 AS DECIMAL(38,20)), CAST(6.8541019662496845446137605030969 AS DECIMAL(38,20)), CAST(46.978713763747791812296323521678 AS DECIMAL(38,20)), CAST(2206.9995468961462151779272055189 AS DECIMAL(38,20)), CAST(4870846.9999997946968976853425802 AS DECIMAL(38,20)), CAST(23725150497406.999999999999957851 AS DECIMAL(38,20)))SELECT n.Number, CAST(CAST((CASE WHEN n.Number & 64 = 0 THEN c.one ELSE c.phi64 END * CASE WHEN n.Number & 32 = 0 THEN c.one ELSE c.phi32 END * CASE WHEN n.Number & 16 = 0 THEN c.one ELSE c.phi16 END * CASE WHEN n.Number & 8 = 0 THEN c.one ELSE c.phi8 END * CASE WHEN n.Number & 4 = 0 THEN c.one ELSE c.phi4 END * CASE WHEN n.Number & 2 = 0 THEN c.one ELSE c.phi2 END * CASE WHEN n.Number & 1 = 0 THEN c.one ELSE c.phi END) / c.root5 + c.half AS BIGINT) AS VARCHAR(20)) AS FibNumberFROM master.dbo.spt_values nCROSS JOIN Constants cWHERE n.type='P' AND n.Number BETWEEN 1 AND 92;[/code]Wed, 20 Feb 2013 03:20:19 GMTMark CowneRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]Jeff Moden (2/19/2013)[/b][hr]Ah. Understood. It would be interesting to find out which is actually faster, though. The mTVF with a loop or the iTVF with the recursive CTE.[/quote]Hehe. Normally I would take that challenge but I'm a bit swamped with other stuff going on right now. I agree that it would be interesting.Tue, 19 Feb 2013 17:12:40 GMTdwain.cRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxAh. Understood. It would be interesting to find out which is actually faster, though. The mTVF with a loop or the iTVF with the recursive CTE.Tue, 19 Feb 2013 09:26:05 GMTJeff ModenRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]Jeff Moden (2/18/2013)[/b][hr][quote][b]dwain.c (2/17/2013)[/b][hr]You can also do this with a recursive CTE, which can be put into an iTVF.See the first example, in the third article in my signature links.[/quote]Yes, you could. But even Peter Larsson's super trimmed down rCTE has a "counting rCTE" as a base. It may not matter much for single use but the formula method runs in sub-millisecond times whereas the rCTE takes 38 milliseconds (on my ever so humble desktop) for elements 0 through 70. You should check out the rads, as well. Recursion just ins't the answer for things like this unless it's to build a lookup table just one time.[/quote]I agree that the formula method would be faster even without running the actual test. That was a very clever approach by the way Jeff.I was just offering an alternative that could be put into an iTVF (unlike the loop).Mon, 18 Feb 2013 17:31:18 GMTdwain.cRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]dwain.c (2/17/2013)[/b][hr]You can also do this with a recursive CTE, which can be put into an iTVF.See the first example, in the third article in my signature links.[/quote]Yes, you could. But even Peter Larsson's super trimmed down rCTE has a "counting rCTE" as a base. It may not matter much for single use but the formula method runs in sub-millisecond times whereas the rCTE takes 38 milliseconds (on my ever so humble desktop) for elements 0 through 70. You should check out the rads, as well. Recursion just ins't the answer for things like this unless it's to build a lookup table just one time.Mon, 18 Feb 2013 12:32:26 GMTJeff ModenRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxYou can also do this with a recursive CTE, which can be put into an iTVF.See the first example, in the third article in my signature links.Sun, 17 Feb 2013 18:08:23 GMTdwain.cRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxHi Jeff thank you for the clarification,i understand well what you mean.Sat, 16 Feb 2013 02:16:40 GMTbyecolizRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]byecoliz (2/15/2013)[/b][hr]Hello,I am calculating the first 20 Fibonacci numbers using a function,but getting wrong answer.The condition is to write a function not a procedure. here is my try,help me.create function fn_fibo(@end int)returns intasbegindeclare @a int, @b int,@fib intset @a = 0set @b = 1set @fib = 0while @fib < @endbegin set @fib = @a + @b set @a = @b set @b = @fibendreturn @fibendselect dbo.fn_fibo(20)[/quote]What I'm really looking at from above is the following...[quote]The condition is to write a function not a procedure. [/quote]That means one of two things. 1. This is for some type of class you need to pass.2. This is for your job (I think not likely here but whatever).If we're going to do this, let's knock the problem right out of the park.First, one of the most important things to do is to do a little research. 1. We find that the largest positive number that the INT data-type can be is 2,147,483,647 and that a BIGINT can handle 9,223,372,036,854,775,807.2. Doing a bit of work in a spreadsheet using conventional calculation methods, we find that the largest Fib Number we can fit into an INT is the 46th Fib number or 1,836,311,903. So, instead, we decide to return a BIGINT from the function.3. Doing a bit of Googling, we figure out how to use an exact calculation using the "Golden Ratio" and "Binet's Formula" to directly calculate Fibonacci numbers. We also come to the understanding that we can't directly calculate more than the 70th Fib number using this method because the FLOAT data-type returned by the SQRT function induces rounding errors after the precision of the return reaches just 15 digits. We could use a "pseudo cursor" to get up to the 92nd Fib number (BIGINT fails after that) but we'll trade a little of the domain for blinding speed. Besides, if you need more than the 70th Fib number, then you're probably using the wrong tool. ;-)4. We also find that traditional methods of error checking don't work in a function but we still want to give more information about bad inputs. For sure, we don't want anyone to try to calculate more than the 70th Fib number because it will be an imprecise number.5. We also want this to be as fast as possible so it's absolutely essential to avoid all loops and other forms of RBAR including recursive CTEs that count.With all of that in mind, here's a function the will return the Nth Fibonacci number so long as N is between 1 and 70. It will return a "TOP" error for numbers less than 0, nothing for 0, a table of Fib numbers from 1 to whatever @End is providing 1 <= @End <= 70, and a thoughful error where @End > 70.[code="sql"] CREATE FUNCTION dbo.FibNumber (@End INT)RETURNS TABLE WITH SCHEMABINDING AS RETURN WITH R3(N) AS (SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1), R81(N) AS (SELECT 1 FROM R3 a, R3 b, R3 c, R3 d),cteTally(N) AS (SELECT TOP (@End) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM R81) SELECT t.N, FibNumber = CAST((1/SQRT(5))*(POWER((1+SQRT(5))/2,t.N)-POWER((1-SQRT(5))/2,t.N)) AS BIGINT) FROM cteTally t WHERE 1 = CASE WHEN @End BETWEEN 1 AND 70 THEN 1 ELSE 1/'[Error: Parameter of FibNumber greater than 70]' END;[/code]You use it to return your 20 Fib numbers like this...[code="sql"] SELECT * FROM dbo.FibNumber(20);[/code]For more information on how the cCTEs (Cascading CTEs) work to create numbers and how a Tally table or cteTally can replace certain loops, please see the following articles. [url]http://www.sqlservercentral.com/articles/T-SQL/62867/[/url][url]http://www.sqlmag.com/article/sql-server/virtual-auxiliary-table-of-numbers-103056[/url] As a sidebar, you might want to get out of the habit of using "Hungarian Notation" (the "fn_" prefix on your function). It's a bit of a yester-year habit that has seriously gone out of favor with many DBAs.Last but not least, avoid the loop wherever and whenever you can.Sat, 16 Feb 2013 00:51:57 GMTJeff ModenRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]Sean Lange (2/15/2013)[/b][hr]I converted this into an inline table value function like this.[/quote]Careful now. That's not an "inline" TVF. That's a "multiline" TVF. An iTVF must be a single query much like you'd write a view.Fri, 15 Feb 2013 20:31:24 GMTJeff ModenRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]Jeff Moden (2/15/2013)[/b][hr]I don't understand why people write functions for this. No matter how many time you run the code , the values will NEVER change. Why not just build a "helper" table to hold the values?[/quote]Agreed 100%. My guess is this has been a learning experience so from that perspective it has been worth it.Fri, 15 Feb 2013 14:59:21 GMTSean LangeRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxI don't understand why people write functions for this. No matter how many time you run the code , the values will NEVER change. Why not just build a "helper" table to hold the values?Fri, 15 Feb 2013 14:52:27 GMTJeff ModenRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxHere is David's solution with the syntax errors corrected.[code]create FUNCTION fn_fibo (@end INT)RETURNS VARCHAR(255)ASBEGIN DECLARE @a INT ,@b INT ,@fib INT ,@counter INT DECLARE @fstring VARCHAR(255) SET @end = @end - 2 SET @a = 0 SET @b = 1 SET @fib = 0 SET @counter = 0 SELECT @fstring = CAST(@a AS VARCHAR(10)) + ',' SELECT @fstring = @fstring + CAST(@b AS VARCHAR(10)) WHILE @counter < @end BEGIN SELECT @fstring = @fstring + ',' SET @fib = @a + @b SET @a = @b SET @b = @fib SELECT @fstring = @fstring + CAST(@fib AS VARCHAR(20)) SET @counter = @counter + 1 END RETURN @fstringEND[/code]This works but it returns all the values in a big long string that you now have to break apart to make it usable. It also is a scalar function which is notoriously slow. Add to this the while loop and this could get nasty quickly.I converted this into an inline table value function like this.[code]create FUNCTION itvf_fibo (@end INT)RETURNS @FibNums table( FibNum int)ASBEGIN DECLARE @a INT ,@b INT ,@fib INT ,@counter INT SET @end = @end - 2 SET @a = 0 SET @b = 1 SET @fib = 0 SET @counter = 0 insert @FibNums select @a union all select @b WHILE @counter < @end BEGIN SET @fib = @a + @b SET @a = @b SET @b = @fib insert @FibNums select @fib SET @counter = @counter + 1 END return;END[/code]I would like to take this one step further and turn this into a set based approach using a tally table. Unfortunately I have a meeting in about 2-3 minutes. If nobody else happens along I will try to pick this up.Fri, 15 Feb 2013 13:28:16 GMTSean LangeRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxWow, thanks David for that solution, and Sean thanks too for the guidance.Fri, 15 Feb 2013 12:02:59 GMTbyecolizRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxAs Sean said, you can't return 20 numbers in an int. You could string them together in a single return value like so:[code="sql"]create function fn_fibo(@end int)returns varchar(255)asbegindeclare @a int, @b int,@fib int, @counter intdeclare @fstring varchar(255) set @end = @end - 2set @a = 0set @b = 1set @fib = 0set @counter = 0select @fstring = CAST(@a as varchar(10)) + ','select @fstring = @fstring + CAST(@b as varchar(10))while @counter < @endbeginselect @fstring = @fstring + ','set @fib = @a + @bset @a = @bset @b = @fibselect @fstring = @fstring + CAST(@fib as varchar(20))set @counter = @counter + 1 end[/code]That's the long way around and I'm sure there are other folks who can jump in with more efficient solutions, but that's the basic idea.Fri, 15 Feb 2013 11:47:10 GMTDavid Webb-CDSRE: Fibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspx[quote][b]byecoliz (2/15/2013)[/b][hr]Hello,I am calculating the first 20 Fibonacci numbers using a function,but getting wrong answer.The condition is to write a function not a procedure. here is my try,help me.create function fn_fibo(@end int)returns intasbegindeclare @a int, @b int,@fib intset @a = 0set @b = 1set @fib = 0while @fib < @endbegin set @fib = @a + @b set @a = @b set @b = @fibendreturn @fibendselect dbo.fn_fibo(20)[/quote]It looks like your calculation is correct but your logic isn't quite. You need to look at what you are doing here. You want a collection of numbers but your function returns an int. You need to do something inside your loop instead of just adding the numbers. There is no chance you can make a scalar function return the first 20 numbers. To do this you will need to use a table valued function.Fri, 15 Feb 2013 10:44:40 GMTSean LangeFibonacci numbers using a function.http://www.sqlservercentral.com/Forums/Topic1420665-3077-1.aspxHello,I am calculating the first 20 Fibonacci numbers using a function,but getting wrong answer.The condition is to write a function not a procedure. here is my try,help me.create function fn_fibo(@end int)returns intasbegindeclare @a int, @b int,@fib intset @a = 0set @b = 1set @fib = 0while @fib < @endbegin set @fib = @a + @b set @a = @b set @b = @fibendreturn @fibendselect dbo.fn_fibo(20)Fri, 15 Feb 2013 10:18:49 GMTbyecoliz