Please start any new threads on our new site at http://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

Our new SQL Server Forums are live! Come on over! We've restricted the ability to create new threads on these forums.

 SQL Server Forums Profile | Active Topics | Members | Search | Forum FAQ Register Now and get your question answered!
 All Forums  SQL Server 2000 Forums  Transact-SQL (2000)  Challenge #3 - The Fibonacci Series Reply to Topic  Printer Friendly
Author  Topic

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

 Posted - 11/20/2003 :  18:35:13 In the spirit of SQL Challenges, calculate the first 20 Fibonacci numbers. Because the series is not a set I will allow the ommission or explicit insertion of the first two numbers 0 and 1.As a guide here is the first 10 numbers 0,1,1,2,3,5,8,13,21,34,55Rules:1) Solutions similar to the following are disallowed... ``` DECLARE @One INT, @Two INT DECLARE @Fibonacci TABLE (Number INT NOT NULL) --Insert first two numbers 0 and 1 INSERT @Fibonacci (Number) SELECT 0 UNION ALL SELECT 1 SELECT @One = 0, @Two = 1 WHILE (SELECT COUNT(*) FROM @Fibonacci) < 20 BEGIN INSERT @Fibonacci (Number) VALUES(@One + @Two) SELECT @Two = @One + @Two, @One = @Two - @One END SELECT * FROM @Fibonacci GO ```SQL please not modified VB..DavidM"SQL-3 is an abomination.."

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

 Posted - 11/20/2003 :  20:24:37 HmmmDoes this work for you ?Assuming you have a Sequence Table/*Create Table Sequence (seq int not null)SET nocount ondeclare @val intselect @val = 1while @val <= 8000 begin Insert into sequence values (@val) select @val = @val + 1 endSet nocount offGO*/The query is this :Declare @seq varchar(2000), @this int, @last int, @oneBefore intSET @last = 1SET @oneBefore = 0Select @this = @last + @oneBefore, @Seq = isNull(@seq + ', ', '') + Cast(@this as varchar(5)), @oneBefore = @last, @last = @thisFROMSequence sWHERE s.seq < 21Select @seqDamian Edited by - Merkin on 11/20/2003 20:36:20

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

 Posted - 11/20/2003 :  20:54:01 That does work, but can you modify it to return as rows in a table?DavidM"SQL-3 is an abomination.."

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

 Posted - 11/20/2003 :  21:10:32 OKA little maths never goes astray Declare @phi floatSelect @phi = (1 + Sqrt(5))/2SELECT CAST( (POWER(@phi, seq) - POWER(-1/@Phi, seq )) / Sqrt(5) as int )FROM SequenceWHERE seq < 21Damian

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

 Posted - 11/20/2003 :  21:28:49 I was hoping somebody wouldn't use that!http://www.math.hmc.edu/funfacts/ffiles/10002.4-5.shtmlDamn Google!!!DavidM"SQL-3 is an abomination.."

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

 Posted - 11/20/2003 :  21:32:00 Yeah, it is cheating a little Damian

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

 Posted - 11/20/2003 :  21:41:26 Nothing wrong with that though!Using the Numbers/Sequence table and a formulae like this really shows the power of working with sets. You ain't got get a faster result than that.. And as a bit of a side note SQL Server can cope with up to 1474 fibonacci numbers with that number being.. 4.9922546054780146E+307.. with almost no apparent speed degradation..I used ROUND instead of CAST...``` SELECT ROUND((POWER(((1 + Sqrt(5))/2), Number) - POWER(-1/((1 + Sqrt(5))/2), Number )) / Sqrt(5) ,1) FROM Numbers WHERE Number < 1475 ```DavidM"SQL-3 is an abomination.."

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

 Posted - 11/20/2003 :  21:48:17 The only other way I got is a variation on the first, and it uses a loop.I like the formula bestCreate Table #fib ( counter int, seq int)INSERT INTO #fib (counter)SELECT seq FROM sequence WHERE seq < 21Declare @this int, @last int, @oneBefore int, @cnt intSET @cnt = 1SET @last = 1 SET @oneBefore = 0WHILE @@Rowcount > 0 UPDATE #fib SET @this = @last + @oneBefore, seq = @this, @oneBefore = @last, @last = @this, @cnt = @cnt + 1 WHERE counter = @cnt and seq is nullSELECT seq FROM #fibDROP TABLE #fibDamian

