Introduction
This tip shows two different ways of generating Fibonacci numbers in Oracle using a single SQL statement.
Fibonacci numbers are named after an Italian mathematician Leonardo Fibonacci. The Fibonacci number sequence starts typically with numbers 0 and 1 and the new number in the sequence is defined by adding two previous numbers. So as a formula
Fn = Fn-1 + Fn-2
For more information about Fibonacci numbers, see Fibonacci number.
This tip utilizes both CONNECT BY and CTE. Generating desired number of rows using these techniques is described in more detail in Generating desired amount of rows in Oracle using single statement.
Alternative 1: CONNECT BY
The first version is done using CONNECT BY clause. Since Fibonacci numbers are always based on the previous numbers in the sequence, one possibility would be to fetch the values from the previous rows in one way or another. However, I felt easiest not to try to reference the previous row with the CONNECT BY version. Instead I used Binet's formula to calculate the values. You can read more about the formula from Binet's Fibonacci Number Formula.
So the query to calculate Fibonacci numbers from F0 to F10 looks like
SELECT 'F' || TO_CHAR(Level - 1) AS FibonacciOrdinal,
( (POWER(1 + SQRT(5), Level - 1)
- POWER(1 - SQRT(5), Level - 1))
/ (POWER(2, Level - 1) * SQRT(5))) AS FibonacciNumber
FROM Dual d
CONNECT BY Level <= 11;
Running the query produces the following result
FibonacciOrdinal FibonacciNumber
---------------- ---------------
F0 0
F1 1
F2 1
F3 2
F4 3
F5 5
F6 8
F7 13
F8 21
F9 34
F10 55
As said, to understand the row generatior, please refer to Generating desired amount of rows in Oracle using single statement. Beyond that the rest of the query is basically just implemention of Binet's formula. One key thing to notice is the usage of Level pseudocolumn. The Level returns current depth of the recursion. Since Fibonacci numbers start from zero and the Level pseudocolumn starts to count from 1 I've deducted 1 from the value the formula uses.
Alternative 2: CTE
The second variation uses Common-Table Expression (CTE). The basic idea is now different from the CONNECT BY alternative. Since in CTE it's natural to reference the previous row this alternative just adds values from the previous rows. The query looks like this:
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
SELECT 1 AS RecursionLevel,
0 AS FibonacciNumber,
1 AS NextNumber
FROM Dual
UNION ALL
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel <= 10
)
SELECT 'F' || TO_CHAR( fn.RecursionLevel - 1 ) AS FibonacciOrdinal,
fn.FibonacciNumber,
fn.NextNumber
FROM FibonacciNumbers fn;
And the result is
FibonacciOrdinal FibonacciNumber NextNumber
---------------- --------------- ----------
F0 0 1
F1 1 1
F2 1 2
F3 2 3
F4 3 5
F5 5 8
F6 8 13
F7 13 21
F8 21 34
F9 34 55
F10 55 89
The FibonacciNumber and the NextNumber are separated into different columns. The column named FibonacciNumber is the actual number in the sequence while the NextNumber is the value to be added to the FibonacciNumber during the this cycle in recursion. So this number will be the Fibonacci number during the next round. The RecursionLevel column is only used as a visual aid in the result set so it has no part in the actual calculation.
Testing with larger amounts of rows
The obvious question is, what happens if we increase the amount of rows, how large values can be produced?
If you try different variations with the CONNECT BY version, you'll notice that F247 is the largest Fibonacci number until an error is generated. If you run the following query
SELECT 'F' || TO_CHAR(Level - 1) AS FibonacciOrdinal,
( (POWER(1 + SQRT(5), Level - 1)
- POWER(1 - SQRT(5), Level - 1))
/ (POWER(2, Level - 1) * SQRT(5))) AS FibonacciNumber
FROM Dual d
CONNECT BY Level <= 251;
You will receive an error
ORA-01426: numeric overflow
Okay, arithmetic overflow, but where? Actually it's the POWER function that is causing the problem as it's hitting the limit of NUMBER data type. The documentation for POWER explains that also BINARY_DOUBLE can be used in calculation so this should increase the amount of values returned but with the cost of accuracy in the result.
To test this you can run following query
SELECT 'F' || TO_CHAR(Level - 1) AS FibonacciOrdinal,
( (POWER( CAST(1 AS BINARY_DOUBLE) + SQRT(5), Level - 1)
- POWER( CAST(1 AS BINARY_DOUBLE) - SQRT(5), Level - 1))
/ (POWER( CAST(2 AS BINARY_DOUBLE), Level - 1) * SQRT(5))) AS FibonacciNumber
FROM Dual d
CONNECT BY Level <= 501;
This returns all the values, but as said, the accuracy is pretty bad.
What about the CTE version then? Lets try
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
SELECT 1 AS RecursionLevel,
0 AS FibonacciNumber,
1 AS NextNumber
FROM Dual
UNION ALL
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel <= 603
)
SELECT 'F' || TO_CHAR( fn.RecursionLevel - 1 ) AS FibonacciOrdinal,
fn.FibonacciNumber,
fn.NextNumber
FROM FibonacciNumbers fn;
This query runs just fine and as with the CONNECT BY version Fibonacci numbers till F603 can be calculated. One big difference is that since this version is just adding numbers and not raising them into a power, the accuracy is far better as we're using NUMBER data type all the time.
I've stated several times that there's difference in the accuracy. To investigate this a bit further let's compare the results using the following query
SELECT a.FibonacciOrdinal AS FibonacciOrdinal,
a.FibonacciNumber AS ConnectByResult,
b.FibonacciNumber AS CTEResult,
a.FibonacciNumber - b.FibonacciNumber AS Difference
FROM (SELECT 'F' || TO_CHAR(Level - 1) AS FibonacciOrdinal,
( (POWER( CAST(1 AS BINARY_DOUBLE) + SQRT(5), Level - 1)
- POWER(CAST(1 AS BINARY_DOUBLE) - SQRT(5), Level - 1))
/ (POWER(CAST(2 AS BINARY_DOUBLE), Level - 1) * SQRT(5))) AS FibonacciNumber
FROM Dual d
CONNECT BY Level <= 604) a,
(WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
SELECT 1 AS RecursionLevel,
0 AS FibonacciNumber,
1 AS NextNumber
FROM Dual
UNION ALL
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel <= 603
)
SELECT 'F' || TO_CHAR( fn.RecursionLevel - 1 ) AS FibonacciOrdinal,
fn.FibonacciNumber,
fn.NextNumber
FROM FibonacciNumbers fn) b
WHERE a.FibonacciOrdinal = b.FibonacciOrdinal;
What the query above does is that it uses both CTE and CONNECT BY versions as inline views. The outer SELECT just joins the results based on FibonacciOrdinal and calculates the difference between these results.
If you investigate the results, you'll notice that the values start to differ very quickly; As early as in F4. When going further in F72 the difference is already a whole number and in the end of the result it's huge. Excerpt from the result
FibonacciOrdinal ConnectByResult CTEResult Difference
---------------- --------------- --------- ----------
F0 0 0 0
F1 1 1 0
F2 1 1 0
F3 2 2 0
F4 3 3 4.44089209850063E-16
F5 5 5 8.88178419700125E-16
F6 8 8 1.77635683940025E-15
F7 13 13 1.77635683940025E-15
F8 21 21 3.5527136788005E-15
F9 34 34 7.105427357601E-15
F10 55 55 1.4210854715202E-14
...
F70 190392490709135 190392490709135 0.4375
F71 308061521170130 308061521170129 0.6875
F72 498454011879265 498454011879264 1.1875
F73 806515533049395 806515533049393 2
F74 1.30496954492866E15 1.30496954492866E15 3
F75 2.11148507797806E15 2.11148507797805E15 5.25
F76 3.41645462290672E15 3.41645462290671E15 8.5
F77 5.52793970088477E15 5.52793970088476E15 14
...
F600 1.10433070572954E125 1.10433070572952E125 2.2170241981385E111
F601 1.78684461669056E125 1.78684461669052E125 3.56978472581623E111
F602 2.89117532242011E125 2.89117532242005E125 5.86196228660349E111
F603 4.67801993911067E125 4.67801993911057E125 9.4693236937441E111
That's it this time. Happy querying :)
References
Some references:
History
- 6th Spetember, 2014: Tip created.
