Forums Développement Multimédia

Aller au contenu

Suite de nombres pseudos aléatoires

CODE Actionscript

25 réponses à ce sujet

#1 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 29 March 2013 - 20:22 PM

Allez savoir pourquoi, je me suis mis en tête de remplacer la fonction Math.random() par un truc à ma sauce.

A cela 3 raisons :
- j'ai souvent entendu dire que cette fonction est lente alors, pourquoi ne pas chercher à l'optimiser ?
- je me sers le plus souvent du Math.random() pour des valeurs uint, d'où un récurrent uint(Math.random()*0xFFFFFFFF) (ou sinon du binaire, pas terrible non plus (Math.random()>0.5)), pourquoi ne pas tirer directement un uint ?
- j'aimerais des fois reproduire le même enchaînement pseudo aléatoire (comme avec le PerlinNoise).

Mes recherches m'ont mené à Hiroshima.
J'ai lu, compris 25% de la méthodologie.
Téléchargé les sources en C et traduit ce que j'ai pu, c'est à dire ce qui m'a semblé le cœur sans le changement d'état qui fait appel a des pointeurs (voire même doubles pointeurs ?)
J'ai obtenu un truc apparemment aléatoire mais très lent.

Du coup, je me suis décidé a tenter l'expérience from scratch.
Ma première réussite me donne des résultats :
- variés,
- 50% plus rapides que le Math.random()
- reproductibles
Ce qui n'est déjà pas si mal, dit l'onaniste qui sommeille en moi.


Voici la classe en l'état.
C'est simple (mais c'est le but) : opération bitwise sur les anciennes valeurs décalées de 7 bits à gauche et de 4 bits à droite… en gros :-D


package
{
public class Random
{
  public static var A:uint=0xedca9865;
  public static var B:uint=0x123567;
  public static var next:uint=0;
  init(0x65412de2);
  public static function get u():uint
  {
   return next=(A+=next&0xDD^next<<7)^(B+=next&0xBB^next>>4);
  }
  public static function init(_u:uint):void
  {
   A = 0xedca9865;
   B = 0x123567;
   next = _u;
  }
}
}
 

S'utilise comme ceci :
var alea:uint=Random.u;

J'ajouterai sans doute .i, .N et .B pour les types int, Number et Boolean…


J'en viens à mes questions…


Le côté aléatoire me semble suffisant pour mes besoins. J'ai testé sur des couleurs dans un grand bitmapdata. J'obtiens un grain un peu plus riche que le natif, ce qui ne me dérange pas et surtout sans motif apparent… Vérifié dans photoshop à la va-vite, les couleurs sont équilibrés, 3 petits trous apparemment mais je serai curieux d'étudier un peu plus sérieusement les résultats, savoir s'il y a des absences, des motifs, une période… autant de truc que je ne vois pas comment étudier vu mes connaissances en Maths (et sans doute en probabilités ?).

Est-ce que quelqu'un à une idée de comment s'y prendre ?
Est-ce que quelqu'un à déjà étudié le sujet ?

#2 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 29 March 2013 - 20:27 PM

Yop,

Tu peux jeter un oeil ici si tu veux : http://en.wikipedia....ntial_generator

Et là : http://en.wikipedia....umber_generator

#3 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 29 March 2013 - 20:36 PM

:-) Là, je n'ai ni le niveau en Math (je ne sais pas lire les équations(?), ni le niveau en anglais…
Bizarrement, j'ai mieux compris TinnyMT en lisant le code qu'en lisant les explications…

#4 Goabonga

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2724 messages

Posté 29 March 2013 - 20:42 PM

Je ne pense pas que tu puisses faire plus optimisé en as3 !!!

Pour avoir une vision de ce qui ce cache derrière voila la source :
https://github.com/n...e/MathUtils.cpp



pour des integer sur une architecture 8bit j'utilise une macro qui donne ça :
rand=(rand*109+89)%251;

sur du 32bit
http://delog.wordpre...-math-on-avr32/

#5 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 29 March 2013 - 20:48 PM

@ Goabonga : je suis complètement largué, là…


Alors, je redéfinit ma première question :
- Est-ce que quelqu'un à une idée de comment s'y prendre [pour avoir des statistiques sur les faiblesses de mon code] ?

#6 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 29 March 2013 - 20:58 PM

Voir le messageGoabonga, le 29 March 2013 - 20:42 PM, dit :

pour des integer sur une architecture 8bit j'utilise une macro qui donne ça :
rand=(rand*109+89)%251;

ça je comprends mieux, mais en le testant, ça fait quand même un très petit motif (sans doute normal pour du 8 bits… §?)

#7 Goabonga

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2724 messages

Posté 29 March 2013 - 21:02 PM

oui de 0 a 255 normalement :)


