Newsgroup: it.comp.lang.c
Titolo: multiply carry?

Mi sono "informato" finalmente sul funzionamento dei generatori
pseudocasuali, qui all'inizio vedete un po' le informazioni raccolte.
http://github.com/AndreaCrotti/Razz/blob/master/README.org
Ho anche capito che in C:
- rand() è sconsigliata
- lrand48() usa le congruenze lineari
- random() usa un metodo additivo (non ho ben capito quale) ed è molto
  più veloce di lrand48.
Dunque ora
1. vorrei capire se implementando qualche altro algoritmo (multiply and
   carry ad esempio) si potrebbero avere performances ancora migliori o
   se non ne vale la pena.
2. vorrei trovare una buona spiegazione per me stesso del fatto che
   quello che faccio è corretto.
   In sostanza dato un mazzo, invece di mescolare ogni volta swappo la
   carta estratta a caso con l'ultima e diminuisco la lunghezza.
   Ora è vero che ad ogni turno ogni carta ha la stessa probabilità di
   essere estratta, ma è anche vero che a ogni turno cambio le carte in
   tavola.
 
   In realtà sono sicuro al 99% che funzioni comunque benissimo questo
   sistema, ma non riesco a capire il perché...
Grazie mille..
Andrea

    In sostanza dato un mazzo
io in genere le carte le mischio così:
for( i = 0; i < 10000; i++ ) { swap( carte[ rand()%40 ], carte[ rand()
%40] ); }
forse basta anche meno di 10000 per definire un mazzo ben mischiato,
non ho mai fatto i test per bene..
Saluti
Iscriviti anche tu al gruppo sociale "Difendiamo rand() dalle
discriminazioni"
:)


Io non lo mescolo proprio, pesco a caso, lo accorcio e ripesco a caso.
A nuova partita risposto, è stata apparentemente un'ottima idea...
Mi permette di fare 4*10^7 pescate in 0.8 secondi.

 higher-order bits ? 
Non solo, ma anche perche' il periodo puo' essere molto corto (sempre nel 1600 :) era magari di 2^16).
Ovvio poi che dipende dall'applicazione, in molte rand() non va bene per niente (senza tirare in ballo la crittografia, dove usare rand() e' come usare 
questa 
http://xkcd.com/221/
 :) , anche in simulazioni scientifiche, algoritmi montecarlo eccetera rand() ha in genere un periodo troppo corto).
Poi, se ti serve qualche numero e non ti servono chissa' quali proprieta' statistiche, andra' benissimo.
Ma ad es. per il problema di Andrea, mi par di capire che lui generi parecchi numeri casuali (miliardi e piu'?)  In questo caso, avere un periodo di solo 
2^32 potrebbe non essere sufficiente per lui (ma tutti gli algoritmi che ha proposto hanno quel periodo, perche' usano int, magari gli va bene, deve valutare 
lui).
Pleg

 non ho mai fatto i test per bene..
Il metodo che proponi quasi certamente non d� una distribuzione uniforme 
delle carte ed � 10000 volte meno efficiente di quello proposto dall'OP.
E.

    carta estratta a caso con l'ultima e diminuisco la lunghezza.
Cosa potrebbe convincerti che un mazzo è mescolato a caso? Ti torna che 
la prima carta può essere una qualunque con probabilità 1/52? Ti torna 
che la seconda carta estratta è una qualunque delle rimanenti con 
probabilità 1/51?
Comunque se ti interessa discutere più in dettaglio questo punto, ti 
consiglio di scrivere su it.scienza.matematica
E.


Tornare mi torna, è solo che mi sembra un po' troppo magico :D
Comunque dopo essere riuscito a generare effettivamente tutte le
possibili partite sono più sicuro (qualcuno diceva fosse un'idea
stupida..).
Questo semplicissimo codice
--8<---------------cut here---------------start------------->8---
def all_cards(init):
    """Generate ALL the possible combinations and
    find the REAL probabilities given"""
    d = Deck(DECK_CARDS)
    d.remove(init)
    ranks = {}
 
    count = 0
    for hand in combinations(d.cards, 4):
        count += 1
        h = RazzHand(list(hand) + init[:3])
        got_rank = h.rank()
        if ranks.has_key(got_rank):
            ranks[got_rank] += 1
        else:
            ranks[got_rank] = 1
 
    return ranks, count
 --8<---------------cut here---------------end--------------->8---
Date alcune carte iniziali,
- le toglie dal mazzo
- genera tutte le possibili combinazioni delle 4 carte restanti
- calcola il ranking
da qui
http://github.com/AndreaCrotti/Razz/blob/master/theory.py
Ora con questo ho potuto verificare veramente il mio programma, usando
la norma della differenza tra il risultato teorico e quello vero, e in
effetti funziona ;)
Comunque l'esame è fatto quindi in teoria non lo toccherò più, ma magari
potrei pubblicarlo come esempio di ottimizzazione estrema dove il
random() è il collo di bottiglia (60% del tempo).