cerhu > comp.* > comp.algorithmes

xtof.pernod (19/05/2010, 20h58)
Le 19/05/2010 16:50, Jérôme Benoit a fait rien qu'à écrire :
> Le Wed, 19 May 2010 10:09:14 +0200, Pascal J. Bourguignon a écrit :
>> Soixante lignes? Tu programme en assembleur?


Que nenni, mon bon :

~/cd# wc -l cmf.c
65 cmf.c

> C'est un pur :)


Oui, en fait, '.C', c'est du C0B0L (langage très 'pur' s'il en est =)


ah oui, mais, hé, t'as pas le nombre de fois où la moyenne calculée
croise la moyenne théorique (0.5) !

ex: (mt est le prng 'mersenne twister',
== comp10 est 10Mo de flux compressé par lpaq8,
bits.60 vient du 'Marsaglia Random Number CDROM',
tea est le 'tiny encryption algorithm')

~/cd# mt 50000 | cmf
(...) pos: longueur somme moyennes
268284724: 13 -> 1394.8 ; x = 14794.57 : 18810.24
268284725: 1 -> 18134.0 ; x = 14793.75 : 18810.01
268284726: 1 -> 18135.0 ; x = 14792.94 : 18809.79
268284727: 1 -> 18136.0 ; x = 14792.12 : 18809.57
# final: 6892.1361 => 0.000017

~/cd# cmf < comp10
155574754: 1 -> 28889.0 ; x = 5385.07 : 3467.55
155574755: 1 -> 28890.0 ; x = 5384.89 : 3467.61
# final: 3467.6119 => 0.000022

~/cd# mt 50000 | tea 0x098137018 | cmf
136121150: 1 -> 7909.0 ; x = 17208.74 : 15602.28
136121159: 9 -> 878.9 ; x = 17206.57 : 15602.48
136121160: 1 -> 7911.0 ; x = 17204.39 : 15602.68
# final: 4485.8273 => 0.000011

~/cd# cat *.c | cmf
000001: 1 -> 0.0 ; x = 1.00 : 1.00
000006: 5 -> 0.2 ; x = 3.00 : 2.00
000017: 11 -> 0.2 ; x = 5.67 : 3.22
# final: 3.2222 =)

~/cd# cmf < files/rnd0/bits.60
77409657: 1 -> 5182.0 ; x = 14935.30 : 23945.35
77409658: 1 -> 5183.0 ; x = 14932.42 : 23943.61
77409667: 9 -> 576.0 ; x = 14929.54 : 23941.87
# final: 23941.8705 / 80000000 => 0.000299

Avec ça, on voit clairement que la moyenne globale est
d'autant plus petite que le flux d'entrée est artificiellement
"agité".

Sauf pour -surprise- le texte, ou ça "bloque" très vite en
crachant une valeur ridiculement bas.

> Je me demande par pure curiosité intellectuelle ce que çà donnerait en
> mixant plusieurs source de PRNG ...


Mixer : par ou exclusif, entrelacement, 4eme dimension, ou autre..?

> en haskell c'est facilement
> implémentable avec Random.split.


Cool, en cobol c'est plus chaud..
JKB (19/05/2010, 23h05)
Le 19-05-2010, ? propos de
Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),
Jérôme Benoit ?crivait dans fr.comp.algorithmes :
> Le Wed, 19 May 2010 10:09:14 +0200, Pascal J. Bourguignon a écrit :
> C'est un pur :)
>> Je me demande par pure curiosité intellectuelle ce que çà donnerait en

> mixant plusieurs source de PRNG ... en haskell c'est facilement
> implémentable avec Random.split.


Chic un concours ;-)

#!/usr/local/bin/rpl -scp

RD
<<
{ "borosh13" "cmrg" "coveyou" "fishman18" "fishman20" "fishman2x"
"gfsr4" "knuthran" "knuthran2" "knuthran2002" "lecuyer21" "minstd"
"mrg" "mt19937" "mt19937_1998" "mt19937_1999" "r250" "ran0"
"ran1" "ran2" "ran3" "rand" "rand48" "random_bsd" "random_glibc2"
"random_libc5" "random128_bsd" "random128_glibc2" "random128_libc5"
"random256_bsd" "random256_glibc2" "random256_libc5" "random32_bsd"
"random32_glibc2" "random32_libc5" "random64_bsd" "random64_glibc2"
"random64_libc5" "random8_bsd" "random8_glibc2" "random8_libc5"
"randu" "ranf" "ranlux" "ranlux389" "ranlxd1" "ranlxd2" "ranlxs0"
"ranlxs1" "ranlxs2" "ranmar" "slatec" "taus" "taus113" "taus2"
"transputer" "tt800" "uni" "uni32" "vax" "waterman14" "zuf" }
1
-> GEN POSITION
<<
cls