Cherches un cours qui aurait pour theme "cycle detection" et qui traite de l'algo de Brents (et laisse toi pousser la barbe :) )

#8 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 29 March 2013 - 21:06 PM

J'ai une autre idée sinon… :-D

Je commence à l'utiliser en l'état et je verrai bien si je tombe sur une aberration avant d'avoir de la barbe… :-P

#9 Goabonga

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2724 messages

Posté 29 March 2013 - 21:08 PM

http://mathpages.com/home/kmath458.htm

T'as commencé alors tu finis !
:)


#10 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 29 March 2013 - 21:15 PM

Citation

Pour avoir une vision de ce qui ce cache derrière voila la source :

:shock:

Lol bon courage ;-)

#11 Galacta

    Etudiant Ingénieur

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 689 messages

Posté 30 March 2013 - 00:30 AM

Y a quand même plus simple, utiliser une suite mathématique, par exemple :

Xn+1 = ( 1103515245 * xn+ 12345 ) %MAX_VALUE


Peut-être moins aléatoire, mais efficace car utilisée sur les systèmes Unix, (peut-être plus actuellement, j'ai pas vraiment investigué).

Il suffit de choisir un x0 qui soit créée dynamiquement, tel que getTimer(), ou System.currentMemory() par exemple ...

C'est pas fait pour de la crypto par contre.
Word hard, play hard.

#12 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 30 March 2013 - 01:48 AM

Moi quand j'ai besoin de pouvoir reproduire les mêmes séries j'utilise http://lab.polygonal.de/?p=162
Je ne me suis pas posé la question de l'optimisation, c'était tout fait et ça m'a convenu :mrgreen:
Il y a peut-être des infos intéressantes dans l'article du blog.

[edit] Oups j'oubliais quelle était ta question. Et... Je ne sais pas y répondre :)

#13 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 30 March 2013 - 10:11 AM

Alors, j'ai tout testé (et tout feuilleté)…

Question tests de rapidité :
- pour 1.000.000 occurrences,
- vieux mac powerpc, 1.25GHz
- Flash CS3 - publication Flash Player 9
- code inclus dans la classe de test

- ma version : 64ms
- Math.random() : 205ms
- version ParkMiller(lilive) : 980ms *
- version Galacta : 1227ms

* Pour ParkMiller, je n'ai pas inclus le code directement dans la classe de tests, je retenterai peut-être.

En gros, ma version atteins bien ses objectifs de rapidité, puisque c'est la seule plus rapide que le classique Math.random(), de reproductivité (comme les autres) et de format uint…

Reste cette question d'équilibre des sorties…
Je crois que je vais au moins tenter de compter la fréquence sur chaque bit, voir si on est bien proche des 50%…
Ça me donnera au moins une première idée…

Les perfs sont sans doute différentes avec des machines plus récentes.
Je joins mes fichiers, si quelqu'un veux tenter (pensez aussi à changer la version de player)

@GoaBonga : je ne cherche pas à faire de la cryptologie, juste à pousser des particules un peu plus vite dans une fontaine, dans un voxel ou dans un labyrinthe.

Fichier(s) joint(s)



#14 Goabonga

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2724 messages

Posté 30 March 2013 - 10:31 AM

Je sais :)
L'algo dont je parle permet de valider une suite ne nombre générer par itérations linéaires ou non-linéaires....


#15 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 30 March 2013 - 11:34 AM