jsmith8858
Dr. Cross Join

USA
7423 Posts

 Posted - 11/20/2003 :  21:52:49 WOW! cool formula .... very neat! nice problem, wish I had more time to work on it . I'm amazed that a formula exists to return the Nth member ...- Jeff

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

 Posted - 11/20/2003 :  22:28:22 "This formula is attributed to Binet in 1843, though known by Euler before him."Considering that Euler was almost 100 years earlier.. Awesome minds. We need more people like this NOW. It does remind of a guy I went to school with.. Photographic memory, coupled with a keen mind, this guy was SMART. In the 12th Grade (Last year of High School in OZ), he proposed a hypothesis for the duality of light that our Physics teacher couldn't fault, although when the physics teacher showed it to some of his Uni prof mates they did see a couple of faults.. Anyway what did he do with this talent.. F#\$%ing Business/Law degree!!!I really can't think of any non-iterative solution other than the formulae...DavidM"SQL-3 is an abomination.."

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

 Posted - 11/20/2003 :  22:35:26 quote:I really can't think of any non-iterative solution other than the formulae...Oh sure. NOW you tell us Damian

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

 Posted - 11/20/2003 :  22:40:04 quote:Oh sure. NOW you tell usWhy would I post otherwise! Oh yeah, I'm arsehole.. Must remember that...Anyway here was my iterative solution...``` DECLARE @Fibonacci TABLE (Number INT NOT NULL) INSERT @Fibonacci (Number) SELECT 0 UNION ALL SELECT 1 WHILE (SELECT COUNT(*) FROM @Fibonacci) < 20 BEGIN INSERT @Fibonacci (Number) SELECT SUM(Number) FROM (SELECT TOP 2 Number FROM @Fibonacci ORDER BY Number DESC) AS X END SELECT * FROM @Fibonacci ```DavidM"SQL-3 is an abomination.."

Freaky Yak Linguist

*
1983 Posts

 Posted - 11/21/2003 :  15:10:26 LOL.. few days ago I was going to propose the subjectbut then decided on it as not much interesting.. Binet..

jsmith8858
Dr. Cross Join

USA
7423 Posts

 Posted - 11/21/2003 :  16:50:11 Check this out; no loop and no numbers table:``` create function FibNums(@n1 int, @n2 int, @count int) returns @t table (i int) as begin declare @n3 int set @n3 = @n2 + @n1 set @count = @count-1 if @count <> 0 insert into @t select @n3 union select * from dbo.FibNums(@n2,@n3,@count) return end select * from dbo.FibNums(0,1,20) ```Something a little different .... the 0,1 in the beginning isn't returned but it's kinda cool ... a recursive table function !It would be shorter but expressions such as @n2+@n3 aren't allowed as arguments in UDF's ... - Jeff Edited by - jsmith8858 on 11/21/2003 16:53:22

nr
SQLTeam MVY

United Kingdom
12543 Posts

 Posted - 11/21/2003 :  17:09:21 create table #a(i int identity, j int)insert #a (j) select 0insert #a (j) select 1while @@identity <= 20insert #a select sum(j) from (select top 2 j from #a order by i desc) aselect j from #a order by id==========================================Cursors are useful if you don't know sql.DTS can be used in a similar way.Beer is not cold and it isn't fizzy.

SamC
White Water Yakist

USA
3467 Posts

 Posted - 11/21/2003 :  19:28:30 Nigel ! Duuuuude !Hey... With respect to all the contributors, Nigel's is the razor of all the solutions. (so far) Edited by - SamC on 11/21/2003 19:36:49

nr
SQLTeam MVY

United Kingdom
12543 Posts

 Posted - 11/21/2003 :  20:44:11 Well at least for slow typists like me :).==========================================Cursors are useful if you don't know sql.DTS can be used in a similar way.Beer is not cold and it isn't fizzy.

ehorn
Flowing Fount of Yak Knowledge

