Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par dprtl »

Entre deux séances de d’optimisation pour Ma... dov'è il sapone et de recherche sur les algorithmes de statistique, sans résultat très probant, je suis tombé dans Wikipedia sur une loi plutôt étonnante. Celle-ci ne va pas beaucoup m’aider pour le jeu de la savonnette mais je la trouve élégante et, surtout, très contre-intuitive ! D’où cette idée de MPO dont l’énoncé commence ci-après. Il est possible que les plus aguerris d’entre vous le trouvent trop simple, ou connaissent déjà la formule directe ?.. On verra bien :oops:

Il s’agit donc d’écrire un programme court capable de réaliser l’équivalent de la chose suivante :
  1. tirage au sort de trois nombres A, B et C dans l’intervalle ]0,1[
  2. multiplication A*B*C et extraction du chiffre K le plus significatif (le premier chiffre le plus à gauche différent de zéro). K peut donc prendre neuf valeurs entières de 1 à 9.
  3. réitération des étapes (1) et (2) un grand nombre de fois. Soit 1000 fois au minimum, ou bien N fois, en fonction des performances de votre machine de prédilection. Après chaque calcul, on incrémente des compteurs T(K) pour compter les occurrences de chaque chiffre.
  4. à la fin des itérations, affichage du résultat du comptage sous forme de pourcentages arrondis à l’entier le plus proche, uniquement pour les occurrences des chiffres de 1 à 5, en utilisant un affichage à 10 chiffres. Par exemple :

    3018121008
Ce résultat signifie que le ‘1’ est apparu comme chiffre le plus significatif dans 30% des tirages, le ‘2’ dans 18%, le ‘3’ dans 12%, le ‘4’ dans 10% et le ‘5’ dans 8%. Pour ne pas défavoriser les machines les moins puissantes, on fera l’impasse sur le comptage des 6, 7, 8 et 9.

Si nous faisons confiance à notre intuition, comme A, B et C sont issus d’un tirage aléatoire, les neufs chiffres devraient avoir chacun la même probabilité d’apparition, soit environ 11% ? Votre calculette va rapidement vous démontrer que ce n’est pas le cas 8O

Sommaire des MPO
Modifié en dernier par dprtl le 26 août 2021 00:03, modifié 3 fois.
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par bernouilli92 »

Petites remarques:- quand tu multiplie 3 nombres de l’intervalle ]0,1[, tu obtiens un nombre dans l’intervalle ]0,1[, le premier chiffre après la virgule peut être un 0.
Ou alors par chiffre significatif, tu veux dire le premier chiffre différent de 0.

Dans le 3), tu écris qu’il faut répéter l’étape 2, ce ne serait pas l’étape 1 ?
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par dprtl »

bernouilli92 a écrit : 25 août 2021 16:44 Petites remarques:- quand tu multiplie 3 nombres de l’intervalle ]0,1[, tu obtiens un nombre dans l’intervalle ]0,1[, le premier chiffre après la virgule peut être un 0.
Ou alors par chiffre significatif, tu veux dire le premier chiffre différent de 0.
Oui, le premier chiffre significatif est différent de 0.
bernouilli92 a écrit : 25 août 2021 16:44 Dans le 3), tu écris qu’il faut répéter l’étape 2, ce ne serait pas l’étape 1 ?
Exact ! Je corrige mon erreur en 'edit' :oops:
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par zpalm »

Cool, l'occasion de sortir la reine des MPO, la WP 34S: 25 pas et 52 octets.

Code : Tout sélectionner

01▸LBL "MPO"
02 CLREGS
03 STO 00
04 RAN#
05 RAN#
06 RAN#
07 ×
08 ×
09 MANT
10 INC -> X
11 X<>Y
12 DSE 00
13 BACK 009
14 #005
15 SDR 003
16 INC X
17 #000
18 RCL -> Y
19 RCL/ T
20 +
21 SDL 002
22 ROUNDI
23 ISG Y
24 BACK 006
25 RTN
On entre le nombre d’itérations dans X puis XEQ "MPO".

Le résultat est effectivement contre-intuitif au premier abord, mais pas si étonnant finalement puisque chaque fois que l'on multiplie par un nombre inférieur à 1, le résultat est inférieur au nombre initial.
Par contre je n'ai pas cherché la formule qui donnerait directement le résultat.

