Le PacBlog !

Salut les gars, moi c'est Robert, et je n'aime pas les mouches.

(Il me fallait une phrase d'intro, j'ai pas trouvé mieux...)

Bon aujourd'hui, c'est le deuxième exo de l'Euler challenge !

 http://projecteuler.net/index.php?section=problems

DISCLAIMER :

J'ai la flemme de m'inscrire sur le site, donc je ne prendrais même pas la peine de vérifier mes résultats

  By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

1) La méthode brutale

Il y a quelques temps, je découvrais la clause MODEL qui permet de faire de l'itératif à partir de 10g... et donc facilement des suites récurrentes.

Donc du coup, c'est tout simple :

SQL> SELECT sum(u)
  2  FROM (
  3       SELECT n, u
  4       FROM (
  5         SELECT 0 n, 0 U FROM DUAL
  6         UNION ALL SELECT 1 n, 1 U FROM DUAL
  7         ) t
  8       MODEL
  9        dimension by (n)
 10        measures (u)
 11        rules upsert
 12        iterate(33)
 13        (u[2+iteration_number] = u[1+iteration_number] + u[iteration_number])
 14  )
 15  WHERE mod(u, 2) = 0
 16  /

    SUM(U)
----------
  4613732

Passionnant, n'est ce pas... allez, on va rigoler un peu plus !

2) La méthode mathématique

Bon, faire la somme de trucs qui sont déjà définis en se sommant les uns les autres, ça sent l'astuce à plein nez, non ?

(J'ai toujours fait les maths à l'intuition, ce qui explique surement mon destin pitoyable...)

Première remarque :

Un+2 = Un+1 + Un

Pour que Un+2 soit pair, il faut que Un+1 et Un soient soit tous les deux pairs, soit tous les deux impairs.

Mais s'ils sont tous les deux pairs, tous les autres termes le sont... et ce n'est pas le cas.

Bref, regardez bien les termes de la suite :

0 1 1 2 3 5 8 13 21 34 ...

Un terme sur 3 est pair, et bien sûr il est la somme des deux termes impairs précédents.

=> Si on s'arrête au bon endroit, la somme des termes pairs est égale à la somme des termes impairs !

La proposition formelle P(p) :

Quel que soit p, somme(U3i, 0<= i <= p) = somme(Ui impairs, 0<=i<=3p)

La preuve :

P(0) vraie, disons-le (ça c'est de l'argument !)

Supposons p(n) vraie, qu'en est-il de p(n+1) ?

somme(U3i, 0<= i <= n+1) = somme(U3i, 0<= i <= n)  + U3(n+1)

                                                 = somme(U3i, 0<= i <= n)  + U3n+1 + U3n+2

                                                 = somme(Ui impairs, 0<= i <= 3n)  + U3n+1 + U3n+2

                                                 = somme(Ui impairs, 0<= i <= 3(n+1))

Ca, c'est fait... 

somme(U3i, 0<= i <= n) = somme(Ui, 0<= i <= 3n) / 2

Il ne reste plus qu'à calculer la "série" de Fibonacci !

Pour cela, deuxième remarque :

quand on somme des termes qui justement se définissent comme la somme des deux précédents, on doit avoir des chances de retomber sur un de ces termes, non ?

Ben on retombe pas tout à fait dessus, mais à un près...

Somme(Ui, 0<=i<=n) = Un+2 - 1

(La démo par récurrence est triviale, vous la ferez vous-même !)

Et du coup, le résultat (en utilisant la forme analytique de Fibonacci) : 

somme(U3i, 0<= i <= n) = (U3n+2 - 1) / 2 = ((((1 + sqrt(5)) / 2) ^ (3n+2) - ((1 - sqrt(5)) / 2) ^ (3n+2)) / sqrt(5) - 1) / 2

(Ok, c'est illisible...)

SQL> SELECT ((power((1+sqrt(5))/2, 35) - power((1-sqrt(5))/2, 35)) / sqrt(5) - 1) / 2 res
  2  FROM dual
  3  /

       RES
----------
   4613732

Bon ok, le U33, je l'ai cherché à tâtons et c'est laid, mais bon !

La récursivité pure SQL sous Oracle, c'est pas évident avant la 11g.
Souvent lors de petits défis entre amis, je me suis bien pris la tête, sans grands résultats.
... jusqu'aujourd'hui, où j'ai dépilé une importante tâche de mon énooooorme to-do list : me documenter sur la CLAUSE MODEL de 10g.

A vrai dire, je ne suis toujours pas sûr de ce qu'on peut en faire dans la vraie vie... mais en tous cas on peut bien rigoler avec !

1) La clause MODEL en quelques mots

