Today is friday and I like the twitter-hashtag #FibonacciFriday,
so I tweeted
Zeckendorfs theorem every positive integer is uniquely the sum of distinct nonconsecutive Fibonaccis http://en.wikipedia.org/wiki/Zeckendorf%27s_theorem#FibonacciFriday
— Matthias Rogel (@MatthiasRogel) 22. Mai 2015
Don’t be afraid of having a look at the wikipedia-site, the math is not complicated at all ( you don’t need more than adding natural numbers smaller than hundred ), nevertheless the theorem is nice from a mathematical point of view.
And there is also mentioned
… For any given positive integer, a representation that satisfies the conditions of Zeckendorf’s theorem can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage. …
After thinking a bit about it, I came to the idea to implement it solely in SQL which might show the strength of this language.
Here we go, we compute the Zeckendorf representations of the first 200 natural numbers in SQL.
If you are not familiar with the xmlquery-part of it, see what Tom Kyte learned from me
with n as ( /* the first 200 natural numbers */ select level as n from dual connect by level <= 200 ), f(n, a, b) as ( /* construct fibonaccis, 30 are surely enough ... */ select 1 as n, 1 as a, 1 as b from dual union all select n+1, b, a+b from f where n<=30 ) , fibonaccis as ( select f.a as f from f ), decomp(n, s) as ( /* here is the magic recursive subquery factoring */ select n.n, (select cast(max(fibonaccis.f) as varchar2(100)) from fibonaccis where fibonaccis.f <= n.n) from n union all select d.n, rtrim ( d.s || ' + ' || ( select cast(max(fibonaccis.f) as varchar2(10)) from fibonaccis where fibonaccis.f <= d.n - xmlquery(d.s returning content).getNumberVal() ), ' + ' ) from decomp d where d.s != rtrim ( d.s || ' + ' || ( select cast(max(fibonaccis.f) as varchar2(10)) from fibonaccis where fibonaccis.f <= d.n - xmlquery(d.s returning content).getNumberVal() ), ' + ' ) ) /* we only want "the last" decomp, the one with maximal length */ select decomp.n || ' = ' || min(decomp.s) keep(dense_rank first order by length(decomp.s) desc) as zeckendorf_representation from decomp group by decomp.n order by decomp.n / ZECKENDORF_REPRESENTATION ------------------------------------------------------------------------------------------------------------------------------------------------------------ 1 = 1 2 = 2 3 = 3 4 = 3 + 1 5 = 5 6 = 5 + 1 7 = 5 + 2 8 = 8 9 = 8 + 1 10 = 8 + 2 11 = 8 + 3 12 = 8 + 3 + 1 13 = 13 14 = 13 + 1 15 = 13 + 2 16 = 13 + 3 17 = 13 + 3 + 1 18 = 13 + 5 19 = 13 + 5 + 1 20 = 13 + 5 + 2 21 = 21 22 = 21 + 1 23 = 21 + 2 24 = 21 + 3 25 = 21 + 3 + 1 26 = 21 + 5 27 = 21 + 5 + 1 28 = 21 + 5 + 2 29 = 21 + 8 30 = 21 + 8 + 1 31 = 21 + 8 + 2 32 = 21 + 8 + 3 33 = 21 + 8 + 3 + 1 34 = 34 35 = 34 + 1 36 = 34 + 2 37 = 34 + 3 38 = 34 + 3 + 1 39 = 34 + 5 40 = 34 + 5 + 1 41 = 34 + 5 + 2 42 = 34 + 8 43 = 34 + 8 + 1 44 = 34 + 8 + 2 45 = 34 + 8 + 3 46 = 34 + 8 + 3 + 1 47 = 34 + 13 48 = 34 + 13 + 1 49 = 34 + 13 + 2 50 = 34 + 13 + 3 51 = 34 + 13 + 3 + 1 52 = 34 + 13 + 5 53 = 34 + 13 + 5 + 1 54 = 34 + 13 + 5 + 2 55 = 55 56 = 55 + 1 57 = 55 + 2 58 = 55 + 3 59 = 55 + 3 + 1 60 = 55 + 5 61 = 55 + 5 + 1 62 = 55 + 5 + 2 63 = 55 + 8 64 = 55 + 8 + 1 65 = 55 + 8 + 2 66 = 55 + 8 + 3 67 = 55 + 8 + 3 + 1 68 = 55 + 13 69 = 55 + 13 + 1 70 = 55 + 13 + 2 71 = 55 + 13 + 3 72 = 55 + 13 + 3 + 1 73 = 55 + 13 + 5 74 = 55 + 13 + 5 + 1 75 = 55 + 13 + 5 + 2 76 = 55 + 21 77 = 55 + 21 + 1 78 = 55 + 21 + 2 79 = 55 + 21 + 3 80 = 55 + 21 + 3 + 1 81 = 55 + 21 + 5 82 = 55 + 21 + 5 + 1 83 = 55 + 21 + 5 + 2 84 = 55 + 21 + 8 85 = 55 + 21 + 8 + 1 86 = 55 + 21 + 8 + 2 87 = 55 + 21 + 8 + 3 88 = 55 + 21 + 8 + 3 + 1 89 = 89 90 = 89 + 1 91 = 89 + 2 92 = 89 + 3 93 = 89 + 3 + 1 94 = 89 + 5 95 = 89 + 5 + 1 96 = 89 + 5 + 2 97 = 89 + 8 98 = 89 + 8 + 1 99 = 89 + 8 + 2 100 = 89 + 8 + 3 101 = 89 + 8 + 3 + 1 102 = 89 + 13 103 = 89 + 13 + 1 104 = 89 + 13 + 2 105 = 89 + 13 + 3 106 = 89 + 13 + 3 + 1 107 = 89 + 13 + 5 108 = 89 + 13 + 5 + 1 109 = 89 + 13 + 5 + 2 110 = 89 + 21 111 = 89 + 21 + 1 112 = 89 + 21 + 2 113 = 89 + 21 + 3 114 = 89 + 21 + 3 + 1 115 = 89 + 21 + 5 116 = 89 + 21 + 5 + 1 117 = 89 + 21 + 5 + 2 118 = 89 + 21 + 8 119 = 89 + 21 + 8 + 1 120 = 89 + 21 + 8 + 2 121 = 89 + 21 + 8 + 3 122 = 89 + 21 + 8 + 3 + 1 123 = 89 + 34 124 = 89 + 34 + 1 125 = 89 + 34 + 2 126 = 89 + 34 + 3 127 = 89 + 34 + 3 + 1 128 = 89 + 34 + 5 129 = 89 + 34 + 5 + 1 130 = 89 + 34 + 5 + 2 131 = 89 + 34 + 8 132 = 89 + 34 + 8 + 1 133 = 89 + 34 + 8 + 2 134 = 89 + 34 + 8 + 3 135 = 89 + 34 + 8 + 3 + 1 136 = 89 + 34 + 13 137 = 89 + 34 + 13 + 1 138 = 89 + 34 + 13 + 2 139 = 89 + 34 + 13 + 3 140 = 89 + 34 + 13 + 3 + 1 141 = 89 + 34 + 13 + 5 142 = 89 + 34 + 13 + 5 + 1 143 = 89 + 34 + 13 + 5 + 2 144 = 144 145 = 144 + 1 146 = 144 + 2 147 = 144 + 3 148 = 144 + 3 + 1 149 = 144 + 5 150 = 144 + 5 + 1 151 = 144 + 5 + 2 152 = 144 + 8 153 = 144 + 8 + 1 154 = 144 + 8 + 2 155 = 144 + 8 + 3 156 = 144 + 8 + 3 + 1 157 = 144 + 13 158 = 144 + 13 + 1 159 = 144 + 13 + 2 160 = 144 + 13 + 3 161 = 144 + 13 + 3 + 1 162 = 144 + 13 + 5 163 = 144 + 13 + 5 + 1 164 = 144 + 13 + 5 + 2 165 = 144 + 21 166 = 144 + 21 + 1 167 = 144 + 21 + 2 168 = 144 + 21 + 3 169 = 144 + 21 + 3 + 1 170 = 144 + 21 + 5 171 = 144 + 21 + 5 + 1 172 = 144 + 21 + 5 + 2 173 = 144 + 21 + 8 174 = 144 + 21 + 8 + 1 175 = 144 + 21 + 8 + 2 176 = 144 + 21 + 8 + 3 177 = 144 + 21 + 8 + 3 + 1 178 = 144 + 34 179 = 144 + 34 + 1 180 = 144 + 34 + 2 181 = 144 + 34 + 3 182 = 144 + 34 + 3 + 1 183 = 144 + 34 + 5 184 = 144 + 34 + 5 + 1 185 = 144 + 34 + 5 + 2 186 = 144 + 34 + 8 187 = 144 + 34 + 8 + 1 188 = 144 + 34 + 8 + 2 189 = 144 + 34 + 8 + 3 190 = 144 + 34 + 8 + 3 + 1 191 = 144 + 34 + 13 192 = 144 + 34 + 13 + 1 193 = 144 + 34 + 13 + 2 194 = 144 + 34 + 13 + 3 195 = 144 + 34 + 13 + 3 + 1 196 = 144 + 34 + 13 + 5 197 = 144 + 34 + 13 + 5 + 1 198 = 144 + 34 + 13 + 5 + 2 199 = 144 + 55 200 = 144 + 55 + 1 200 rows selected. Elapsed: 00:01:28.71
Sokrates on Oracle
Hi Matthias.
This is really cool!
Encouraged by your post, I wrote another version of this query, using 12c Pattern Matching (with your “Fibonacci generator”).
The elapsed time (for the same population of the first 200 natural numbers) is now less than 0.1 second.
with
f(n, a, b) as
(
/* construct fibonaccis, 30 are surely enough … */
select 1 as n, 1 as a, 1 as b
from dual
union all
select n+1, b, a+b
from f
where n<=30
)
select n.n || ' = ' ||
(select listagg(f,' + ') within group (order by f desc)
from (select n.n,f.a as f from f)
match_recognize(
order by f desc
measures classifier() cls
all rows per match
pattern(A (A|B)*)
define A as sum(A.f) <= n)
where cls='A') zeckendorf_representation
from (select level as n from dual connect by level <= 200) n;
Thanks,
Oren.
Hi Oren,
fantastic !
Didn’t know how cool pattern matching really can be !
Thanks Matthias
Nice post and great reply! Here is a slight variation on the reply:
1. Generate just enough fibonacci numbers to get to 200, by stopping when f(n) + f(n-2) is greater than 200
2. Join n and f such that f is never greater than n.
(The combination of 1. and 2. reduces the number of input rows from 6000 to 1836.)
3. Instead of running a subquery for each n, run one query using “partition by n” and “group by n”.
4. Instead of “where cls = ‘A'”, use the “exclusion syntax {- -}” in the PATTERN clause.
5. Without the WHERE clause, no need for the MEASURES clause.
with n as (
select level as n
from dual
connect by level <= 200
)
,f(b,f) as (
select 1 as b, 1 as f
from dual
union all
select f, b+f
from f
where 2*b+f = f
)
select n, listagg(f,’+’) within group(order by f desc) z_r
from candidates
match_recognize(
partition by n order by f desc
all rows per match
pattern((A|{-B-})+)
define A as sum(A.f) <= n
)
group by n;
To me, Oren's use of (A|B)* to implement the greedy algorithm was the fundamental insight that allowed for use of MATCH_RECOGNIZE. Hats off to you both!
Stew, thanks for commenting, I appreciate it very much from the guru of pattern matching !
Seems that your SQL has one or two typos in it, I assume
with n as ( select level as n from dual connect by level <= 200 ) ,f(b,f) as ( select 1 as b, 1 as f from dual union all select f, b+f from f where 2*b+f <= 200 ), candidates as ( select n.n, f.f from n, f where n.n >= f.f ) select n || ' = ' || listagg(f,' + ') within group(order by f desc) z_r from candidates match_recognize( partition by n order by f desc all rows per match pattern((A|{-B-})+) define A as sum(A.f) <= n ) group by nwas meant.
Wow, I don’t know what happened with the copy and paste there! The “candidates” subquery was NOT left as an exercise for the reader, at least not deliberately. Thanks for correcting. Also, I’ll have to remember that [ code ] can be used in comments on WordPress.
Best regards, Stew
Pingback: ODC Appreciation Day : Pattern Matching in SQL - @DBoriented