FP 11 standalone, pour 10 000 000 occurences (j'ai rajouté un 0), donne respectivement chez moi :
124
308
324
536

#16 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 30 March 2013 - 12:03 PM

Voir le messagedldler, le 30 March 2013 - 10:11 AM, dit :

Reste cette question d'équilibre des sorties…
Je crois que je vais au moins tenter de compter la fréquence sur chaque bit, voir si on est bien proche des 50%…
Ça me donnera au moins une première idée…
Un générateur qui renvoie uniquement des 0x00000000 et des 0xFFFFFFFF passerait ce test avec succès.
J'ai pensé à compter le nombre d'apparition de chaque nombre, mais Ça ferait un array (ou vector) de longueur 0xFFFFFFFF, cad 0xFFFFFFFF / 1024 / 1024 = 4096 Mo, c'est peut-être un peu beaucoup !
Je suis allé regarder des pages sur les statistiques. On dirait que comparer la variance ou l'écart type de 2 méthodes de génération puisse te renseigner, mais je ne suis pas sûr, je n'ai jamais étudié les stats:
http://fr.wikipedia....bilit%C3%A9s%29
http://www.statcan.g...5214891-fra.htm

#17 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 30 March 2013 - 13:40 PM

@ Goabonga : je vais faire une autre tentative de lecture alors. Mais je doute de comprendre le début de quoi ça parle.

@ lilive : merci pour les perfs. ça reste donc intéressant…

Pour les tests, j'ai bien compris le souci avec 0 et 0xFFFFFFFF, par exemple. Mais je sais déjà que mon retour est varié, via une copie d'écran d'un grain sur un bitmapdata, étudié avec les histogrammes dans Photoshop. Je ne cherche pas une démonstration mathématique. Juste à éprouver un peu le truc.

J'ai quelques autres idées :
- compter le nombre de bits à 1 dans chaque nombre. Et je ne vais pas faire une moyenne mais incrémenter un tableau de 32 cases.
- pareil pour la position des bits à 1, donc
- compter les sorties par tranche de valeurs (32 tranches ?)
- et si j'ai bien compris, faire une moyenne entre Math.random() et mon tirage

Pas d'autres idées ?

Sinon, j'en suis désolé croyez-moi, mais je ne comprends vraiment rien à tous les trucs sous la forme Image IPB
Faut que je fasse sans.

#18 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 30 March 2013 - 13:56 PM

Voir le messagedldler, le 30 March 2013 - 13:40 PM, dit :

Sinon, j'en suis désolé croyez-moi, mais je ne comprends vraiment rien à tous les trucs sous la forme Image IPB
Faut que je fasse sans.
Je trouve Wikipedia très difficile pour les explications mathématiques. Je suis souvent largué moi aussi.
Dans le 2eme lien que j'ai donné c'est plus clair:
Image attachée: variance.jpg

Cela donnerait:

Générer une première fois N nombres aléatoires R1, R2, ... RN.
En calculer la moyenne M = (R1 + R2 + ... + RN) / N
Puis calculer la variance en faisant:
[ (R1 - M)² + (R2 - M)² + ....+ (RN - M)² ] / N

C'est donc pas compliqué. Comme je disais, ce que je ne sais pas par manque de pratique, c'est à quel point la variance te renseignera sur ce que tu cherches à savoir.

#19 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 30 March 2013 - 14:17 PM

Et sinon je pensais:
Pour regarder ce que ça donne de façon brute, tu pourrais choisir une plage de valeur P à observer, par exemple les nombres de 0 à 1023.
Créer un tableau T de 1024 int pour compter le nombre d'occurrences de ces valeurs. Initialiser ce tableau à 0.
A chaque enterframe:
- Générer disons 10 000 valeurs aléatoires avec ton générateur. Pour chacune de ces valeurs, si elle est dans la plage P (cad entre 0 et 1023), la compter. T[0] est le nombre d'apparition de la première valeur de P (0 dans mon exemple), T[1] est le nombre d'apparition de la deuxième valeur de P (1 dans mon exemple), etc.
- A ce stade T te donne le nombre de fois qu'est apparue chaque valeur de P.
- Dessiner T sous forme d'histogramme.
En laissant tourner un moment tu as une bonne vision de l'homogénéité de la répartition de tes nombres sur la plage P.

Tu peux même analyser le résultat après un certain nombre d'enterframes, en calculant:
Le minimum MIN de T, cad le nombre d'apparition de la valeur de P qui est la moins sortie au tirage aléatoire
Le maximum MAX de T, cad le nombre d'apparition de la valeur de P qui est la plus sortie au tirage aléatoire
Si MIN et proche de MAX c'est que c'est homogène sur P.
Si MIN == 0 tu as des trous
Tu peux aussi calculer la moyenne MOY des valeurs de T.

Tu peux faire ce test sur plusieurs plages P différentes, et comparer à chaque fois avec le MIN, le MAX, et la moyenne MOY des autres plages. Tu auras alors une vision d'ensemble de l'homogénéité.

J'espère avoir été compréhensible :)

#20 Galacta

    Etudiant Ingénieur

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 689 messages

Posté 30 March 2013 - 14:23 PM

J'ai tenté de passer ta fonction en C en utilisant FlasCC et définissant la fonction comme inline. Les performances ne sont pas tip top...

La variance te donnera une idée de la répartition des valeurs obtenues par ta fonction, plus elle est grande mieux c'est, dans ton cas. Deux valeurs seront ainsi très dispersées.

L'espérance, c'est ce que tu peux attendre de ta fonction, sur un grand nombre de tirage, pas sur que cette valeur soit la plus intéressante. Mais elle est nécessaire pour calculer la variance.

Comme tu test sur un nombre n de tirage d'un nombre aléatoire, tu es dans un cas discret (tu connais à l'avance le nombre de cas que tu te donnes), donc tu peux te ramener à l'expression Image IPB , pi étant la probabilité que la ième valeur sorte ( donc 1/ uint.MAX_VALUE ) et xi étant ta valeur à la ième itération, dans un cas aléatoire parfait.

