Bonjour,
La question parait un peu simple au départ, voire sans intérêt mais au final ça la solution ne semble pas si évidente, il n'y a peu être pas de solution du tout finalement.
Voilà une spécification de calcul exact d'une moyenne entière approchée:
La donnée: on se donne un liste d'entier de longueur quelconque (pour comprendre l'intérêt du problème on peut considérer des listes extêment longues d'entiers), les entiers étant tous dans un inter val fini donné (par exemple les entiers représentables sur 32bit).
Le résultat attendu: la moyenne arithmétique exacte (M) (nombre rationnel en général) de tous ces entiers est un nombre qui au sens mathématique est borné par les mêmes bornes que l'interval dans lequel sont les entiers au départ, donc la partie entière (E) de la moyenne arithmétique se trouve dans le même interval que tous les entiers de la liste. Si M-E < .5 alors le résultat attendu est E sinon c'est E+1, et dans ce cas E+1 est aussi dans le même interval que les entiers de départ.
Pour calculer ça tout le monde connaît l'algo de base qui constitue la définition de la moyenne arithématique, qui consiste à additionner tous les entiers et à diviser la somme par le nombres d'entiers dans la liste.
En pratique le problème est que cette somme (entière) peut dépassée la capacité de représentions des entiers, et on ne peut pas utiliser les nombres flottants car ça va conduire à de grosses approximations dans la somme entière, et par la suite dans la division (on aurait alors plus un algorithme exact). on imagine utiliser une bibliothèque de grand nombre, mais on aurait d'impression de sortir l'artillerie lourde juste pour calculer un moyenne d'entiers qui au départ sont tous représentables sans problème avec les types de base.
Bref, en donnée on a une liste d'entiers tous représentables, le résultat est un entier représentable de la même manière.
On aurait tendance à se dire que c'est un problème simple et qu'il doit bien y avoir un algo simple et qui ne vas pas utiliser des ressources considérables.
Un exemple, supposons que vous vouliez calculer la moyenne de débit de votre connexion internet. Pour avoir une mesure précise vous mesurez votre débit toutes les secondes (en ayant un téléchargement en permanence par exemple et observant le nombre d'octets reçu chaque seconde) que vous obtenez en octets par secondes, comme vous allez avoir beaucoup de données vous essayez de limiter la ressource utilisée pour sauvegarder chaque mesure, en l'occurrence 11 bits par mesure en octet/s devrait suffire (ça permet d'aller jusqu'à 2048octets/s, ça semble suffisant pour une connexion perso). Pour avoir un bon aperçu vous faites cette mesure pendant 24h (ou plus), vous allez donc avoir 3600 mesures.
En fait avec une bonne connexion vous allez être proche de votre débit maxi en permanence (en tout cas vous l'espérez), disons que vous avez un bon abonnement fibre optique donc 1500 à peu près pour chaque mesure. Si vous voulez calculer la moyenne de manière habituelle vous allez calculer la somme de tout ça, pour arriver mathématiquement à quelque chose de l'ordre de 1500*3600*24=129600000, on dépasse donc évidemment très largement la borne de 2048 des entiers au départ (en fait les vieux ordinateurs 16bits seraient déjà en dépassement de capacité, alors qu'on n'est pas parti avec des nombres très grands).
C'est un petit exemple simple, imaginez si on part avec une mesure sur 32bits (au lieu des 11 bits pour atteindre 2048), on peut aller au delà des capacités de nos ordi moderne très rapidement. Et ça juste pour calculer une moyenne entière d'entier !
Bref, on se dit qu'il doit y avoir une solution simple sans avoir besoin de beaucoup de ressources, mais depuis quelque temps que je regarde ça en détail y'a toujours quelque chose qui coince dans les ressources nécessaires pour représenter les résultats intermédiaires du calcul.
Est-ce que quelqu'un à une idée? ou des liens qui expliquent que ce genre de problème n'a pas de solutions ?
Remarque: si vous cherchez sur le net vous trouverez plein de petits programme C de calcul de moyenne utilisant des float (ou des double car c'est bien connu les double ça règle tous les problèmes), il faut faire gaffe car si les nombres à virgules flottantes permettent de manipuler des nombres très grands et très petit, donc des nombres dans un interval très large, en fait cet interval contient énormément de trous, et donc quasi tous les calculs sont approchés (voir très approchés), donc les nombres à virgules flottantes ne sont en général pas du tout adapté à faire du calcul exact.*
Merci
-----
Envoyé par sitalgo 