USA
1632 Posts

 Posted - 11/22/2003 :  00:03:27 Rather than calculating the fibonacci number, here is a method to detect when n is a fibonacci number.Gessel solved this in 1972 with a very simple test:n is a Fibonacci number if and only if 5 N^2 + 4 or 5 N^2 – 4 is a square number.For instance, 3 is a Fibonacci number since 5x3^2+4 is 49 which is 7^2 5 is a Fibonacci number since 5x5^2–4 is 121 which is 11^2 4 is not a Fibonacci number since neither 5x4^2+4=84 nor 5x4^2–4=76 are pefect squares. ```SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT n FROM Numbers WHERE ( ( power(round(sqrt((5 * power(convert(bigint,n),2)) + 4),0),2) = (5 * power(convert(bigint,n),2)) + 4 ) OR ( power(round(sqrt((5 * power(convert(bigint,n),2)) - 4),0),2) = (5 * power(convert(bigint,n),2)) - 4 ) ) AND (LOG(n) + LOG(5)/2)/LOG((1 + Sqrt(5))/2) <= 20 ORDER BY n ``` Edited by - ehorn on 11/22/2003 00:26:46

Freaky Yak Linguist

*
1983 Posts

 Posted - 11/22/2003 :  06:52:52 LOL Jay.. it should be named as gessel-ehorn solution..

JuniorFletch
Starting Member

USA
1 Posts

 Posted - 07/05/2013 :  13:37:41 quote:Originally posted by byrmolIn the spirit of SQL Challenges, calculate the first 20 Fibonacci numbers. Because the series is not a set I will allow the ommission or explicit insertion of the first two numbers 0 and 1.As a guide here is the first 10 numbers 0,1,1,2,3,5,8,13,21,34,55Rules:1) Solutions similar to the following are disallowed... ``` DECLARE @One INT, @Two INT DECLARE @Fibonacci TABLE (Number INT NOT NULL) --Insert first two numbers 0 and 1 INSERT @Fibonacci (Number) SELECT 0 UNION ALL SELECT 1 SELECT @One = 0, @Two = 1 WHILE (SELECT COUNT(*) FROM @Fibonacci) < 20 BEGIN INSERT @Fibonacci (Number) VALUES(@One + @Two) SELECT @Two = @One + @Two, @One = @Two - @One END SELECT * FROM @Fibonacci GO ```SQL please not modified VB..DavidM"SQL-3 is an abomination.."/*Recursive version to be different, albeit less efficient =)*/``` with Fibonacci as ( SELECT 0 as Seq, 0 as "Seq[N-2]", 1 as "Seq[N-1]", 1 as N UNION ALL SELECT "Seq[N-1]" + Seq, Seq + "Seq[N-2]", Seq, N + 1 FROM Fibonacci WHERE N < 20 ) SELECT Seq FROM Fibonacci ```
Topic
 Reply to Topic  Printer Friendly Jump To: Select Forum General SQL Server Forums       New to SQL Server Programming       New to SQL Server Administration       Script Library       Data Corruption Issues       Database Design and Application Architecture SQL Server 2012 Forums       Transact-SQL (2012)       SQL Server Administration (2012)       SSIS and Import/Export (2012)       Analysis Server and Reporting Services (2012)       Replication (2012)       Availability Groups and DR (2012)       Other SQL Server 2012 Topics SQL Server 2008 Forums       Transact-SQL (2008)       SQL Server Administration (2008)       SSIS and Import/Export (2008)       High Availability (2008)       Replication (2008)       Analysis Server and Reporting Services (2008)       Other SQL Server 2008 Topics SQL Server 2005 Forums       Transact-SQL (2005)       SQL Server Administration (2005)       .NET Inside SQL Server (2005)       SSIS and Import/Export (2005)       Service Broker (2005)       Replication (2005)       High Availability (2005)       Analysis Server and Reporting Services (2005)       Express Edition and Compact Edition (2005)       Other SQL Server Topics (2005) SQL Server 2000 Forums       SQL Server Development (2000)       SQL Server Administration (2000)       Import/Export (DTS) and Replication (2000)       Transact-SQL (2000)       Analysis Services (2000)       MSDE (2000) Development Tools       ASP.NET       Reporting Services Development       Other Development Tools Site Related Forums       Site Related Discussions       Article Discussion       Poll Discussion       The Yak Corral Other Forums       SQL Server 6.5 \ SQL Server 7.0       Other Topics       MS Access       ClearTrace Support Forum Old Forums       CLOSED - General SQL Server       CLOSED - SQL Server 2005/Yukon  -------------------- Home Active Topics Frequently Asked Questions Member Information Search Page
 SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC
 This page was generated in 0.14 seconds.