SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 SQL Server 2000 Forums
 Transact-SQL (2000)
 Challenge #3 - The Fibonacci Series
 New Topic  Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

Posted - 11/20/2003 :  18:35:13  Show Profile  Reply with Quote
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!

Australia
4970 Posts

Posted - 11/20/2003 :  20:24:37  Show Profile  Visit Merkin's Homepage  Reply with Quote
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
Go to Top of Page

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

Posted - 11/20/2003 :  20:54:01  Show Profile  Reply with Quote
That does work, but can you modify it to return as rows in a table?

DavidM

"SQL-3 is an abomination.."
Go to Top of Page

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

Posted - 11/20/2003 :  21:10:32  Show Profile  Visit Merkin's Homepage  Reply with Quote
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
Go to Top of Page

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

Posted - 11/20/2003 :  21:28:49  Show Profile  Reply with Quote
I was hoping somebody wouldn't use that!
http://www.math.hmc.edu/funfacts/ffiles/10002.4-5.shtml

Damn Google!!!


DavidM

"SQL-3 is an abomination.."
Go to Top of Page

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

Posted - 11/20/2003 :  21:32:00  Show Profile  Visit Merkin's Homepage  Reply with Quote
Yeah, it is cheating a little



Damian
Go to Top of Page

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

Posted - 11/20/2003 :  21:41:26  Show Profile  Reply with Quote
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.."
Go to Top of Page

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

Posted - 11/20/2003 :  21:48:17  Show Profile  Visit Merkin's Homepage  Reply with Quote
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
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 11/20/2003 :  21:52:49  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
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
Go to Top of Page

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

Posted - 11/20/2003 :  22:28:22  Show Profile  Reply with Quote
"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.."
Go to Top of Page

Merkin
Funky Drop Bear Fearing SQL Dude!

Australia
4970 Posts

Posted - 11/20/2003 :  22:35:26  Show Profile  Visit Merkin's Homepage  Reply with Quote
quote:


I really can't think of any non-iterative solution other than the formulae...



Oh sure. NOW you tell us



Damian
Go to Top of Page

byrmol
Shed Building SQL Farmer

Australia
1591 Posts

Posted - 11/20/2003 :  22:40:04  Show Profile  Reply with Quote
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.."
Go to Top of Page

Stoad
Freaky Yak Linguist

*
1983 Posts

Posted - 11/21/2003 :  15:10:26  Show Profile  Visit Stoad's Homepage  Reply with Quote
LOL.. few days ago I was going to propose the subject

but then decided on it as not much interesting.. Binet..
Go to Top of Page

jsmith8858
Dr. Cross Join

USA
7423 Posts

Posted - 11/21/2003 :  16:50:11  Show Profile  Visit jsmith8858's Homepage  Reply with Quote
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
Go to Top of Page

nr
SQLTeam MVY

United Kingdom
12543 Posts

Posted - 11/21/2003 :  17:09:21  Show Profile  Visit nr's Homepage  Reply with Quote
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.
Go to Top of Page

SamC
White Water Yakist

USA
3467 Posts

Posted - 11/21/2003 :  19:28:30  Show Profile  Reply with Quote
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
Go to Top of Page

nr
SQLTeam MVY

United Kingdom
12543 Posts

Posted - 11/21/2003 :  20:44:11  Show Profile  Visit nr's Homepage  Reply with Quote
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.
Go to Top of Page

ehorn
Flowing Fount of Yak Knowledge

USA
1631 Posts

Posted - 11/22/2003 :  00:03:27  Show Profile  Reply with Quote
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
Go to Top of Page

Stoad
Freaky Yak Linguist

*
1983 Posts

Posted - 11/22/2003 :  06:52:52  Show Profile  Visit Stoad's Homepage  Reply with Quote
LOL Jay.. it should be named as gessel-ehorn solution..
Go to Top of Page

JuniorFletch
Starting Member

USA
1 Posts

Posted - 07/05/2013 :  13:37:41  Show Profile  Reply with Quote
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

Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.12 seconds. Powered By: Snitz Forums 2000