Solved

Fibonacci Numbers With a SQL query

Posted on 2004-10-01
8
357 Views
Last Modified: 2008-02-01
Is it possible to generate a fibonacci sequence with a single SQL query?
0
Comment
Question by:dignified
  • 2
  • 2
  • 2
  • +2
8 Comments
 
LVL 15

Expert Comment

by:jdlambert1
ID: 12205580
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
 
LVL 10

Expert Comment

by:AaronAbend
ID: 12205884
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
 
LVL 49

Expert Comment

by:Gustav Brock
ID: 12211157
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.
        adecSeq(lngIndex) = CDec(lngIndex)
      Else
        ' Value is the sum of the two preceding numbers.
        adecSeq(lngIndex) = CDec(adecSeq(lngIndex - 2)) + CDec(adecSeq(lngIndex - 1))
      End If
''      Debug.Print adecSeq(lngIndex);
    Next
  End If
 
  FibonacciSequenceDec = adecSeq()

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
 
LVL 10

Expert Comment

by:AaronAbend
ID: 12211516
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
Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

 
LVL 12

Accepted Solution

by:
kselvia earned 250 total points
ID: 12214642
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
 

Author Comment

by:dignified
ID: 12234236
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
 
LVL 12

Expert Comment

by:kselvia
ID: 12234319
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 Comment

by:dignified
ID: 12234585
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

Featured Post

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Introduction: I have seen many questions on EE and elsewhere, asking about how to find either gaps in lists of numbers (id field, usually) ranges of values or dates overlapping date ranges combined date ranges I thought it would be a good …
APEX (Application Express) is used to develop a web application from Oracle. SQL Workshop is one of the tools that comes with Oracle APEX to query or modify the database objects or to make any changes to the structure.
Video by: Steve
Using examples as well as descriptions, step through each of the common simple join types, explaining differences in syntax, differences in expected outputs and showing how the queries run along with the actual outputs based upon a simple set of dem…
Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now