1 1000000 for I
if
I 1000 mod 1 same
then
GEN POSITION get dup disp rdgn
POSITION incr GEN size mod 1 + 'POSITION' sto
rand s+
ns mean 2 ->list disp
else
rand s+
end
next

ns mean 2 ->list disp

Bon, c'est du goret-codage tout ce qu'il y a de plus sous-optimal,
mais c'est fait en 5 minutes sur un coin de table, et en évitant les
dérives numériques dues au calcul de la moyenne. Dans le programme
proposé plus haut, je ne suis pas sûr que la somme

(loop for i from 0 to 1e6 sum (random 1.0) into s

soit faite dans les règles de l'art, c'est-à-dire en sommant les
nombres du plus petit vers le plus grand.

Résultat :

....
{ 324001
0.499929666258953 }
....
random8_libc5
{ 361001
0.500055614694412 }
....
{ 448001
0.500336379198361 }
random256_glibc2
{ 449001
0.500332235992291 }
random32_bsd
{ 450001
0.500345894738089 }
random32_libc5
{ 451001
0.500336354630807 }
random64_glibc2
{ 452001
0.500357423152803 }
random8_bsd
{ 453001
0.500361602562264 }
random8_libc5
{ 454001
0.500340119956777 }
ranf
{ 455001
0.500304132972317 }
ranlux389
{ 456001
0.500324225031746 }
ranlxd2
{ 457001
0.500340350959623 }
ranlxs1
{ 458001
0.50034482631729 }
ranmar
{ 459001
0.500358943477625 }
taus
{ 460001
0.500383140460758 }
taus2
{ 461001
0.50039528570526 }
tt800
{ 462001
0.50038539017121 }
uni32
{ 463001
0.500378677095937 }
waterman14
{ 464001
0.500348716358563 }
borosh13
{ 465001
0.50035710505251 }
coveyou
{ 466001
0.500350425372611 }
fishman20
{ 467001
0.500360809667737 }
^C+++Interruption

JKB
Pascal J. Bourguignon (20/05/2010, 07h59)
Jérôme Benoit <jerome.benoit> writes:

> Le Wed, 19 May 2010 10:09:14 +0200, Pascal J. Bourguignon a écrit :
> C'est un pur :)
>> Je me demande par pure curiosité intellectuelle ce que çà donnerait en

> mixant plusieurs source de PRNG ... en haskell c'est facilement
> implémentable avec Random.split.


Avec la fonction rand() de unix:

(loop for i from 0 to 1e6 sum (/ (linux:random) 2147483648.0) into s
do (case i ((10 100 1000 10000 100000 1000000)
(print (list i (/ s i))))))
-->
(10 0.6423787)
(100 0.5499566)
(1000 0.5072906)
(10000 0.49707523)
(100000 0.49986368)
(1000000 0.50000274)
NIL

Mais ça ne veut rien dire, on obtient aussi des séquences comme:

-->
(10 0.4914257)
(100 0.51135695)
(1000 0.5026758)
(10000 0.49963745)
(100000 0.49932718)
(1000000 0.4999366)
NIL

Il y a des livres entiers sur l'analyse des pseudo-aléatoires.
xtof.pernod (20/05/2010, 13h21)
> Le 19-05-2010, à propos de
> Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),
> Jérôme Benoit ?crivait dans fr.comp.algorithmes :


C'est vrai que c'est court et élégant..

Mais ça donne pas de réponse à la question -- au demeurant
fort mal posée, je reconnais, j'ai un mal de chien..


Le 19/05/2010 23:05, JKB a fait rien qu'à écrire :

> #!/usr/local/bin/rpl -scp
> (...)


la vaaache.. j'ai rien compris.

> ...
> random8_libc5
> { 361001
> 0.500055614694412 }
> ...


(...)

Qu'est-ce tu voulais montrer ? que tes prng tendent tous
vers 1/2, avec une précision de 3 ou 4 décimales ?..

