# Fibonacci Numbers With a SQL query

Is it possible to generate a fibonacci sequence with a single SQL query?
###### Who is Participating?

RetiredCommented:
Binets formula. http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

A single statement using a derived table - but it's limited to the first 72 digits before rounding errors cause errors.

select cast (
floor((power((cast(1 as decimal(30,0))+sqrt(cast(5 as decimal(30,0)))),id)-
power((cast(1 as decimal(30,0))-sqrt(cast(5 as decimal(30,0)))),id))/
(power(cast(2 as decimal(30,0)),id)*sqrt(cast(5 as decimal(30,0)))))
as decimal(30,0)) fn
FROM
(
select top 72 cast((a0.id + a1.id) as decimal(30,0)) id FROM
(select 0 id union select 1 union select 2 union select 3 union select 4 union
select 5 union select 6 union select 7 union select 8 union select 9) a0,
(select 0 id union select 10 union select 20 union select 30 union select 40 union
select 50 union select 60 union select 70 union select 80 union  select 90) a1
) Numbers
0

Commented:
Yes, in any database that supports Stored Procedures or User-Defined Functions.

Which database are you using, and do you need one number per row, or in a comma delimited list?
0

Commented:
This works in SQL Server.

drop table a
create table a(a int, b int)
insert a values (1, 1)
insert a values (2, 1)
-- repeat this next statement as many times as you want...
insert a select max(a)+1, sum(b) from a where a>(select max(a) from a)-2
-- get your results with this statement
select * from a

A few syntax changes might be needed for oracle ("insert into a" instead of "insert a" - I do not have Oracle on my machine so I cannot test it right now)
0

CIOCommented:
I guess it would be fastest to generate a fixed lookup table from an external function:

I brushed up some VB(A) code in the archive. It don't use recursion as often seen (which is _extremely_ slow for anything more than a handful of elements); instead it fills a simple array (very fast):

Public Function FibonacciElementDec( _
ByVal lngElements As Long) _
As Variant

' Returns the value of element lngElements in the
' Fibonacci sequence of numbers.
' Max. number returned:
'   50095301248058391139327916261
'
' 2004-10-03. Gustav Brock, Cactus Data, CPH.

Const clngIndexMin  As Long = 0
Const clngIndexMax  As Long = 139

Dim decValue        As Variant

If lngElements < clngIndexMin Or lngElements > clngIndexMax Then
' Not a valid input. Return error.
decValue = CDec(-1)
Else
' Return last number in sequence in array.
decValue = FibonacciSequenceDec(lngElements)(lngElements)
End If

FibonacciElementDec = decValue

End Function

Public Function FibonacciSequenceDec( _
ByVal lngElements As Long) _
As Variant()

' Build and return array with Fibonacci sequence of numbers.
' Count of elements is determined by lngElements.
' Max. number returned in array:
'   50095301248058391139327916261
'
' 2004-10-03. Gustav Brock, Cactus Data, CPH.

' Min. index of sequence per definition.
Const clngIndexMin  As Long = 0
' Max. possible index of sequence for datatype Decimal.
Const clngIndexMax  As Long = 139

Dim adecSeq()       As Variant
Dim lngIndex        As Long

If lngElements < clngIndexMin Or lngElements > clngIndexMax Then
' Not a valid input.
Else
' Build and fill array with the Fibonacci sequence of numbers.
ReDim adecSeq(clngIndexMin To lngElements)
For lngIndex = clngIndexMin To lngElements
If lngIndex < 2 Then
' Values of the first two elements are 0 and 1 per definition.
Else
' Value is the sum of the two preceding numbers.
End If
Next
End If

End Function

You can create a simple loop - using either the array from the last function or just repetitive calls of the first function, speed is so fast that you hardly can tell the difference - to insert the index and the value in two fields of the table.
Note that the first element (index zero) is zero.

If you need more than 139 elements I have the equivalent functions for datatype Double but note that you will loose absolute accuracy for element index 76 and beyond.

/gustav
0

Commented:
I reread the question - to be accurate - as far as I know, unless you use a SQL Programming language like TSQL or PL/SQL, it is not possible to create a query that recurses and generates rows without some underlying data. As a result, it is technically impossible to generate the sequence with a SINGLE SQL (pure) statement without using some kind of driver table (a table that has enough rows to drive the creation of new records).  Of couse any table with a couple of hundred or so rows will do for this - including data dictionary tables like sysobjects.  Once you get into the programming languages, you could program it as easily as you would with VB, just using variables (why bother with a table if you are going to generate a few hundred rows based on a simple algorithm?)

A nice weekend challenge though...

0

Author Commented:
Wow, that's very cool. I don't mind using derived tables. I'm already using one. Actually, I just used the term fibonacci numbers because everyone knows what it is. My aplication doesn't actually use fibonacci numbers, but the idea is almost identical. Basically I have a stack and I want add the numbers up so that it follows a similar fibonacci recurrance relation. So the ith index in the stack equals the sum of the digits from zeroth to (i-1)th indices.
0

RetiredCommented:
In that case it's probably better just to create a permanent table of integers to join against for you nth index lookups

Select top 1000000 id = identity(int,1,1) Into Numbers from sysobjects s1, sysobjects s1, sysobjects s1, sysobjects s1

In general, an actual table as opposed to a derived table will perform better once you get above a few thousand rows because statistics are kept for a real table and derived tables will be converted to unindexed work tables at some point.

What exactly is your algorithm? We may be able to optimize it.
0

Author Commented:
This goes beyond the scope of the question. If you'd like to email me, drop me a line at rcdetert at nospam ucdavis edu and I'll tell you exactly what I'm doing.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.