Note: petite astuce, comme la fonction RAN# retourne un nombre 0<=n<1 on peut tomber sur le cas ou le résultat est nul, dans ce cas on incrémente le registre 0 qui est le compteur de boucle, avant de le décrémenter, ce qui ne compte pas pour le nombre d'itérations total.
Modifié en dernier par zpalm le 25 août 2021 23:42, modifié 1 fois.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par dprtl »

Encore un excellent programme de notre ami zpalm ! Rien que de le recopier sur cette satanée WP-34S, à l'ergonomie de m$#@!@§, c'est déjà une gageure. Et comme ça faisait longtemps que je n'y avais pas touché, je n'y serais pas arrivé sans ouvrir le manuel :D
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par zpalm »

dprtl a écrit : 25 août 2021 22:40 Rien que de le recopier sur cette satanée WP-34S, à l'ergonomie de m$#@!@§, c'est déjà une gageure.
C'est une machine un peu sauvage qui demande à être apprivoisée comme un pur sang, on apprécie quand même d'avoir le moins de pas possible à entrer ;)
Heureusement, pour l'avoir toujours avec soi on dispose depuis peu d'une version Android identique à l'originale ainsi que d'une version qui tourne sur la DM42 avec un système de menu mappé sur le clavier de la DM42 sans nécessiter d'overlay. C'est propre et efficace mais ça demande quand même une certaine familiarité avec la 34S.
dprtl a écrit : 25 août 2021 15:58 à la fin des itérations, affichage du résultat du comptage sous forme de pourcentages arrondis à l’entier le plus proche,
J'ai changé l'instruction IP au pas 22 par ROUNDI pour être conforme à l'énoncé.
Avatar du membre
Pocket
Administrateur
Administrateur
Messages : 5941
Enregistré le : 24 mai 2002 16:55
Localisation : Toulouse
Contact :

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par Pocket »

Salut,

Sans calculatrice, je dis 1 à plus de 50%.

A+
Pocket, voit tout, sait tout, lit l'avenir dans les entrailles d'une base phpBB ...
Image
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par Danny »

C’est bon on peut fermer le sujet :lol: 8)
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par C.Ret »

Bon, comme à mon habitude je n'y arrive pas bien. J'ai un peu de mal à respecter les consignes.

Voici donc pour le moment le truc le plus optimisé, mais qui pour le moment est assez loin de ce qui est demandé :

Instructions:
Se procurer une HP-15C ou un modèle assez proche ou à défaut un émulateur pour y saisir le code suivant :

Code : Tout sélectionner

001- ►LBL A
002-      STO 0  CLx	
004-      2  10^X  ×	
007-      1.005  STO I  CLx	
014-     ►LBL 1	
015-          RCL×0  RCL+(i)  ISG I  GTO 1	
019-      RND  +	
021-  RTN
Initialiser quelques registres afin de rendre cela probable et s'approcher régressivement un peu du sujet :

Code : Tout sélectionner

.0162 STO 1  .412  CHS  STO 2  4.113  STO 3  20  CHS  STO 4  46  STO 5 
Se mettre en mode USER pour minimiser le nombre de touches à presser :

Code : Tout sélectionner

f USER
Comme dprtl ne demande que les pourcentages arrondis à l'unité pour les chiffres de 1 à 5, procéder ainsi:

Code : Tout sélectionner

0  FIX 0  1  A  2  A  3  A  4  A  5  A
Noter que l'on peu avoir les pourcentages arrondis à l'unité pour n'importe quelle séquence de cinq chiffres puisque l'affichage se limite à dix chiffres.

Code : Tout sélectionner

0  FIX 0  5  A  6  A  7  A  8  A  9  A
Mais que les pourcentages de chaque chiffre peuvent être obtenus individuellement et approximativement:

Code : Tout sélectionner

0  FIX 1  7  A  
affiche 5.1 %

Bon, tout cela n'approche encore que très grossièrement les résultats espérés ...
Modifié en dernier par C.Ret le 26 août 2021 10:57, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par gege »

Bonjour,
Intéressant, mais est-ce contre-intuitif ?

