Discussion :

[klandah]

Bonjour,

J'ai une liste de nombres ordonnés de manière croissante. Je voudrais pouvoir générer, à tout moment, un nombre entre deux nombres successifs de cette liste.

Exemple:

J'ai: 1 - 4 - 5 - 6 - 13.7 - 18 ...
Pour simplifier, on va dire que je veux générer un nombre entre 5 et 6, je fais (5+6)/2 = 5.5 et je l'insère à la bonne position (liste triée) en utilisant n'importe quel algo (exemple recherche binaire/dichotomique).
J'aurai: 1 - 4 - 5 - 5.5 - 6 - 13.7 - 18 ...

Cependant, en générant des nombres comme ça, on peut arriver à un moment où on ne peux plus générer de nombres entre deux nombres donnés et on aura un dépassement de capacité à cause de la précision des types (float, double etc selon les langages de programmation). Je parle donc d'un problème de précision des flottants.

Avez vous une solution/algo pour éviter ce-là ? Serait il par exemple possible de coder ces nombres en chaines de caractères au lieu de nombre réels (e.g. double) ? Toute proposition est la bienvenue.

Merci d'avance.

[Acrim]

Il existe des types de variables dont la précision n'a pas de limite. Tu trouveras des infos là : Arbitrary-precision arithmetic (j'ai aussi trouvé ce document sur le sujet Arithmétique en précision arbitraire ).

Si tu veux mettre en place ton propre type, au niveau arithmétique tu as peu de chose à prendre en compte : l'addition et la division par 2 (qui n'est qu'un décalage de bit).

[souviron34]

on aura un dépassement de capacité à cause de la précision des types (float, double etc selon les langages de programmation).

Alors avant de se lancer dans des grands trucs, d'utiliser tout un tas de biblothèques ou de se triturer les cheveux pour se faire un algo perso, le tout est de bien poser le problème :

• Que représentent ces nombres ?
• Qu'entends-tu par "infini" ?
• Qu'entends-tu par pécision ?

Est-ce une précision absolue, une précision relative ?
Dans le cas dune précision absolue, cela a-t-il un sens pour les éléments de ton tableau d'être simultanément comparés ?

[pseudocode]

Et j'ajouterais une question :

- Quelle est la problématique de départ qui t'a conduit à vouloir "générer, à tout moment, un nombre entre deux nombres successifs de cette liste." ?

[FR119492]

Salut!
Je pense que tu devrais commencer par regarder la norme ISO 754.
Jean-Marc Blanc

[edfed]

il est aussi possible de coder les nombres sous forme fractionelle. ce qui rend la demarche finale d'interpolation beaucoup plus precise et facile.

donc, au lieu de coder chaque element sur un reel, il faut le coder sur deux entiers.

et donc, lorsque l'on va additionner deux valeurs concecutives, on va chercher le plus petit denominateur commun des deux fractions. puis additionner les numerateurs.

au final, si l'on à disons:

Code :

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

1
2
3
4
 
1:1
5:1
19:1

la creation d'une donnée entre 1:1 et 5:1, et 5:1 et 19:1 donnera

Code :

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

1
2
3
4
5
6
 
1:1
6:2
5:1
24:2
19:1

si on continue

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
 
1:1
8:4
6:2
5:1
34:4
24:2
62:4
19:1
 
et comme en plus, on peut simplifier
 
1:1
2:1
3:1
5:1
17:2
12:1
31:2
19:1

on ne perd pas en precision, et les nombres du style 3,33333 serons simplement representés par la fraction 10:3

et si en plus, on desire afficher le nombre sous la forme 3,3333, ça reste possible grace à la fpu et la conversion flottant vers BCD.
mais c'est aussi possible en virgule fixe.

[Acrim]

donc, au lieu de coder chaque element sur un reel, il faut le coder sur deux entiers.

et donc, lorsque l'on va additionner deux valeurs concecutives, on va chercher le plus petit denominateur commun des deux fractions. puis additionner les numerateurs.

Puisqu'il ne fait que des divisions par deux, on pourrait même s'amuser à coder uniquement le ln_2 du dénominateur ?

Ce qui est bien sur ce forum c'est qu'il y a toujours des points de vue très variés