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,55
Rules: 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
"SQL3 is an abomination.." 

Merkin
Funky Drop Bear Fearing SQL Dude!
Australia
4970 Posts 
Posted  11/20/2003 : 20:24:37

Hmmm
Does this work for you ?
Assuming you have a Sequence Table
/* Create Table Sequence (seq int not null) SET nocount on declare @val int select @val = 1 while @val <= 8000 begin Insert into sequence values (@val) select @val = @val + 1
end
Set nocount off GO */
The query is this :
Declare @seq varchar(2000), @this int, @last int, @oneBefore int
SET @last = 1 SET @oneBefore = 0
Select @this = @last + @oneBefore, @Seq = isNull(@seq + ', ', '') + Cast(@this as varchar(5)), @oneBefore = @last, @last = @this FROM Sequence s WHERE s.seq < 21
Select @seq
Damian 
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
"SQL3 is an abomination.." 


Merkin
Funky Drop Bear Fearing SQL Dude!
Australia
4970 Posts 
Posted  11/20/2003 : 21:10:32

OK
A little maths never goes astray
Declare @phi float Select @phi = (1 + Sqrt(5))/2
SELECT CAST( (POWER(@phi, seq)  POWER(1/@Phi, seq )) / Sqrt(5) as int ) FROM Sequence WHERE seq < 21
Damian 


byrmol
Shed Building SQL Farmer
Australia
1591 Posts 

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
"SQL3 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 best
Create Table #fib ( counter int, seq int )
INSERT INTO #fib (counter) SELECT seq FROM sequence WHERE seq < 21
Declare @this int, @last int, @oneBefore int, @cnt int
SET @cnt = 1 SET @last = 1 SET @oneBefore = 0
WHILE @@Rowcount > 0 UPDATE #fib SET @this = @last + @oneBefore, seq = @this, @oneBefore = @last, @last = @this, @cnt = @cnt + 1 WHERE counter = @cnt and seq is null
SELECT seq FROM #fib
DROP TABLE #fib
Damian 


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 noniterative solution other than the formulae...
DavidM
"SQL3 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 noniterative 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 us
Why 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
"SQL3 is an abomination.." 


Stoad
Freaky Yak Linguist
*
1983 Posts 
Posted  11/21/2003 : 15:10:26

LOL.. few days ago I was going to propose the subject
but 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 = @count1
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 0 insert #a (j) select 1
while @@identity <= 20 insert #a select sum(j) from (select top 2 j from #a order by i desc) a
select 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 


Stoad
Freaky Yak Linguist
*
1983 Posts 
Posted  11/22/2003 : 06:52:52

LOL Jay.. it should be named as gesselehorn solution.. 


JuniorFletch
Starting Member
USA
1 Posts 
Posted  07/05/2013 : 13:37:41

quote: Originally posted by byrmol
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,55
Rules: 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
"SQL3 is an abomination.."
/*Recursive version to be different, albeit less efficient =)*/
with Fibonacci as
(
SELECT
0 as Seq,
0 as "Seq[N2]",
1 as "Seq[N1]",
1 as N
UNION ALL
SELECT
"Seq[N1]" + Seq,
Seq + "Seq[N2]",
Seq,
N + 1
FROM
Fibonacci
WHERE
N < 20
)
SELECT
Seq
FROM
Fibonacci




Topic 
