Pchełki SQL, odcinek 10: Fibonacci

https://xpil.eu/fneQW 📋

I jeszcze jedna pchełka SQL związana z numerkami. Tym razem zamiast rzucać się na wielkie problemy (typu liczby pierwsze), zajmiemy się wyliczaniem kolejnych elementów ciągu Fibonacciego.

Dla niezorientowanych przypomnę: ciąg Fibonacciego definiujemy jako nieskończony ciąg liczb naturalnych, z których dwie pierwsze to 0 i 1 a każda następna jest sumą dwóch poprzednich.

W zapisie formalnym:
\(a_n=1\) dla n<=2

\(a_n=a_{n-2}+a_{n-1}\) dla n>2

Kilka początkowych wyrazów:

0,1,1,2,3,5,8,13,21,34,55,89,...

Spróbujemy teraz wyliczyć kilka początkowych elementów tego ciągu za pomocą SQL. Ponownie, przypominam, że język ten nie nadaje się za bardzo do przeprowadzania obliczeń numerycznych (o wiele wydajniej da się takie rzeczy wyliczać w czymś niskopoziomowym, na przykład C#, a dla twardzieli w asemblerze), ale ponieważ to mój blog, będę tutaj za pomocą SQL-a robił dużo bardziej karkołomne rzeczy niż jakieś tam ciągi liczbowe.

No to lecimy. Najpierw - tradycyjnie - kod:

WITH fb as (
  SELECT  1 n, CAST(0 as bigint) f, CAST(1 as bigint) f1
  UNION ALL
  SELECT  n + 1, f + f1 f, f f1 FROM fb WHERE n < 93
)
SELECT  n, f FROM fb;

Teraz kilka słów wyjaśnienia:

with fb as ...

To podzapytanie ma dwa elementy: pierwszy blok SELECT definiuje dwa pierwsze elementy ciągu (a więc 0 i 1), kolejny (ten po UNION ALL) wylicza kolejne elementy - aż do elementu numer 93, który wynosi 7540113804746346429, i który jest największą liczbą Fibonacciego "mieszczącą się" w typie bigint (jeżeli nie użyjemy tego ograniczenia, SQL wygeneruje pierwsze 93 rekordy po czym kucnie z komunikatem błędu).

Ostatnie zapytanie prezentuje wyliczone elementy.

Tymczasem, borem - lasem.

Dopisane 25 kwietnia 2013: ten sam kod uruchomiony na Oracle (oczywiście z niezbędnym ozdobnikiem FROM DUAL oraz z podmianą BIGINT na NUMBER) pozwala na wyliczenie aż 605 pierwszych wyrazów ciągu Fibonacciego. Ostatni wyraz, który mieści się w typie NUMBER jest równy: 756 919 526 153 062 141 627 096 571 973 853 690 638 200 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

https://xpil.eu/fneQW 📋