Si on ignore les produits A*B*C situés dans l'intervalle [0, 0.1[ il est clair qu'il n'y a pas de raison que la répartition soit uniforme : on n'aura pas la même fréquence dans [0.1, 0.2[ que dans [0.5,0.6[ par exemple.
Pour l'intervalle [0, 0.1[ on retire le zéro du début et on se retrouve au cas précédent, pas d'uniformité non plus.
Le truc se replie donc comme un mille-feuilles et n'est pas uniforme.

Par contre la loi donnant la répartition… je réfléchis ;-)
Marrant !
G.E.
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par bernouilli92 »

Je pense que la répartition doit être similaire à la répartition des chiffres dans les nombres de 1 à N.
Le 1 est beaucoup plus fréquent que le 2 qui est plus fréquent que le 3 etc.
Je crois que c’est la loi de Benford qui s’applique ici aussi.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par C.Ret »

Ouff, j'ai beau réfléchir dans un sens ou dans l'autre, je ne trouve pas de loi simple qui pourrait aider à réduire mon code.

Du coup, je fais comme dprtl le demande , ici pour une HP-28S:

On entre le nombre de tirages aléatoire souhaité (par exemple 1E3) et on lance le code MPO préalablement saisi :

Code : Tout sélectionner

« { 9 } 0 CON 
  1 ROT START
      RAND RAND RAND * * MANT IP DUP2 GET 1 + PUT
  NEXT DUP CNRM / 100 * 0 FIX »
'MPO' STO
  
1[EEX]3 (MPO)
Les pourcentages arrondis à l'unité s'affichent dans le vecteur au niveau 1: de la pile pour chaque chiffre de 1 à 9.

Oui je sais, c'est pas exactement ce qui a été demandé, mais c'est plus court sur cette machine qui n'est pas limité à un affichage de dix chiffres.

P.S.: Et puis je suis content, j'ai (enfin) trouvé une machine qui a une instruction MANT ce qui comme pour la WP34S de zpalm facilite bien les choses !! hé hé !


NOTE: La fonction RAND de l'HP-28S est sensée donner un nombre aléatoire sur l'intervalle [ 0 , 1 [ mais je n'ai pas pris le soin de tester si le produit est nul. J'utilise cette calculatrice depuis octobre 1991 et jamais la fonction RAND ne m'a renvoyé une valeur nulle. Cela pourrait arriver un jour, ce n'est pas impossible il suffit d'initier la semence par 0 RDZ et toutes les valeurs sont alors nulles, mais comme j'ai entré (il y a très longtemps) une semence non nulle de douze décimales, la probabilité que le nombre de douze chiffres renvoyé par un RAND soit exactement 0.00000000 est extrêmement faible (ou alors c'est mon karma, je ratte très souvent les événements rarissimes qui surviennent autour de moi !)

Donc, pour ce MPO, pas de test ni d'astuce pour le produit nul (contrairement au code d zpalm); ce qui peut présenter un danger pour les utilisateurs d'HP-28S n'ayant pas autant de chance que moi !
Modifié en dernier par C.Ret le 27 août 2021 07:20, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par C.Ret »

bernouilli92 a écrit : 26 août 2021 17:44 Je pense que la répartition doit être similaire à la répartition des chiffres dans les nombres de 1 à N.
Le 1 est beaucoup plus fréquent que le 2 qui est plus fréquent que le 3 etc.
Je crois que c’est la loi de Benford qui s’applique ici aussi.
Effectivement, c'est la loi découverte en 1994 par Jeff BOYLE
Produit de variables indépendantes:
----------------------------------------------------
En 1994, Jeff Boyle a montré que si une variable résulte de la multiplication entre elles d'un grand nombre de variables indépendantes, elle suit à peu près la loi de Benford (exactement à la limite). Autrement dit, la loi de Benford serait naturelle si les nombreux facteurs qui expliquent telle ou telle grandeur agissent multiplicativement.

Ce résultat est un équivalent logarithmique de la loi des grands nombres.
Ici, un lien fort interessant qui explique tout cela (en plus c'est en français pour une fois)!
Math. & Sci. hum. / Mathematics and Social Sciences (46e année, n◦ 182, 2008(2), p. 7–15) - POURQUOI LA LOI DE BENFORD N’EST PAS MYSTÉRIEUSE - Nicolas GAUVRIT , Jean-Paul DELAHAYE.

Voilà qui explicite bien la distribution contre-intuitive, mais malheureusement ne nous donne pas de piste pour la distribution du produit X*Y*Z des trois variables aléatoires de distributions uniformes.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par zpalm »

Merci pour le lien, l'article est intéressant, je ne connaissais pas la loi de Benford.
C.Ret a écrit : 26 août 2021 18:00

Code : Tout sélectionner

« { 9 } 0 CON 
  1 ROT START
      RAND RAND RAND * * MANT IP DUP2 GET 1 + PUT
  NEXT DUP CNRM / 100 * 0 FIX »
'MPO' STO
  
1[EEX]3 (MPO)
J'ai testé ce programme sur ma 48SX et il fonctionne parfaitement, j'ai juste remplacé à la fin '0 FIX' par '0 RND' pour arrondir à l'entier le plus proche sans changer le mode d'affichage.
Il est proche du premier programme que j'avais écris sur ma HP Prime avant de passer sur la WP 34S, du coup j'ai repris le programme de la HP Prime et je l'ai modifié pour obtenir la différence en % entre la fréquence des chiffres avec les tirages aléatoires et celle donnée par la loi de Benford en LOG(1+1/n), en arrondissant les % à 1 chiffre après la virgule:

Code : Tout sélectionner

EXPORT MPO103(N)
BEGIN
 LOCAL b,n,l:={0,0,0,0,0,0,0,0,0};
 FOR I FROM 1 TO N DO
  n:=IP(MANT(RANDOM()*RANDOM()*RANDOM()));
  l(n):=l(n)+1
 END;
 l:=ROUND(100*l/N,1);
 b:=MAKELIST(ROUND(100*LOG(1+1/I),1),I,1,9);
 %CHANGE(l,b);
END;
Voici les résultats de 9 tirages de 100000 produits aléatoires A*B*C:
MPO103.png
MPO103.png (9.71 Kio) Vu 7977 fois
Si la fréquence des chiffres 1, 4 et 5 est proche de celle donnée par la loi de Benford, on observe entre 5 et 10% d'écart environ pour les chiffres 2,3,6,7,8 et 9.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°103 : A*B*C vérification d’une loi contre-intuitive

Message par C.Ret »

Ah! Ah!

J'observe également cet écart entre la répartition du produit de trois variables aléatoires uniformément répartie et la Loi de benford.

J'ai modifié mon programme sur HP-28S pur qu'il compte le premier chiffre significatif pour les trois variable a b et c (issues des trois RAND), mais également les produits de deux variables (respectivement a.b , a.c et b.c) ainsi que le produit a.b.c des trois.

Je publie les comptages issue de 9.E4 tirages sucessifs dans le tableau suivant :

Code : Tout sélectionner

            **1**        **2**        **3**        **4**        **5**        **6**        **7**        **8**        **9**
a         3397 11,3%   3333 11,1%   3312 11,0%   3326 11,1%   3318 11,1%   3384 11,3%   3394 11,3%   3336 11,1%   3200 10,7%
b         3317 11,1%   3354 11,2%   3357 11,2%   3318 11,1%   3297 11,0%   3292 11,0%   3343 11,1%   3415 11,4%   3307 11,0%
c         3261 10,9%   3329 11,1%   3356 11,2%   3321 11,1%   3365 11,2%   3323 11,1%   3320 11,1%   3459 11,5%   3266 10,9%

a.b       7322 24,4%   5407 18,0%   4374 14,6%   3571 11,9%   2730  9,1%   2256  7,5%   1833  6,1%   1437  4,8%   1070  3,6%
a.c       7309 24,4%   5468 18,2%   4325 14,4%   3526 11,8%   2820  9,4%   2314  7,7%   1781  5,9%   1375  4,6%   1082  3,6%
b.c       7166 23,9%   5402 18,0%   4413 14,7%   3549 11,8%   2868  9,6%   2261  7,5%   1889  6,3%   1395  4,7%   1057  3,5%

a.b.c     8845 29,5%   5673 18,9%   4067 13,6%   2956 9,9%    2347 7,8%    1953  6,5%   1623  5,4%   1353  4,5%   1183  3,9%

Benford   9031 30,1%   5283 17,6%   3748 12,5%   2907 9,7%    2375 7,9%    2008  6,7%   1740  5,8%   1535  5,1%   1373  4,6%


Je suis rassuré de la bonne uniformité des densités des trois variables pseudo-aléatoires produites par les instructions RAND.

Comme on peu le voir, les produits de trois variables ne sont pas exactement dans les proportions indiquée par le Loi de Benford, Il faut apparemment bien plus de variables...

Ce qui est impressionnant c'est la façon dont cette répartition évolue dès que l'on fait le premier produit et l'on retrouve bien la même répartition pour les trois produits deux à deux.

Il ne me reste plus qu'à déterminer les réparations des premiers chiffres significatifs pour des produits de quatre, cinq, six, ... variables!
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Répondre

Retourner vers « Tous les Pockets »