> fishman20
> { 467001
> 0.500360809667737 }
> ^C+++Interruption


Tiens, ça a l'air marrant, le ctrl-C-plus-plus-plus.
Est-ce que ça corrige les défauts de la version précédente ?

Est-ce que ça 'tricrémente' la variable (incrément, bicrément, ...) spécifiée ?

</mode troll=off>
JKB (20/05/2010, 14h01)
Le 20-05-2010, ? propos de
Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),
xtof.pernod ?crivait dans fr.comp.algorithmes :
> Le 19/05/2010 23:05, JKB a fait rien qu'à écrire :
>> la vaaache.. j'ai rien compris.
>> (...)

> Qu'est-ce tu voulais montrer ? que tes prng tendent tous
> vers 1/2, avec une précision de 3 ou 4 décimales ?..


Je voulais juste gagner le concours ;-)

>> fishman20
>> { 467001
>> 0.500360809667737 }
>> ^C+++Interruption

> Tiens, ça a l'air marrant, le ctrl-C-plus-plus-plus.
> Est-ce que ça corrige les défauts de la version précédente ?


Naon !... C'est un SIGINT envoyé depuis le clavier et le programme
répond : "+++Interruption". Faudrait voir à suivre un peu !
[..]
xtof.pernod (20/05/2010, 15h32)
Le 20/05/2010 14:01, JKB a fait rien qu'à écrire :
> Le 20-05-2010, ? propos de
> Re: Chuck Norris est déja allé à Toire (Fût: Re: Question hyper-basique),
> xtof.pernod écrivait dans fr.comp.algorithmes :
>> Le 19/05/2010 23:05, JKB a fait rien qu'à écrire :
>> (...)
>>> #!/usr/local/bin/rpl -scp


Désolé, nous ne faisons pas cet article n'est pas en stock.

>> (...)
>> Qu'est-ce tu voulais montrer ? que tes prng tendent tous
>> vers 1/2, avec une précision de 3 ou 4 décimales ?..

> Je voulais juste gagner le concours ;-)


Hein ?! quel concours ?
Pinaise, on me dit jamais rien à moi..

> Naon !... C'est un SIGINT envoyé depuis le clavier et le programme
> répond : "+++Interruption". Faudrait voir à suivre un peu !


Quel programme ? Le tien, où y'a pas 1 gramme de gestion de signaux,
ou l'interpréteur de language de type "write-only", style Liste Infinie
de Stupides Parenthèses [traduction approx. & à l'arrache de :
"Lot of Insipid and Stupid Parenthesis", c'est pas moi kill édit]

<mode je_me_fais_des_amis = "off" />

>> (...)
>>> JKB

Naaaan, je déc*nne ..... Respect à tous les languages que les
machines daignent avaler, pour peu qu'elles soyent à peu près
bien programmées.
JKB (20/05/2010, 16h03)
Le 20-05-2010, ? propos de
Re: Super-fête à Toire (Fût: Re: Question hyper-basique),
xtof.pernod ?crivait dans fr.comp.algorithmes :
> Le 20/05/2010 14:01, JKB a fait rien qu'à écrire :
> Désolé, nous ne faisons pas cet article n'est pas en stock.
> Pinaise, on me dit jamais rien à moi..
> ou l'interpréteur de language de type "write-only", style Liste Infinie
> de Stupides Parenthèses [traduction approx. & à l'arrache de :
> "Lot of Insipid and Stupid Parenthesis", c'est pas moi kill édit]


C'est un _compilateur_, et j'aime assez ce genre de langage
'write-only'.

><mode je_me_fais_des_amis = "off" />


Gagné :-P

>>> (...)
>>>> JKB

> Naaaan, je déc*nne ..... Respect à tous les languages que les
> machines daignent avaler, pour peu qu'elles soyent à peu près
> bien programmées.


C'est pour ça que j'utilise _mes_ bugs et pas ceux des autres. J'ai
assez fait dans ma vie de bugs reports pour arrêter de jouer avec
ça.

JKB
Joe Cool (26/05/2010, 20h47)
Paul Gaborit a écrit :
> J'attends donc toujours le nom de l'agorithme de tri qui réponde aux
> exigences de Joe Cool et qui garantisse un ordre final aléatoire et
> équiréparti si on lui fournit une fonction de comparaison totalement
> aléatoire.


Déjà fait. Lisez l'historique du newsgroup.

Mais je me doute bien que même si je vous le mettais sous le
nez, vous prétendriez ne pas l'avoir vu. Alors je ne me fatiguerai
pas pour vous.
Joe Cool (26/05/2010, 20h49)
Paul Gaborit a écrit :
> Un flux réellement aléatoire n'est que rarement bien réparti...


Alors qu'on flux qui n'est pas aléatoire a plus de chance de l'être...
Joe Cool (26/05/2010, 20h54)
Paul Gaborit a écrit :
> Prenons l'exemple d'une pièce de monnaie. Il est très rare qu'une série
> de tirages comporte autant de pile que de face. Et si on regarde combien
> de fois on revient à l'équilibre, on s'aperçoit que plus on augmente le
> nombre de tirages et plus la fréquence de retour à l'équilibre
> diminue...


Les probabilités sont basées sur les rapports de mesures, pas sur les
mesures absolues. Ce que vous dites est aussi vrai que stupide, sauf
sur un point: ce n'est pas la fréquence de retour à l'équilibre qui
diminue, mais la fréquence de retour à l'origine.
Joe Cool (26/05/2010, 20h58)
Paul Gaborit a écrit :
> Joe Cool <zierouhli> écrivait (wrote):
>> Cf. la discussion sur le sujet. Tous les arguments y sont présentés.

> Dea arguments sont certes présentés mais sans aucune référence ni même
> esquisse de preuve...


Pas de bol: les esquisses sont là; mais il faut vouloir les lire et pouvoir
les comprendre. Évidemment, on ne peut pas faire boire un âne qui n'a pas soif...

> Et les contre-exemples n'ont pas été examinés (ni
> même peut-être compris).


En effet, les auteurs des «contre-exemples» n'ont rien compris.
Joe Cool (26/05/2010, 21h02)
Jérôme Benoit a écrit :
> Je vais en citer une ... de contre-référence :
> [..]
> Mais est-ce bien raisonnable de ma part ? ;-)


