Challenge #3 - The Fibonacci Series

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

All Forums

SQL Server 2000 Forums

Transact-SQL (2000)

Challenge #3 - The Fibonacci Series

Author

Topic

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2003-11-20 : 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

"SQL-3 is an abomination.."

Merkin
Funky Drop Bear Fearing SQL Dude!

4970 Posts

Posted - 2003-11-20 : 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

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2003-11-20 : 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!

4970 Posts

Posted - 2003-11-20 : 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

1591 Posts

Posted - 2003-11-20 : 21:28:49

I was hoping somebody wouldn't use that!
[url]http://www.math.hmc.edu/funfacts/ffiles/10002.4-5.shtml[/url]

Damn Google!!!

DavidM

"SQL-3 is an abomination.."

Merkin
Funky Drop Bear Fearing SQL Dude!

4970 Posts

Posted - 2003-11-20 : 21:32:00

Yeah, it is cheating a little

Damian

byrmol
Shed Building SQL Farmer

1591 Posts

Posted - 2003-11-20 : 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!

4970 Posts

Posted - 2003-11-20 : 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

7423 Posts

Posted - 2003-11-20 : 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

1591 Posts

Posted - 2003-11-20 : 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!

4970 Posts

Posted - 2003-11-20 : 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

1591 Posts

Posted - 2003-11-20 : 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

"SQL-3 is an abomination.."

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2003-11-21 : 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

7423 Posts

Posted - 2003-11-21 : 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

nr
SQLTeam MVY

12543 Posts

Posted - 2003-11-21 : 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

3467 Posts

Posted - 2003-11-21 : 19:28:30

Nigel ! Duuuuude !

Hey... With respect to all the contributors, Nigel's is the razor of all the solutions. (so far)

nr
SQLTeam MVY

12543 Posts

Posted - 2003-11-21 : 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
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2003-11-22 : 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

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2003-11-22 : 06:52:52

LOL Jay.. it should be named as gessel-ehorn solution..

JuniorFletch
Starting Member

1 Post

Posted - 2013-07-05 : 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

"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

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources