Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Any better Fibonacci series generator using pure Oracle SQL?

I wonder if there is any way to generate Fibonacci numbers that beat in simplicity and efficiency this one I wrote:

WITH d (seq) AS
       (SELECT     LEVEL
        FROM       DUAL
        CONNECT BY LEVEL < 195)
SELECT   seq
        ,fib
FROM     d
MODEL
  DIMENSION BY(seq)
  MEASURES(0 AS fib)
  RULES
    (fib [1] = 0,
    fib [2] = 1,
    fib [seq BETWEEN 3 AND 194] = fib[CV(seq) - 2] + fib[CV(seq) - 1],
    fib [seq > 194] = NULL)
ORDER BY 1
/
Execution Plan
----------------------------------------------------------
Plan hash value: 2245903385

---------------------------------------------------------------------------------------
| Id  | Operation                      | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |      |     1 |    13 |     2   (0)| 00:00:01 |
|   1 |  SQL MODEL ORDERED             |      |     1 |    13 |            |          |
|   2 |   VIEW                         |      |     1 |    13 |     2   (0)| 00:00:01 |
|*  3 |    CONNECT BY WITHOUT FILTERING|      |       |       |            |          |
|   4 |     FAST DUAL                  |      |     1 |       |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - filter(LEVEL<195)


Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          0  consistent gets
          0  physical reads
          0  redo size
       4798  bytes sent via SQL*Net to client
        500  bytes received via SQL*Net from client
         14  SQL*Net roundtrips to/from client
          1  sorts (memory)
          0  sorts (disk)
        194  rows processed

SQL>

Note: LEVEL < 195 was not arbitrarily chosen, higher values make the algorithm lose precision so I decided not to include them in order to keep correct results only.

like image 395
abrittaf Avatar asked Feb 04 '23 07:02

abrittaf


2 Answers

on the simplicity side of things, the query can rely on the built in features (ITERATE () and ITERATION_NUMBER) of MODEL:

select * from dual
model
  dimension by (0 seq)
  measures (0 val)
  rules iterate (195) 
  (
     val[iteration_number] = val[iteration_number-1] + val[iteration_number-2],
     val[2] = 1, 
     val[1] = 0, 
     val[0] = 0
  )
;
like image 147
Slkrasnodar Avatar answered Feb 07 '23 02:02

Slkrasnodar


You can use a recursive sub-query factoring clause:

WITH fib ( lvl, value, next ) AS (
  SELECT 1, 0, 1
  FROM DUAL
UNION ALL
  SELECT lvl + 1, next, value + next
  FROM fib
  WHERE lvl < 195
)
SELECT lvl, value FROM fib
like image 40
MT0 Avatar answered Feb 07 '23 02:02

MT0