Discussion :

[john_evrest]

Bonjour,
je dois écrire la fonction puissance en Caml sous une forme efficace (diviser pour régner) sachant que:

si b pair a^b = (x^(b/2))^2
si b impair a^b = x*(x^(b-1/2))^2

l’algorithme doit être récursif terminal. Et voila le problème, je n'arrive pas à le coder récursif terminal.

Je cherche désesperement depuis un petit moment sans trouver, si quelqu'un pourrait m'aider.
merci d'avance et bonne soirée

[kwariz]

Hello,

un algo récursif terminal pour l'algo naïf peut s'écrire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
Algo puissance_T(a : réel, n : entier, acc : réel) : réel
début
  si n = 0 alors
    retourner acc
  sinon
    acc := acc * a
    retourner puissance_T(a, n − 1, acc)
  fin si
fin
 
Algo puissance( a : réel, n : entier ) : réel
variables
  acc : réel
début
  si a = 0 alors
    retourner 0
  sinon
    acc := 1
    retourner puissance_T(a,n,acc)
  fin si
fin

Tu vois comment faire ?

[john_evrest]

Non toujours pas, j'arrive a trouver l'algo rapide non récursif terminal:

let puissance x y in
match y with
|0-> 1
|1 -> x
|e -> if pair e) then let (puissance x (y/2) )= c in
c*c
else let (puissance x ((y-1)/2) )= c in
x*c*c ;;

mais des que j'essai avec une fonction auxiliaire je me retrouve bloquer pour faire l'appel recursif et pour mémoriser le résultat dans la variable auxiliaire.

[gasche]

L'astuce est la suivante : au lieu de dire que, dans le cas où b est pair, on a :
a^b = (x^(b/2))^2
tu peux l'écrire
a^b = (x^2)^(b/2)

Il devient alors facile d'écrire ce cas de façon récursive terminale. Si tu veux aussi gérer le cas impair, il faut ajouter un accumulateur représentant un coefficient multiplicatif (dans lequel mettre le 'x' de 'x*c*c' dans ton implémentation).

Écrire cet algorithme de façon récursive terminale n'a aucun intérêt en pratique : comme le nombre d'appels récursifs est logarithmique en la puissance demandée, la pile d'appel croît de façon négligeable. Insister pour la récursivité terminale dans tous les cas nuit à la lisibilité et n'améliore pas les performances.

[TropMDR]

Écrire cet algorithme de façon récursive terminale n'a aucun intérêt en pratique : comme le nombre d'appels récursifs est logarithmique en la puissance demandée, la pile d'appel croît de façon négligeable. Insister pour la récursivité terminale dans tous les cas nuit à la lisibilité et n'améliore pas les performances.

Je ne suis pas d'accord. Prenons le micro-bench inutile suivant (spoileur, solution inside)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
let rec ntr_pow x y =
  if y = 0 then 1 else
  let xy2 = ntr_pow x (y / 2) in
  if y mod 2 = 1 then
    xy2 * xy2 * x
  else
    xy2 * xy2
 
 
let tr_pow x y =
  let rec aux xpow res y =
    if y = 0 then res else
    aux (xpow * xpow) 
      (if y mod 2 = 1 then res * xpow else res) (y / 2) in
  aux x 1 y
 
let nothing x y = x
 
let f = nothing
 
let _ = 
  for i = 1 to 10000000 do
    for j = 1 to 32 do
      let _ = f i j in
      ()
    done
  done

Pour f = nothing, on obtient
Real: 0.41s User: 0.41s System: 0.00s Percent: 99% Cmd: ./n_pow

Pour f = ntr_pow
Real: 19.28s User: 19.05s System: 0.02s Percent: 98% Cmd: ./ntr_pow

et pour f = tr_pow
Real: 14.54s User: 14.37s System: 0.02s Percent: 98% Cmd: ./tr_pow

Bien sûr, ce n'est pas énorme dans ce cas, mais 25% d'amélioration sur du code numérique, je ne peux pas qu'on puisse qualifier ça de négligeable ou d'inutile !

[kwariz]

En plus il me semble qu'un compilateur est en mesure de transformer un algo terminal en boucle ... enfin à confirmer.

[TropMDR]

En plus il me semble qu'un compilateur est en mesure de transformer un algo terminal en boucle ... enfin à confirmer.