Cependant, vu que tu initialises toi même le seed de ta fonction, et les paramètres a et b, ce n'est pas vraiment de l'aléatoire, juste une suite de nombre, de sorte Un+1 = f(un) ... Tu as reproduit le comportement de la fonction rand() en C.

Dans ton cas, la probabilité est toujours de 1, si je ne dis pas de bêtises, car Un+1 est dépendant de Un. Tu dois donc pouvoir juste faire la somme de 1 à K de (xi - moyenne de x)²
Word hard, play hard.

#21 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 30 March 2013 - 15:06 PM

OK.
Ça devient plus clair, petit à petit.
Je vais me faire un tableau de bord, sur un enterframe, et étudier certaines valeurs génériques + une tranche.

@Galacta : je ne suis pas surpris des différences de performances avec le C. J'ai juste tenté de générer de l'aléa en n'utilisant que les instructions que je sais rapide en AS. Pas de multiplication/division par exemple.

Week-end chargé, donc je ne sais pas quand j'aurai fait le tour, mais je vous tiens au jus.

Encore merci beaucoup à tous.

#22 Galacta

    Etudiant Ingénieur

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 689 messages

Posté 30 March 2013 - 16:02 PM

Justement avec le C, les performances sont dégueulasses :D 190ms pour ta fonction, et 1 000 000 d'itérations ...
Word hard, play hard.

#23 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 30 March 2013 - 17:12 PM

Voir le messageGalacta, le 30 March 2013 - 16:02 PM, dit :

Justement avec le C, les performances sont dégueulasses :D 190ms pour ta fonction, et 1 000 000 d'itérations ...
:D Ça tombe bien, je ne cherche pas un truc optimisé en C…

Bon.
Premier jet, question moyenne, Ça va.
Mais question variance, les valeurs sont aussi folles pour ma méthode que pour le Math.random()…
Je ne sais pas trop ce que je vais pouvoir tirer de tout Ça…

PS : la première ligne correspond à la valeur de la boucle en cours
la seconde correspond à la moyenne des boucles

Fichier(s) joint(s)



#24 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 30 March 2013 - 17:40 PM

Je pense que ta conversion de la variance en uint est peut-être une erreur.
Voici ce que ça donne sans conversion.

function calculer(a:Array,o:Object):void
{
        var moyenne:Number=0;
        for (i=0;i<max;i++) moyenne+=a[i];
        moyenne /= max;
        o.moyenne= (o.moyenne*(t.currentCount-1)+moyenne)/t.currentCount;
        o.tableau.c1.value1.text=uint(moyenne).toString(16).toUpperCase();
        o.tableau.c1.value2.text=uint(o.moyenne).toString(16).toUpperCase();
       
        var variance:Number=0;
        for (i=0;i<max;i++) variance += (valeurs[i]-moyenne)*(valeurs[i]-moyenne);
        variance /= max;
        o.variance=(o.variance*(t.currentCount-1)+variance)/t.currentCount;
        o.tableau.c2.value1.text=variance.toFixed(0);
        o.tableau.c2.value2.text=o.variance.toFixed(0);
}

Du coup les vairances de ta méthode et random se ressemblent.

Fichier(s) joint(s)



#25 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 30 March 2013 - 18:31 PM

Rhhhaaaa… encore un merci lilive.

J'ai fini par comprendre : dans 'somme des carrés des différences' il y a 'carré', donc valeurs possibles de longueur 0xFFFFFFFFFFFFFFFF… et une moyenne supérieure à 0xFFFFFFFF, qui ne tiennent pas dans un uint. Du coup, je récoltais sans doute une sorte de modulo… J'ai corrigé en ne typant plus et en affichant en base 32…

Et je continue sur les bits cette fois… :-)
Pour l'instant, tout va bien…

#26 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 30 March 2013 - 22:57 PM

Si on m'avait dit, il y a 4 ans(?) qu'un jour je m'amuserais devant un truc pareil… je ne m'aurais pas cru…

Bon. Je trouve un truc équilibré sur les bits aussi.
Difficile de comparer vraiment puisque la méthode Miller ne rend qu'un 31 bits (les plus bas) tandis que Math.random() renvoie les 31 bits les plus hauts…
Mais pour le besoin que j'en ai, je trouve les tests suffisamment concluants. Je vais décliner les autres types et je poste la version complète de la classe.

Je poste le swf, mais ouvrez-le dans une nouvelle fenêtre, c'est écrit tout petit.
La première ligne des bits est la moyenne d'apparition de ce bit
La seconde ligne est le nombre de sorties contenant ce nombre de bits.

Fichier(s) joint(s)





1 utilisateur(s) li(sen)t ce sujet

0 membre(s), 1 invité(s), 0 utilisateur(s) anonyme(s)