algorithme exact de calcul de moyenne
Répondre à la discussion
Affichage des résultats 1 à 16 sur 16

algorithme exact de calcul de moyenne



  1. #1
    inviteea95960a

    algorithme exact de calcul de moyenne


    ------

    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

    -----

  2. #2
    whoami

    Re : algorithme exact de calcul de moyenne

    Bonjour,

    Il faut utiliser - ou développer - une bibliothèque de calcul multi-précision, qui permet d'utiliser des nombres de taille quelconque.

    En C, la plus connue est GMP.

  3. #3
    lou_ibmix_xi

    Re : algorithme exact de calcul de moyenne

    Ou bien utiliser un type de plus grande dynamique pour le cumulant, par exemple un cumulant sur 64bits pour des données d'entrées de 32 bits laisse quand même pas mal de marge avant d'avoir un dépassement de dynamique: il faudrait avoir 2^31 valeurs à la valeur max (ou min)...

  4. #4
    sitalgo

    Re : algorithme exact de calcul de moyenne

    B'jour,

    J'ai ça mais il faut des flottants.

    La valeur de calcul est à peine supérieure à la moyenne calculée.
    Mais si t'as l'gosier, Qu'une armure d'acier, Matelasse. Brassens, Le bistrot.

  5. A voir en vidéo sur Futura
  6. #5
    whoami

    Re : algorithme exact de calcul de moyenne

    Bonjour,
    Citation Envoyé par sitalgo Voir le message
    J'ai ça mais il faut des flottants.
    La question précise "la valeur exacte", ce qui élimine tout calcul avec des flottants.

  7. #6
    inviteea95960a

    Re : algorithme exact de calcul de moyenne

    Citation Envoyé par whoami Voir le message
    Il faut utiliser - ou développer - une bibliothèque de calcul multi-précision, qui permet d'utiliser des nombres de taille quelconque.
    C'est ce dont je parlais quand je parlais de «bibliothèque de grand nombre», et ça me semble sortir l'arme de destruction massive pour se débarrasser d'un moustique, et on finira pas utiliser énormément de ressources.

    Sinon pour l'autre réponse, effectivement l'utilisation des nombre à virgule flottante est totalement exclu par nécessité de faire une calcul exact. Le problème ici est vraiment informatique et pas mathématiques. On peut trouver pleins de formules de math qui vont nous permettre de n'avoir à mémoriser et manipuler que peu de nombres, le problème est que la représentation de ces nombres n'est elle pas bornée (en tout cas dans tout ce que j'ai trouvé par moi-même) et grossira avec la longueur de la liste.

    Pour se rendre compte du problème, il faut imaginer qu'au lieu de programmer un logiciel sur un ordinateur on est en train de mettre au point un circuit électronique, on peut y mettre dessus une mémoire de la taille qu'on veut (mais pour des raisons évidentes il ne faudrait qu'elle soit trop énorme) mais une fois le circuit fabriqué cette mémoire ne pourra plus augmenter (c'est la même chose qui se passe avec un ordinateur mais dans d'autres proportions car si on manque de mémoire vive on peut aller (au pire) chercher de la mémoire sur disque dur).

    L'idéal serait effectivement comme dans la tentative de sitalgo d'avoir un algo qui puisse prendre les entiers un par un et ne mémoriser qu'un petit nombre d'information à la fois.

    Pour lou_ibmix_xi: c'est ce qu'on fait le plus souvent (via des bibliothèque de manipulation de grands nombre si nécessaire) car compte tenu des entrées on est souvent capable de borner la taille des informations qu'on va manipulé. Mais dans le cas général que j'ai pris, la liste d'entier peut-être arbitrairement longue, et ce qui est intéressant est le cas où elle sera extrêmement longue.

    En fait si on pose au départ que la liste d'entier peut être très longue mais de longueur fixée connue à l'avance alors on peut faire une estimation au pire des ressources nécessaires et se débrouiller comme ça. En revanche si on veut faire un calcul de la moyenne « au fur et à mesure », sur une liste dont la longueur n'est pas connue d'avance là je ne sais pas comment on peut faire (Imaginons dans l'exemple qu'au lieu de mesurer le débit sur une période donnée, on souhaite avoir un indicateur présent en permanence à l'écran qui nous donne le débit moyen depuis que l'interface réseau a été démarrée... je suis pas sûr que ça eit un grand intérêt mais c'est juste pour l'exemple)

    Ici la question que je pose est évidemment plus de l'algorithmique générale.

    Mon impression avec les différents essais j'ai fait c'est que si en mathématiques les données manipulées restent bornées, elle le sont en fait pas en informatique: considérons par exemple l'erreur arithmétique commise entre la valeur mathématique exacte de la moyenne (nombre rationnel), et la valeur entière approchée de cette moyenne. En mathématique cette erreur est bornée entre -0,5 et 0,5. Mais en informatique sa représentation n'est pas du tout bornée, ca il y a une infinité de nombres dans cet intervalle, et ils ne sont donc pas représentables en totalité par une représentation bornée.

    Comme je le disais je ne suis pas persuadé que ce genre de problème extrêmement simple en mathématiques ai une solution simple en informatique, mais au fond je n'en sais rien.

  8. #7
    sitalgo

    Re : algorithme exact de calcul de moyenne

    C'est juste histoire de rectifier une omission.
    Mais si t'as l'gosier, Qu'une armure d'acier, Matelasse. Brassens, Le bistrot.

  9. #8
    lou_ibmix_xi

    Re : algorithme exact de calcul de moyenne

    Citation Envoyé par lou_ibmix_xi Voir le message
    Ou bien utiliser un type de plus grande dynamique pour le cumulant, par exemple un cumulant sur 64bits pour des données d'entrées de 32 bits laisse quand même pas mal de marge avant d'avoir un dépassement de dynamique: il faudrait avoir 2^31 valeurs à la valeur max (ou min)...
    et puis l'arrondi c'est tout simple:
    Code:
    arrondi = 2 *(cum % nb) >= cum ? 1 : 0;
    Ou alors il y a quelque chose qui m'échappe...

  10. #9
    inviteea95960a

    Re : algorithme exact de calcul de moyenne

    Je n'ai pas vérifié si le calcul de l'arrondi est correct on non car ce n'est pas le problème d'obtenir les formules, mais comment faire un calcul qui restera exact quel que soit la longueur de la liste.

    Utiliser du 64 bits pour des entiers 32bits ça va un moment mais si la liste est très longue ça ne suffit plus.

    Encore une fois ce n'est pas un problème très concret (a-t-on vraiment besoin d'un algo qui fonctionne pour une longueur de liste quelconque ? en pratique on ne fait pas des moyennes sur des listes quasi-infinies) mais plus théorique.

    Si c'est possible d'avoir un algo qui peut utiliser une quantité bornée de ressources dès le départ quelle que soit la longueur de la liste, j'aimerais bien le connaître. Sinon j'aimerais bien savoir comment on prouve qu'un tel algo n'existe pas !

    En fait les formules mathématiques usuelles qui ont été évoquées précédemment utilisent toutes la longueur de la liste d'une manière ou d'une autre, de façon plus ou moins directe. Cette longueur pouvant être arbitrairement grande (en théorie), les ressources nécessaires pour implanter ces algos augmenteront donc à chaque fois en conséquence.

    Existe-t-il un algo qui n'a pas besoin de considérer la longueur la liste? j'aurai tendance à penser que non (mais je n'en sais rien) et qu'en conséquence l'algo que je cherche n'existe pas. Mais comment le prouver pour en être bien certain ?

  11. #10
    whoami

    Re : algorithme exact de calcul de moyenne

    Bonjour,

    Si tu envisages qu'il n'y ait pas de limite aux entrées, tu ne peux pas limiter la taille des données, facile à prouver : une somme infinie de termes tend vers l'infini.

  12. #11
    inviteea95960a

    Re : algorithme exact de calcul de moyenne

    non ça ne prouve rien, là tu suppose que tu utilises un algorithme qui va considérer à un moment ou à un autre la somme de tous les termes.

    Mais qu'est-ce qui te dit qu'il n'existe pas un autre algorithme qui n'utilise pas cette quantité ?

  13. #12
    polo974

    Re : algorithme exact de calcul de moyenne

    Citation Envoyé par phorane Voir le message
    C'est ce dont je parlais quand je parlais de «bibliothèque de grand nombre», et ça me semble sortir l'arme de destruction massive pour se débarrasser d'un moustique, et on finira pas utiliser énormément de ressources...
    Saleté de moustique.
    Citation Envoyé par phorane Voir le message
    Je n'ai pas vérifié si le calcul de l'arrondi est correct on non car ce n'est pas le problème d'obtenir les formules, mais comment faire un calcul qui restera exact quel que soit la longueur de la liste.

    Utiliser du 64 bits pour des entiers 32bits ça va un moment mais si la liste est très longue ça ne suffit plus.
    4 milliards de moustiques, ça fait un sacré nuage déjà!!! il te faudra plus qu'une bombe d'insecticide pour en venir à bout.
    Existe-t-il un algo qui n'a pas besoin de considérer la longueur la liste? j'aurai tendance à penser que non (mais je n'en sais rien) et qu'en conséquence l'algo que je cherche n'existe pas. Mais comment le prouver pour en être bien certain ?
    choix 1: tu stockes la somme et le nombre pour faire la div. la somme est juste, le nombre est juste,
    il faut "log base2 du nombre arrondi vers le haut" bits pour stocker le nombre d'échantillons.
    il faut pour la somme autant de bit que le nombre plus la longueur nécessaire à l'échantillon max.
    il faut ensuite faire gaffe lors de la division à ne pas perdre de précision.
    ces choses sont gérées dans les bibliothèque d'arithmétique sur entiers de longueur arbitraire.
    la division n'est nécessaire qu'au moment où on désire un résultat.

    choix 2: tu calcules la moyenne au fil de l'eau avec la formule proposée par sitalgo
    le pb, c'est qu'à chaque itération, tu intègres une erreur d'arrondi, et que ça coûte 2 divisions (l'addition et la multiplication à coté, c'est gratos)
    il faut tout de même stocker la moyenne et le nombre sur des formats qui grandissent au fur et à mesure qu'on intègre des données...
    sauf qu'il faut stocker sur la bonne longueur dès le départ, hors on ne la connaît pas à priori ! ! !
    (la preuve (très imagée): 1/3 stocké sur 2 digit donne 0.33, mais si on va au-delà de 100 échantillons, 1/100 = 0.01, on perd des infos, il aurait fallu stocke 1/3 sur 3 digit, soit 0.333, mais si .... etc, etc...)
    bref, c'est l'algo type où les float ou double mal exploités vont montrer leurs limites.

    choix 3: (juste pour dire) tu stockes tous les échantillons, et à chaque fois, calcule la moyenne...
    aucun intérêt sauf si tu veux calculer une moyenne glissante sur N échantillons, il faut donc garder les N échantillons, le nombre d'échantillons et la somme (à laquelle on retire le sortant à partir du moment où N est atteint), mais là, on est dans un système fini en taille de l'ensemble.

    Conclusion: il faut stocker sous le format de fraction Sigma/Nb, c'est le format le plus économique sans perte de précision, et pouvant grandir au fil du besoin, bref, que du bonheur.

    Les anglo-saxons sont habitués à le faire contrairement à nous les frenshies (pour une fois qu'ils n'ont pas entièrement tors).
    Jusqu'ici tout va bien...

  14. #13
    invite1acecc80

    Re : algorithme exact de calcul de moyenne

    Hi,
    Citation Envoyé par whoami Voir le message
    facile à prouver : une somme infinie de termes tend vers l'infini.
    heu...



    ...

  15. #14
    inviteea95960a

    Re : algorithme exact de calcul de moyenne

    Bonjour,

    Désolé je pensais avoir été clair sur ce que je demandais. Je ne cherche pas des astuce d'implantation qui permette de gérer les ressources nécessaires qui grandiront au fur et à mesure. Ça je sais faire.

    La question c'est «est-ce qu'il existe un algo qui va utiliser une quantité bornée de ressources quelque soit la longueur de la liste». Personnellement (comme apparemment tout le monde ici) je ne pense pas qu'il existe un tel algo. Mais alors comment on pourrait faire pour prouver qu'il n'en existe pas qui satisfasse la spécification (entrée: liste d'entier, sortie: un entier dans le même intervalle qui est la moyenne entière approchée des entiers de la liste en entrée) en utilisant une quantité de ressources bornée quel que soit la longueur de la liste.

    Il existe des méthodes (que je ne maîtrise du tout, au passage) en théorie de la calculabilité qui permettent de prouver (parfois, pas toujours) la non calculabilité d'une spécification, mais ces méthodes de prennent pas en compte (à ma connaissance) les ressources nécessaires au calcul. Dans le cas que j'évoque ici ce n'est pas un problème de calculabilité, on est tous capable de pondre un algo qui va calculer de manière exacte la moyenne entière approchée si on n'a pas à se préoccuper de la disponibilité des ressources. Mais comment prouver qu'il n'existe pas d'algo qui n'utiliserait qu'une quantité bornée de ressources quelle que soit la longueur de la liste? (À moins qu'il se trouve que cet algo existe, et je pense que tout le monde aimerait le connaître)

    Merci

  16. #15
    whoami

    Re : algorithme exact de calcul de moyenne

    Bonjour,
    Citation Envoyé par Astérion Voir le message
    Hi,


    heu...



    ...
    Je sais, mais en l'occurrence, il s'agit d'entiers.

  17. #16
    polo974

    Re : algorithme exact de calcul de moyenne

    Citation Envoyé par phorane Voir le message
    Bonjour,

    Désolé je pensais avoir été clair sur ce que je demandais. Je ne cherche pas des astuce d'implantation qui permette de gérer les ressources nécessaires qui grandiront au fur et à mesure. Ça je sais faire.
    ...
    Merci
    Désolé, je n'ai peut-être pas été très clair dans mon message, mais les solutions possibles ne sont pas très nombreuses:

    on fait sigma/ nb (donc somme, donc stockage d'une information nécessitant un stockage grandissant (d'ailleurs idem pour nb)).

    on fait un calcul de moyenne qu'on pondère à chaque nouvel échantillon, mais là, il faut stocker un rationnel, et donc soit sous la forme numérateur/dénominateur (retour au premier cas), soit sous un format à virgule (flottant ou non), mais TOUJOURS avec un arrondi donc une perte de précision.
    et de toute façon, il faut aussi stocker nb sur une taille en théorie inconnue mais grandissante.

    Il n'y a pas de magie permettant de faire disparaître le nb d'échantillons dans un calcul (juste) d'une moyenne. Comme la taille de nb est inconnue, il faut une représentation pouvant évoluer.
    Jusqu'ici tout va bien...

Discussions similaires

  1. Algorithme de calcul de la puissance d'un nombre
    Par Sam* dans le forum Logiciel - Software - Open Source
    Réponses: 22
    Dernier message: 04/10/2013, 14h31
  2. [FORTRAN]algorithme de calcul de valeurs propres
    Par Julien78 dans le forum Logiciel - Software - Open Source
    Réponses: 1
    Dernier message: 14/01/2010, 08h55
  3. Algorithme de calcul d'un déterminant de matrice
    Par inviteb1a0f5f6 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 12/11/2006, 19h45
  4. algorithme pour le calcul numerique
    Par invite4ef352d8 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 11/12/2005, 12h56
  5. calcul d'une moyenne de notes
    Par invitee685b427 dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 07/02/2005, 15h22
Découvrez nos comparatifs produits sur l'informatique et les technologies.