Non, ce n'est pas raisonnable. Cette «référence» a été citée dans
la discussion initiale et j'y ai répondu comme il se doit.

En résumé, le «calcul» douteux effectué par l'auteur du blog montre:
- soit que l'implémentation du tri testé est foireuse, ce qui ne remet
pas en cause la méthode, seulement la tentative de l'utiliser;
- soit que les outils statistiques utilisés sont foireux, ce qui remet
en cause la rigueur et l'intérêt de votre source.

Des calculs pseudo-aléatoires... Mais les preuves, où sont-elles?
Savent-ils au moins ce qu'est une preuve?
xtof.pernod (27/05/2010, 02h16)
Le 26/05/2010 20:58, Joe Cool a fait rien qu'à écrire :
> Paul Gaborit a écrit :
>> Joe Cool <zierouhli> écrivait (wrote):

^^^^^^^^
Tiens, t'es là, toi ?... Tu manquais pas.

T'en as fini, avec les goto, les maths, ta science infuse etc ?

>>> Cf. la discussion sur le sujet. Tous les arguments y sont présentés.

>> Dea arguments sont certes présentés mais sans aucune référence ni même
>> esquisse de preuve...

> Pas de bol: les esquisses sont là;

^^
Où ça, exactement ? Là ? ------------------->
Ta précision est aussi grande que ta modestie.

> mais il faut vouloir les lire et pouvoir
> les comprendre. Évidemment, on ne peut pas faire boire un âne qui n'a
> pas soif...


En clair: "Je dis que la preuve existe, dém**dez vous pour
la trouver, sinon c'est que vous être trop c*ns".

Qu'est-ce que c'est constructif..

Sur sa copie, Jo Cool à mis : "Je sais q'une preuve existe".
Son professeur de maths lui a mis 20 (+ O(1)).

>> Et les contre-exemples n'ont pas été examinés (ni
>> même peut-être compris).

> En effet, les auteurs des «contre-exemples» n'ont rien compris.


héééé oui... dure leçon de la vie, petit: "Seul JC a tout compris".

[Le pire, c'est qu'il y a un début de preuve de l'existence
d'un algo. qui utilise un tri en O(N) pour mélanger un tableau.
mais c'est tellement crétin que personne n'osera le faire.]

Discussions similaires
Question basique

question basique

php: question basique

Question basique


Fuseau horaire GMT +2. Il est actuellement 06h25. | Privacy Policy