S'appliquant sur le résultat d'un SELECT, elle permet de considérer le résultat comme un tableau (éventuellement multi-dimensionnel), et de faire joujou avec.
 

Pour avoir les détails, je vous renvoie vers l'excellent article de l'excellent Antoun qui est en fait une excellente traduction d'un non moins excellent Neerlandais dont j'ai oublié le très excellent nom (je me souviens juste qu'il fait plein de points au scrabble) :
http://antoun.developpez.com/oracle/model/

2) Les suites numériques !

Donc voilà moi ce que j'en ai retenu, c'est qu'on peut créer des nouvelles "cases" dans le "tableau", et ce de manière itérative en faisant référence aux cases précédentes.

Du coup, mon grand fantasme est réalisé : sortir la sutie de Fibonacci en "pur" SQL :

  SELECT n, u
  FROM (
    SELECT 0 n, 0 U FROM DUAL
    UNION ALL SELECT 1 n, 1 U FROM DUAL
    ) t
  MODEL
   dimension by (n)
   measures (u)
   rules upsert
   iterate(10)
   (u[2+iteration_number] = u[1+iteration_number] + u[iteration_number])

Petite explication pour ceux qui ont eu la flemme de suivre le lien :
- Le résultat du SELECT sans le MODEL, c'est le tableau initial.

- J'y mets n et U(n), j'y initialise les premiers éléments de la suite : U0 = 0, U1 = 1

- Dimension, c'est ce qui indexe le tableau : n, puisqu'on fait du U(n)

 
- Measures, ça doit lister toutes les grandeurs du tableau, ici juste U(n)

 
- Rules : c'est là que commencent les règles de calcul

- Upsert : c'est pour dire que si pour un n donné U(n) existe déjà dans le tableau, on le met à jour, sinon on crée une nouvelle ligne. On peut spécifier Update ou Upsert All (ce dernier étant un truc obscur, je le rajoute à ma to-do list)
Iterate(10) : ca dit que la règle qui va suivre, faudra l'appliquer 10 fois (en fait 11, parce qu'on commence à 0 je dirais)

 
- Et la dernière ligne, c'est la règle de calcul à appliquer. Ici c'est la définition de la récurrence : Un+2   =   Un+1   +   Un.

Tadaaaam !

         N          U
---------- ----------
         0          0
         1          1
         2          1
         3          2
         4          3
         5          5
         6          8
         7         13
         8         21
         9         34
        10         55
        11         89

12 rows selected.

(Va falloir que je change de froc, je me suis fait dessus)

3) Produit cumulatif

Je sais pas si ça se fait dans la vraie vie, mais parmi les nombreuses applications de la récursivité, il y a le produit cumulatif.

Et la requête MODEL, je sens qu'elle est encore plus grottesque que la version Exp(Sum(Ln(x))

Alors, un jeu de données :

SQL> CREATE TABLE testcumproduct
  2  (grp NUMBER,
  3   ratio NUMBER);

C'est parti !

SQL> select grp, ratio, rn, nb
  2  from (
  3    select grp, ratio, row_number() over(partition by grp order by null) rn, count(*) over(partition by grp) nb
  4    from testcumproduct
  5  ) t
  6  model
  7    return updated rows
  8    partition by (grp)
  9    dimension by (rn)
 10    measures(ratio, nb)
 11    rules upsert
 12    iterate (100) until (iteration_number = nb[1]-1)
 13    ( ratio[1] = ratio[1] * coalesce(1+ratio[2+iteration_number], 1) );

       GRP      RATIO         RN         NB
---------- ---------- ---------- ----------
         1      .3432          1          4
         0     1.0296          1          5

A noter que :
- j'ai multiplié par 1+ ratio, pour faire genre ce sont des taux
- La clause partition permet d'émuler le group by
- J'itère en mettant à jour la première ligne de chaque groupe
- La clause return updated rows permet de compléter l'émulation du group by
- J'aurais bien voulu mettre directement mon nb dans en paramètre d'itération, mais il veut pas...

Voilà voilà, encore un article complètement inutile, vous êtes bien sur le PacBlog !