Calcul du nombre d'or

Bonsoir à tous,

Cette année, je suis dispensé d'un cours d'informatique (enfin plutôt une introduction). Étant donné le premier chapitre (55 dias pour nous apprendre à utiliser cout et cin), j'ai décidé de prendre un peu d'avance et de m'attarder sur des exos.

Un des exercices me pose plutôt soucis. Voici l'énoncé :

Calculer les termes de la suite de Fibonacci jusqu’à ce que la différence entre deux valeurs calculées consécutives du nombre d'or soit inférieure à la précision e (la précision étant saisie au clavier)

Voilà ce que j'ai écrit

 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
28
29
30
31
32
33

//Calculer le nombre d'or à la précision saisie par l'utilisateur
        //Declaration de variables
    int e = 0; //Nombre de chiffres significatifs
    int j = 2; //Variable de boucle
    double diff = 0.; //Difference entre deux nombres d'or
    double k = 1.; //Décimale traduisant la précision
    double t = 0.; //Variable de stockage temporaire
    double nombreOrRef = 0., nombreOr2 = 0.; // Nombres d'or
        //Saisie par l'utilisateur
    std::cout << "Calcul du nombre d'or " << std::endl;
    std::cout << "Quelle precision souhaitez vous ? ";
    std::cin >> e; //On récupere le nombre de chiffres significatifs
        //Calcul de la précision en décimal
    for (int i = 1; i < e; i++)
    {
        k = k/10; //Pour chaque i, on divise par 10. Ex : si notre précision est de 3 -> on divise 3x par 10
    }
    nombreOrRef = fibonacci(2)/fibonacci(1); //On calcule notre premier nombre d'or (entre le premier et le deuxieme terme)
    do 
    {
        nombreOr2 = fibonacci(j+1)/fibonacci(j); //Calcul du nombre d'or suivant (j initialisé à 2 auparavant)
        diff = nombreOr2 - nombreOrRef; //On stocke la différence (entre le précédent et celui calculé)
        if (diff < 0) //On considère toujours la différence comme positive
        {
            diff = - diff;
        }
        t = nombreOrRef; 
        nombreOrRef = nombreOr2; // On assigne notre nombre calculé comme référence pour le prochaine
        j++; //On incrémente pour calculer le nombre d'or suivant
    }while(diff > k); //Tant que la différence est sup à la précision saisie
    std::cout.precision(e); 
    std::cout << "Nombre d'or avec precision souhaitee : " << t << std::endl;
    std::cout << "Nombre d'or avec precision souhaitee : " << nombreOrRef << std::endl;

Le soucis étant le suivant : 1,6180339887 selon Wikipedia. La machine me donne pour t & nombreOrRef respectivement (entre parenthèse à la main)

1 -> 1 et 2 (1)

2 -> 1,7 et 1,6 (1,6)

3 -> 1,62 et 1,62 (1,62)

4 -> 1,618 et 1,618 (1,618)

5 -> 1,6180 et 1,6181 (1,6180)

6 -> 1,61804 et 1,61803 (1,61803)

7 -> 1,618034 et 1,618034 (1,618034)

8 -> 1,6180341 et 1,6180340 (1,6180340)

9 -> 1,61803399 et 1,61803399 (1,61803399)

10 -> 1,618033988 et 1,618033989 (1,618033989)

Et ainsi de suite. Mes questions sont les suivantes :

• Aucune des deux listes de variable est 100% correcte. La deuxième semble plus plausible mais les précisions 1 et 5 ne le sont pas (la 1 je comprends encore mais la 5 ?).

• N'y a-t-il aucune méthode un peu plus élégante? Une piste? Car la j'ai envie de vomir sur mon code

Merci d'avance

Je t'avoue ne pas forcément comprendre ton problème.. Pour ce qui est de ton code, il est plutôt propre, merci pour la documentation très bien fait pour un forum ! Tu peux peut être économiser quelques variables mais c'est pas le sujet..

Essaie de réexpliquer ton problème