C'est exactement l'intérêt de la récursion terminale: c'est transformé en boucle. L'avantage est double:

1. Tu ne risques pas de faire exploser la pile
2. Tu économises des appels de fonctions qui peuvent être couteux

Le premier est négligeable dans notre cas, puisque le nombre d'appel est effectivement logarithmique. En revanche, le second fait gagner 25% ici, ce qui n'est pas si mal.

[john_evrest]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
let tr_pow x y =
  let rec aux xpow res y =
    if y = 0 then res else
    aux (xpow * xpow) 
      (if y mod 2 = 1 then res * xpow else res) (y / 2) in
  aux x 1 y

merci beaucoup, c'est exactement ce que je cherchais.
Si je peut me permettre une derniére question, je vois bien que l’algorithme a une complexité en log (n) mais comment peut-on le prouver?

merci encore tropmdr.

[TropMDR]

Pffff, ça va exactement à l'encontre de ce que je disais dans un autre post... J'ai balancé la solution directement Désolé.

@john_evrest: déjà, je n'aurais absolument pas du te donner la solution, et je m'en veux assez pour ne pas me refaire avoir...

Es-tu sûr d'avoir compris mon algorithme ? Pourquoi est-il correct ? Que contiens chaque accumulateur à chaque appel de fonction ?

Et enfin, pourquoi termine-t-il ? Tu aurais sans doute la solution à ta question quand tu auras répondu à tout ça.

[gasche]

TropMDR > merci d'avoir pris l'effort de faire le test en pratique. Il faudrait toujours faire ça avant de parler de performances !

Bien sûr, ce n'est pas énorme dans ce cas, mais 25% d'amélioration sur du code numérique, je ne peux pas qu'on puisse qualifier ça de négligeable ou d'inutile !

Sur ma machine, on obtient le même gain en performance (en fait légèrement supérieur) en écrivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
let rec ntr_pow x = function
| 0 -> 1
| y ->
  let xy2 = ntr_pow x (y / 2) in
  if y mod 2 = 1 then
    xy2 * xy2 * x
  else
    xy2 * xy2

Bien sûr, ce sont deux optimisations indépendantes qui se combinent, et on peut obtenir un code encore plus de la mort en ayant une version récursive terminale avec ça, ou même en écrivant la fonction en C pour éviter les décalages de bits.

Maintenant, est-ce que c'est ce qu'on a envie d'apprendre aux gens ? Je suis d'accord avec ton optique "on fait un test dans ce cas précis et on prend ce qui est le plus rapide". Il n'empêche que pour moi il s'agit ici de différences de performances fragiles, peu justifiées (ok, il y a quelques spills de plus dans la version non-tail-rec), et équivalentes en terme de gains à de purs changements cosmétiques.

Je persiste à penser que pour cette fonction, demander une version tail-récursive n'a aucun intérêt. La tail-récursivité ce n'est pas une idole à satisfaire dans chaque fonction, et son utilisation dans un cadre d'enseignement doit se baser sur des raisons rationnelles, justifiées, à un niveau sémantique compréhensible par les élèves. On peut parler de consommation mémoire des appels et ça a du sens (même sans forcément aller jusqu'à la compilation, on peut le faire en parlant de la taille des contextes d'évaluation avec n'importe quelle présentation rigoureuse de la réduction). Ici il n'y a rien de sensé qui justifie de demander une fonction tail-rec.

PS: sur ma machine, avec le même code en faisant des calculs de nombres flottants, la version non tail-rec est systématiquement plus rapide, j'observe un gain de 10% environ. Je suppose que c'est parce que le compilateur optimise mieux le boxing dans `xy2 *. xy2 *. x`. Mais ça me semble une illustration assez caractéristique de la fragilité de ces considérations.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let rec ntr_pow x y =
  if y = 0 then 1. else
  let xy2 = ntr_pow x (y / 2) in
  if y mod 2 = 1 then
    xy2 *. xy2 *. x
  else
    xy2 *. xy2
 
let tr_pow x y =
  let rec aux xpow res y =
    if y = 0 then res else
    aux (xpow *. xpow) 
      (if y mod 2 = 1 then res *. xpow else res) (y / 2) in
  aux x 1. y

[TropMDR]

J'ai posté ma réponse sur un autre post:

http://www.developpez.net/forums/d11...c/#post6312262

(Il me semble que ce ne serait pas une mauvaise idée de déplacer les posts précédents )