(les doubles n'ont pas une précision infinie et son codés en base 2).

Ksass`Peuk m'a grillé mais je vais essayer d'être un peu plus explicite.

Le type double du C ne permet pas de stocker n'importe quel nombre décimal, seulement les nombres de la forme $m \cdot 2^{-n}$ où $m$ et $n$ sont des entiers. Tu ne peux pas espérer faire des calculs exacts avec ça, surtout si tu plonges loin dans les décimales. Il te faut utiliser une bibliothèque d'arithmétique multi-précision, comme la MPFR.

Et encore, Dominux Carnufex, si c'était le seul problème, c'est à dire qu'on pouvait se garantir facilement que n'importe quel flottant représentait un réel issu d'un calcul avec la précision théorique de $10^{-16}$, ça serait formidable.

Je pensais qu'utiliser un double au lieu d'un float serait suffisant (du moins pour les 10 premières décimales). Je vais jeter un coup d’œil à cette bibliothèque (car j'en aurai peut-être besoin pour d'autres calculs).

En tous cas, merci pour vos aides!

Ce n'est pas le cas Kristof. Il y a une différence entre la représentabilité des réels en machines et la précision d'un résultat après calcul.

De part le fait que la mémoire est finie, tous les réels ne sont pas représentables par un nombre flottant. Ce que dit la précision c'est que toute quantité plus petite que celle-ci est considérée comme un zéro machine ou plus globalement comme non-pertinente (je n'évoque pas les dénormalisés).
Cependant, il ne faut pas croire que tous les nombres réels sont représentables s'ils ont une écriture décimale finie avant la précision des flottants. L'exemple typique serait $0.1$ qui n'est pas représentable par la norme IEEE754 et qui pourant admet un développement décimale finie à l'ordre $10^{-1}$.

Ainsi, rien qu'en affectant un réel à un flottant, on commet une erreur que l'on appelle erreur d'affectation. Cette erreur est multipliée et amplifiée à chaque opération (+,-,*,/) et on peut se retrouver avec des résultats après de simples calculs qui ne présentent qu'un ou deux chiffres en commun avec le calcul sur le corps des réels alors que pourtant la précision théorique est de $10^{-16}$.

C'est tout l'art du calcul numérique que de vérifier la stabilité des calculs effectués pour limiter ces propagations d'erreurs (et c'est un problème différent du conditionnement et de la stabilité numérique au sens des algorithmes - et par ailleurs, parfois, ces deux aspects peuvent être contradictoire : des opérations plus stables numériquement au point de vu mathématique peuvent conduire à des propagations d'erreur plus grande).
Rien que dans une simple somme des termes d'un vecteur, de grosses erreurs peuvent apparaître. Un algorithme pour corriger cela est donné par la Sommation de Kahan:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func kahan_sum(seq []float64) float64 {
  var sum float64 = 0
  var c float64 = 0
  for _, v := range seq {
    y := v - c
    t := sum + y
    c = (t - sum) - y
    sum = t
  }
  return sum
}

func sum(seq []float64) float64 {
  var sum float64 = 0
  for _, v := range seq {
    sum += v
  }
  return sum
}

Et voici un très bref rappel sur l'arithmétique flottante que j'ai écris pour un article sur les méthodes stochastiques de contrôle d'arrondis en virgule flottante pour la validité du calcul numérique (en cours de préparation):

Rappels d'arithmétique flottante

Soit $b$ la base de l'arithmétique dans laquelle nous travaillerons. Généralement, $b=2$ ou $b=16$ pour les unités de calculs. Alors, tout nombre $x\in \mathbb{R}$ est représenté par la machine de manière normalisée par un flottant $X$ de sorte que : $$X = \pm Mb^E$$ Avec $\frac{1}{b} \leq M < 1$ et $M$ la mantisse codée sur un nombre $n$ fixe de digits et $E$ l'exposant codé également sur un nombre fixe de digits.
On peut donc écrire $M$ en base $b$ : $\sum_{i=1}^n M_ib^{-i}, 0 \leq M_i < b$

A l'instar, on peut également décomposer $x$ en base $b$ : $$X = \pm mb^E$$ Avec cette fois une mantisse $m$ possédant un nombre (possiblement) illimité de chiffres.

On considère l'opération d'affectation ($\rightarrow$) : $x \rightarrow X, \forall x \in \mathbb{R}$. Alors, l'erreur relative d'affectation sera $\alpha = \frac{X - x}{X}$.

Si l'on pose $r = m - M$ le résidu, c'est à dire la partie perdue de la mantisse, on a $\alpha = \frac{-r}{M}$ avec un encadrement du résidu selon que l'on se trouve en arithmétique d'arrondi ou de troncature :

• $0 \leq r < \frac{1}{b^n}$ en arithmétique de troncature.
• $\frac{-1}{2b^n} \leq r < \frac{1}{2b^n}$ en arithmétique d'arrondi.