C++; lib.
Eccomi ancora qua con c++; ci riprovo anche se questa volta lo sto facendo più seriamente.
Arrivo subito al dunque.
Vorrei iniziare a creare le mie funzioni che effettuano dei calcoli che devo eseguire molto frequentemente.
Per farvi capire cosa mi serve faccio un esempio pratico: devo poter richiamare agevolmente funzioni di densità di varie distribuzioni. L'idea è quella di scrivere un po' di funzioni tipo:
double pdf_Binom (int x, int n, double p)
{
}
e lo stesso per altre.
Dove devo andare a mettere tutte queste cosette? In una libreria credo.
Quindi come la creo? Dove la salvo? Come la richiamo? (Uso Linux)
Ci sono delle librerie standard già implementate? (ovviamente saranno state create)
A proposito di binomiale avete qualche idea di come fare il coefficiente binomiale
vi sembra corretta questa strutturazione.
Infine come generate numeri casuali da una uniforme (0,1)?
binomiale
Poi ho visto ogni tanto fare una cosa del tipo:
srand( non ricordo)
per settare il seme; ma è necessario; se si quando va fatto?
Grazie, buon pranzo
Arrivo subito al dunque.
Vorrei iniziare a creare le mie funzioni che effettuano dei calcoli che devo eseguire molto frequentemente.
Per farvi capire cosa mi serve faccio un esempio pratico: devo poter richiamare agevolmente funzioni di densità di varie distribuzioni. L'idea è quella di scrivere un po' di funzioni tipo:
double pdf_Binom (int x, int n, double p)
{
}
e lo stesso per altre.
Dove devo andare a mettere tutte queste cosette? In una libreria credo.
Quindi come la creo? Dove la salvo? Come la richiamo? (Uso Linux)
Ci sono delle librerie standard già implementate? (ovviamente saranno state create)
A proposito di binomiale avete qualche idea di come fare il coefficiente binomiale
double Binomial_Coefficient (int n, int k)
{
double x = 0;
double y = 0;
double z;
if ( (k>-1) && (n>=k) )
{
for(int i=n-k+1; i<n+1; i++) { x = x + log(i) }
for(int i=2; i<k+1; i++) { y = y + log(i) }
z = exp(x-y);
}
else
{
z = 0;
cout << "input error \n";
}
return z;
}
vi sembra corretta questa strutturazione.
Infine come generate numeri casuali da una uniforme (0,1)?
binomiale
double Uniform_Generator ()
{
double x = rand() / double(RAND_MAX);
return x;
}
Poi ho visto ogni tanto fare una cosa del tipo:
srand( non ricordo)
per settare il seme; ma è necessario; se si quando va fatto?
Grazie, buon pranzo
Risposte
Usa Boost Random. Per scaricare e usare boost (che è un insieme di librerie in C++ molto diffuse e usate) puoi leggerti le istruzioni presenti in questa pagina del manuale online o verificare se la tua distribuzione fornisce già dei pacchetti per questa libreria (potrebbero anche essere già installati se in alcune distro hai chiesto di installare gli strumenti di sviluppo per il C++).
Ciao DajeForte 
,
ma che proprietà matematica utilizzi per calcolare il coefficiente binomiale?
I tipi degli operatori non sono appropriati, perchè penso tu sappia che ci sono limitazioni sul numero calcolabile imposti dal calcolatore, ed ogni tipo ha un limite.
,"DajeForte":
A proposito di binomiale avete qualche idea di come fare il coefficiente binomiale
double Binomial_Coefficient (int n, int k) { double x = 0; double y = 0; double z; if ( (k>-1) && (n>=k) ) { for(int i=n-k+1; i<n+1; i++) { x = x + log(i) } for(int i=2; i<k+1; i++) { y = y + log(i) } z = exp(x-y); } else { z = 0; cout << "input error \n"; } return z; }
vi sembra corretta questa strutturazione.
ma che proprietà matematica utilizzi per calcolare il coefficiente binomiale?
I tipi degli operatori non sono appropriati, perchè penso tu sappia che ci sono limitazioni sul numero calcolabile imposti dal calcolatore, ed ogni tipo ha un limite.
@apatriarca: grazie della risposta. Si boost non è la prima volta che la sento ed è molto diffusa; adesso la installo anche se dovrò comunque imparare a scrivere pacchettini per conto mio visto che la generazione è una parte soltanto delle applicazioni comuni che devo fare.
@ham_burst: Ciao
Risolti i tuoi problemi con le variabili aeatorie. Spero di si altrimenti posta manda un PM quando vuoi!
Veniamo a queo che dici: intendi che i double non sono appropriati lo penso anche io però non so cosa metterci. long int ?
L'idea era quella di costruire una funzione che calcolasse i fattoriale che però ancora non ho fatto proprio perchè il fattoriale diventa subito enorme e quindi mi ero arenato in attesa di aumentare la mia conoscenza.
Allora sono andato sul coefficiente binomiale che va più piano del fattoriale e per calcolarlo ho fatto così:
usando $x=exp(log(x))$ (x>0) allora $((n),(k))=exp(log((n!)/((n-k)!)-log(k!))$
e $log(n!)=sum_{i=2}^n log(i)$
@ham_burst: Ciao
Risolti i tuoi problemi con le variabili aeatorie. Spero di si altrimenti posta manda un PM quando vuoi!Veniamo a queo che dici: intendi che i double non sono appropriati lo penso anche io però non so cosa metterci. long int ?
L'idea era quella di costruire una funzione che calcolasse i fattoriale che però ancora non ho fatto proprio perchè il fattoriale diventa subito enorme e quindi mi ero arenato in attesa di aumentare la mia conoscenza.
Allora sono andato sul coefficiente binomiale che va più piano del fattoriale e per calcolarlo ho fatto così:
usando $x=exp(log(x))$ (x>0) allora $((n),(k))=exp(log((n!)/((n-k)!)-log(k!))$
e $log(n!)=sum_{i=2}^n log(i)$
"DajeForte":
@ham_burst: Ciao
grazie dell'interessamento, ho messo da parte per qualche settimana probabilità, per affrontare un esame, perciò ritornerò a porre domande tra non molto
Veniamo a queo che dici: intendi che i double non sono appropriati lo penso anche io però non so cosa metterci. long int ?
non ti ho scritto altro su questo, perchè volevo vedere che tipo di proprietà hai utilizzato.
L'idea era quella di costruire una funzione che calcolasse i fattoriale che però ancora non ho fatto proprio perchè il fattoriale diventa subito enorme e quindi mi ero arenato in attesa di aumentare la mia conoscenza.
Allora sono andato sul coefficiente binomiale che va più piano del fattoriale e per calcolarlo ho fatto così:
usando $x=exp(log(x))$ (x>0) allora $((n),(k))=exp(log((n!)/((n-k)!)-log(k!))$
e $log(n!)=sum_{i=2}^n log(i)$
[/quote]
L'unico modo per calcolare il fattoriale è un ciclo for con moltiplicazione, costo $O(n)$. Con limitazione sul numero. Io non ne conosco altri, non penso che si possano fare ulteriori ottimizzazioni.
Si può oltrepassare il limite dato dal calcolatore, utilizzando classi apposite come BigInteger.
Per il binomiale, interessante.
I problemi però sono dovuti, che te sfori nei reali limitando il numero al logaritmo. Questo sforamento comporta l'utilizzo dei double, che hanno una strutturazione interna particolare (floating point), che limita ancora di più il numero rappresentabile (intero tipizzato reale). Qua poi ci sono problemi dovuti all'approssimazione del numero reale e tante altre cose
Qua ci sarebbe da fare un po' di analisi degli algoritmi, ma ti propongo un'alternativa così da non limitare il numero rappresentabile dovuto ai double.
Perchè allora non utilizzare direttamente la definzione di coefficiente binomiale sugli interi, penso che saprai meglio di me, che un'altra definizione del coefficiente binomiale utilizza il triangolo di tartaglia e questa struttura ricorsiva:
$C(n,k) = {(1,if k=0 vv n=k),(C(n-k;k-1) + C(n-1;k),other):}$
Qua si può strutture il tutto con un algoritmo o ricorsivo o che memoriazza i vari risultati che puoi accedere quando vuoi, salvandoli o su file o in memoria.
Quello ricorsivo è banalmente inefficiente, ma ti da UN risultato e basta, ogni volta che calcolareai un numero lo dovrai rifare richiamando la funzione.
Visto che hai scritto che riutilizzerai le funzioni in un secondo momento, meglio salvarsi tutti i dati direttamente ed accessibili in un secondo momento. perciò utilizzare una struttura esterna, tipo una matrice (con tutti gli accorigimeni del caso):
Bin(integer n,integer[][] C){
for integer i<-0 to n do
C[i,0] <- 1
C[i,i] <- 1
for integer i<- 2 to n do
for integer j <- 1 to i-1 do
C[i,j] <- C[i-1,j-1] + C[i-1,j]
}
Questo funziona perchè riutilizzi dati già calcolati in precedenza, come da definizione e non serve ricalcolarli perchè salvati in posizioni minori (cosa che fa la versione ricorsiva).
il costo sarà $O(n^2)$ in spazio $O(n^2)$. Le ottimizzazioni dipendono dall'utilizzo che ne fai
allocando C[][] in esterno potrai accedere al binomiale $((n),(k))$ attraverso l'accesso diretto a C con $C[n][k]$ ed a tutti i valori inferiori ad essi.
Ora dipende dall'utilizzo, se lo specifichi ti si dice anche i tipi corretti o se usare un altro algoritmo
Come detto il tuo algoritmo anche se è $O(n)$ è limitato da errori di approssimazione e dai tipi.
PS: Comunque penso che esista una funzione in qualche libreria che calcola il coefficiente binomiale
Grazie ancora della risposta.
Allora non ho ancora uno scopo ben preciso; la necessità di calcolare quel coefficiente nasce dalla volontà di impratichirsi con c++.
Dunque dopo aver visto un po' di teoria (poca poca) ho deciso di iniziare a fare qualche programmino e funzioncina. La prima idea è stata: costruisco un po' di funzioni di probabilità di differenti distribuzioni e sono partito proprio dalla binomiale.
Queste distribuzioni poi saranno alla base di altri programmi più complessi i quali utilizzeranno queste distribuzioni.
Ad esempio mi servirà prezzare un'opzione con il modello binomiale e quindi mi dovrà servire una distribuzione binomiale; oppure mi potrà servire una distribuzione di Poisson per creare un processo jump-diffusion; oppure una distribuzione normale per un moto browniano.
Come diceva apatriarca e come ritengo oivvio, essendo cose molto comuni, esisteranno librerie pronte per eseguirli.
Ora quindi la mia finalità (ad esempio per il coefficiente binomiale, o le varie distribuzioni) è nel crearmi una base di funzioni stastistiche sottostanti che mi permettano di effettuare tutti i calcoli probabilistici che mi servono.
Parallelamente a questo c'è anche una finalità di apprendimento sottostante: ovvero queste funzioni mi servono anche per apprendere e per imparare in via diretta a programmare. In quest'ottica queste funzioni non me le dovrò tenere a vita ma tra un anno, diciamo, avendo imparato a programmare con c++ essere in grado di trovare strade efficiente per effettuare i calcoli. Ad esempio invece che prendermi un coefficiente binomiale già fatto ma averlo creato e postato mi hai fatto notare alcune problematiche sulle quali riflettero...cercando di dedurne qualcosa.
Ad esempio io uso quasi sempre le variabili double e int e diciamo che questa non è una cosa molto buona.
Veniamo al dunque. Nel programma che ho scritto mi dici che utilizza double che limita il numero. Potrei sostituire il double nella definizione (e nella z) con int?
Poi dici che c'è un problema di approssimazione in che senso, che log ed esponenziale con approssimazioni mi potrebbe restituire un numero non intero?
int z = exp(x-y+0.1); è una zozzata fare una cosa del genere?
Tu poi proponi tartaglia; che però giustamente deve calcolare un sacco di roba prima di arrivare al risultato.
Infine arrivi al salvare questo non ci avevo pensato, potrebbe ritornare utile.
C'è ancora un po' da riflettere, ci penso su ancora un po...comunque grazie ancora.
Allora non ho ancora uno scopo ben preciso; la necessità di calcolare quel coefficiente nasce dalla volontà di impratichirsi con c++.
Dunque dopo aver visto un po' di teoria (poca poca) ho deciso di iniziare a fare qualche programmino e funzioncina. La prima idea è stata: costruisco un po' di funzioni di probabilità di differenti distribuzioni e sono partito proprio dalla binomiale.
Queste distribuzioni poi saranno alla base di altri programmi più complessi i quali utilizzeranno queste distribuzioni.
Ad esempio mi servirà prezzare un'opzione con il modello binomiale e quindi mi dovrà servire una distribuzione binomiale; oppure mi potrà servire una distribuzione di Poisson per creare un processo jump-diffusion; oppure una distribuzione normale per un moto browniano.
Come diceva apatriarca e come ritengo oivvio, essendo cose molto comuni, esisteranno librerie pronte per eseguirli.
Ora quindi la mia finalità (ad esempio per il coefficiente binomiale, o le varie distribuzioni) è nel crearmi una base di funzioni stastistiche sottostanti che mi permettano di effettuare tutti i calcoli probabilistici che mi servono.
Parallelamente a questo c'è anche una finalità di apprendimento sottostante: ovvero queste funzioni mi servono anche per apprendere e per imparare in via diretta a programmare. In quest'ottica queste funzioni non me le dovrò tenere a vita ma tra un anno, diciamo, avendo imparato a programmare con c++ essere in grado di trovare strade efficiente per effettuare i calcoli. Ad esempio invece che prendermi un coefficiente binomiale già fatto ma averlo creato e postato mi hai fatto notare alcune problematiche sulle quali riflettero...cercando di dedurne qualcosa.
Ad esempio io uso quasi sempre le variabili double e int e diciamo che questa non è una cosa molto buona.
Veniamo al dunque. Nel programma che ho scritto mi dici che utilizza double che limita il numero. Potrei sostituire il double nella definizione (e nella z) con int?
Poi dici che c'è un problema di approssimazione in che senso, che log ed esponenziale con approssimazioni mi potrebbe restituire un numero non intero?
int z = exp(x-y+0.1); è una zozzata fare una cosa del genere?
Tu poi proponi tartaglia; che però giustamente deve calcolare un sacco di roba prima di arrivare al risultato.
Infine arrivi al salvare questo non ci avevo pensato, potrebbe ritornare utile.
C'è ancora un po' da riflettere, ci penso su ancora un po...comunque grazie ancora.
Siccome la memoria dei nostri computer è finita, finito è anche il numero massimo di simboli, in questo caso numeri, che possiamo rappresentare. I tipi primitivi, essendo di dimensioni fissa, sono particolarmente limitati in questo senso. È infatti possibile scrivere dei programmi che facciano calcoli con interi molto grandi, nell'ordine anche di milioni di cifre, ma questi valori non potremmo certamente inserirli negli int, long int, long long int o quant'altro che ci fornisce il C++. Per raggiungere numeri più grandi è necessario quindi ricorrere a librerie particolari o definire dei tipi e delle funzioni particolari per permetterti di fare questo genere di operazioni. Questa seconda soluzione non è molto pratica, soprattutto se si ha poca esperienza con la programmazione in generale e con il C++ in particolare*. Per decidere quindi come implementare la tua funzione è allora necessario decidere quali sono gli scopi:
1. Se decidi di aver bisogno solo di numeri relativamente piccoli dei long int o long long int potrebbero essere abbastanza grandi da contenere i risultati.
2. Se un certo errore nel risultato può essere ritenuto accettabile, i double potrebbero essere una soluzione. Un double rappresenta il numero nella forma segno + esponente + mantissa, tutti rappresentabili con un numero finito di bit. Facendo un esempio, supponendo che il tipo double sia basato su cifre decimali e possa rappresentare due cifre di esponente e \(4\) di mantissa, il numero \(123456\) verrebbe approssimato da \(1235 * 10^2\), cioè \(123500\). Questo è più o meno quello che succede con i grandi numeri usando i double. Tutti gli interi fino a \(2^{53}\) (se non ricordo male) possono comunque essere rappresentati esattamente. Andando oltre questa cifra si ha un errore maggiore di una unità, ma si possono arrivare fino a numeri nell'ordine di \(2^{1024}\).
3. Se necessiti di calcoli esatti, devi fare ricorso a librerie particolari.
Che libro/guida/tutorial stai seguendo per imparare il C++? Il C++ è poco adatto ad essere imparato come autodidatta.
* Esistono in effetti linguaggi, come Haskell che forniscono questo genere di funzionalità. È infatti possibile ad esempio implementare il fattoriale e poi calcolarsi il fattoriale di 222 senza grossi problemi (questa è una piccola sessione con l'interprete ma può anche essere compilato):
1. Se decidi di aver bisogno solo di numeri relativamente piccoli dei long int o long long int potrebbero essere abbastanza grandi da contenere i risultati.
2. Se un certo errore nel risultato può essere ritenuto accettabile, i double potrebbero essere una soluzione. Un double rappresenta il numero nella forma segno + esponente + mantissa, tutti rappresentabili con un numero finito di bit. Facendo un esempio, supponendo che il tipo double sia basato su cifre decimali e possa rappresentare due cifre di esponente e \(4\) di mantissa, il numero \(123456\) verrebbe approssimato da \(1235 * 10^2\), cioè \(123500\). Questo è più o meno quello che succede con i grandi numeri usando i double. Tutti gli interi fino a \(2^{53}\) (se non ricordo male) possono comunque essere rappresentati esattamente. Andando oltre questa cifra si ha un errore maggiore di una unità, ma si possono arrivare fino a numeri nell'ordine di \(2^{1024}\).
3. Se necessiti di calcoli esatti, devi fare ricorso a librerie particolari.
Che libro/guida/tutorial stai seguendo per imparare il C++? Il C++ è poco adatto ad essere imparato come autodidatta.
* Esistono in effetti linguaggi, come Haskell che forniscono questo genere di funzionalità. È infatti possibile ad esempio implementare il fattoriale e poi calcolarsi il fattoriale di 222 senza grossi problemi (questa è una piccola sessione con l'interprete ma può anche essere compilato):
Prelude> let factorial n = product [1..n] factorial :: (Num a, Enum a) => a -> a (0.00 secs, 5756424 bytes) Prelude> factorial 222 112050755800644139182824657874288503316182344836201072566418066442575170654489 604988455473085891233152722255158215820835509118567770425555664949954615083500 304129450159283620378895008790288025331140066449564826484508657579315925606917 480955013780196392370141851418465252049263944145260911871147445328203745168510 368854915637280099588264866194322947975660549095765165693992960000000000000000 0000000000000000000000000000000000000 it :: Integer (0.00 secs, 2193740 bytes)
Esistono algoritmi efficienti per calcolare il fattoriale, ma ovviamente come ti hanno già detto tutto dipende dallo scopo: se ti accontenti dei long int, se ti serve una rappresentazione arbitrariamente grande, eccetera.
Non conosco - e non ho trovato - progetti "standard" diciamo così di librerie siffatte, anche se si trovano molte implementazioni che sembrano interessanti.
(Un'occhiata al codice di R magari?
)
Non conosco - e non ho trovato - progetti "standard" diciamo così di librerie siffatte, anche se si trovano molte implementazioni che sembrano interessanti.
(Un'occhiata al codice di R magari?
)
Grazie a tutti e due domani.
@apatriarca: domani rileggo cosa hai scritto che ora sono troppo fuso per apprendere.
@apatriarca: domani rileggo cosa hai scritto che ora sono troppo fuso per apprendere.
@apatriarca: Grazie.
Allora mi sono un minimo documentato e da qualche prova ho capito che il range dei numeri segue questo schema:
http://www.cplusplus.com/doc/tutorial/variables/
Inanzitutto il long int e int pare abbiano la stessa capicità; con il long long aumenta.
Credo dunque di aver anche capito quello che dite con l'idea di scopo: secondo le finalità si potranno seguire diverse strategie con una idea che meno precisione più efficenza.
Allra partiamo dalla grandezza; in generale non credo mi serviranno numeri molto elevati
ad esempio $((50),(25))$ ha 15 cifre; R mi ritorna per questo 1.264106e+14
$((100),(50))$ ha 30 cifre; R mi ritorna per questo 1.008913e+29
Come dice Rggb cercherò di dare una sbirciata a R anche se credo sarà difficile arrivare a comprendere come viene strutturata questa funzione.
Ora credo dunque di accettare un margine di errore e quindi seguire quello che dici nel punto due e poi cercherò di fare qualche prova per capire che errore commetto.
A questo punto ti chiedo se la strutturazione che gli ho dato io ti sembra corretta (magari cambiando la definizione con long long int? però così facendo se sforo sballo tutto).
Mi vergogno a dirtelo ma sto facendo l'autodidatta con la libertà di guardare qua e la per reperire informazioni qualora sorga un problema. Ho qua accanto a me lo Stroustrup ma lo uso per guardare appunto quando c'è un problema cosa fare. Risultato: non ne ho mai ricavato niente; credo sia un libro che debba essere lettere un po' tutto per carci qualcosa.
Ora vado a vedere nella sezioni di appunti e dispense; te/voi avresti qualche cosa da consigliare?
Grazie ancora ciao.
Allora mi sono un minimo documentato e da qualche prova ho capito che il range dei numeri segue questo schema:
http://www.cplusplus.com/doc/tutorial/variables/
Inanzitutto il long int e int pare abbiano la stessa capicità; con il long long aumenta.
Credo dunque di aver anche capito quello che dite con l'idea di scopo: secondo le finalità si potranno seguire diverse strategie con una idea che meno precisione più efficenza.
Allra partiamo dalla grandezza; in generale non credo mi serviranno numeri molto elevati
ad esempio $((50),(25))$ ha 15 cifre; R mi ritorna per questo 1.264106e+14
$((100),(50))$ ha 30 cifre; R mi ritorna per questo 1.008913e+29
Come dice Rggb cercherò di dare una sbirciata a R anche se credo sarà difficile arrivare a comprendere come viene strutturata questa funzione.
Ora credo dunque di accettare un margine di errore e quindi seguire quello che dici nel punto due e poi cercherò di fare qualche prova per capire che errore commetto.
A questo punto ti chiedo se la strutturazione che gli ho dato io ti sembra corretta (magari cambiando la definizione con long long int? però così facendo se sforo sballo tutto).
"apatriarca":
Che libro/guida/tutorial stai seguendo per imparare il C++? Il C++ è poco adatto ad essere imparato come autodidatta.
Mi vergogno a dirtelo ma sto facendo l'autodidatta con la libertà di guardare qua e la per reperire informazioni qualora sorga un problema. Ho qua accanto a me lo Stroustrup ma lo uso per guardare appunto quando c'è un problema cosa fare. Risultato: non ne ho mai ricavato niente; credo sia un libro che debba essere lettere un po' tutto per carci qualcosa.
Ora vado a vedere nella sezioni di appunti e dispense; te/voi avresti qualche cosa da consigliare?
Grazie ancora ciao.
Non sembra che R restituisca i valori corretti, nel senso che restituisce una loro approssimazione (che sembrerebbe addirittura basata sui float - o forse semplicemente stampa solo pochi valori per renderli più facilmente stampabili). Personalmente non credo molto che ci siano dei vantaggi nell'usare il tuo metodo. Devi infatti comunque fare lo stesso numero di cicli della soluzione basata sulla definizione e devi poi ricorrere a funzioni come l'esponenziale e il logaritmo. È secondo me a questo punto meglio usare l'identità
\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{\prod_{i = \max(k, n-k) + 1}^n i}{\min(k, n-k)!} \]
oppure calcolare e memorizzare tutti i valori del binomiale fino al valore massimo che ti serve usando il triangolo di tartaglia e poi ottenere il valore leggendolo da questa tabella. Questa soluzione richiede un po' di spazio, ma per numeri relativamente piccoli non è neanche molto (una matrice 1024x1024 di double occupa 8 MB che non è poi molto vista la dimensione delle memorie attuali*). Ma per valori molto grandi usando i double potrebbe ad un certo punto essere conveniente fare ricorso ad un'approssimazione asintotica del binomiale. Usando infatti sia la definizione che il triangolo di tartaglia si finirebbe presto a sommare errori di approssimazione sempre più grandi ottenendo valori sempre più imprecisi. Per fare un esempio. Ho calcolato \(\binom{2n}{n}\) usando prima gli Integer e poi i double in haskell e poi ho fatto ricorso all'approssimazione \(\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}\) per calcolare lo stesso valore e confrontato i risultati.
Come puoi vedere quello che opera l'approssimazione riesce a dare un risultato per \(n = 256\) (e riesce a darne anche per valori più grandi come \(n=511)\) per cui restituisce \(1.1216831144933562 * 10^306\)**) mentre il metodo che fa uso della definizione non ce la fa perché arriva ad una espressione del tipo \( \infty / \infty \) molto presto.
* Ed è poi in realtà possibile memorizzare solo metà dei valori per ogni riga e solo i valori calcolabili. Per cui per avere tutti i binomiali con n < 1024 si possono usare circa 2MB (pochi KB in più). Ma questo è un numero fin troppo alto in quanto non rappresentabile dai double.
** In effetti il primo valore non approssimabile dai double si ottiene per \(n = 515\).
\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{\prod_{i = \max(k, n-k) + 1}^n i}{\min(k, n-k)!} \]
oppure calcolare e memorizzare tutti i valori del binomiale fino al valore massimo che ti serve usando il triangolo di tartaglia e poi ottenere il valore leggendolo da questa tabella. Questa soluzione richiede un po' di spazio, ma per numeri relativamente piccoli non è neanche molto (una matrice 1024x1024 di double occupa 8 MB che non è poi molto vista la dimensione delle memorie attuali*). Ma per valori molto grandi usando i double potrebbe ad un certo punto essere conveniente fare ricorso ad un'approssimazione asintotica del binomiale. Usando infatti sia la definizione che il triangolo di tartaglia si finirebbe presto a sommare errori di approssimazione sempre più grandi ottenendo valori sempre più imprecisi. Per fare un esempio. Ho calcolato \(\binom{2n}{n}\) usando prima gli Integer e poi i double in haskell e poi ho fatto ricorso all'approssimazione \(\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}\) per calcolare lo stesso valore e confrontato i risultati.
Prelude> let vi n = div (product [(n+1)..(2*n)]) (product [1..n]) vi :: Integral a => a -> a (0.00 secs, 2026920 bytes) Prelude> let vd n = product [(n+1.0)..(2.0*n)] / product [(1.0::Double)..n] vd :: Double -> Double (0.02 secs, 0 bytes) Prelude> let va n = (4.0::Double) ** n / sqrt (pi * n) va :: Double -> Double (0.02 secs, 0 bytes) Prelude> vi 128 5768658823449206338089748357862286887740211701975162032608436567264518750790 it :: Integer (0.02 secs, 0 bytes) Prelude> vd 128 5.768658823449208e75 it :: Double (0.02 secs, 2022180 bytes) Prelude> va 128 5.7742950165976394e75 it :: Double (0.00 secs, 2026572 bytes) Prelude> vi 256 472553303154964924989004370051186389478210715642481882577328859153566070336566100844650299634054239969857431328433974960326174706663509667348266572071494 it :: Integer (0.02 secs, 2027860 bytes) Prelude> vd 256 NaN it :: Double (0.00 secs, 0 bytes) Prelude> va 256 4.727840982676636e152 it :: Double (0.00 secs, 0 bytes)
Come puoi vedere quello che opera l'approssimazione riesce a dare un risultato per \(n = 256\) (e riesce a darne anche per valori più grandi come \(n=511)\) per cui restituisce \(1.1216831144933562 * 10^306\)**) mentre il metodo che fa uso della definizione non ce la fa perché arriva ad una espressione del tipo \( \infty / \infty \) molto presto.
* Ed è poi in realtà possibile memorizzare solo metà dei valori per ogni riga e solo i valori calcolabili. Per cui per avere tutti i binomiali con n < 1024 si possono usare circa 2MB (pochi KB in più). Ma questo è un numero fin troppo alto in quanto non rappresentabile dai double.
** In effetti il primo valore non approssimabile dai double si ottiene per \(n = 515\).
Ho anche provato il tuo metodo e si comporta in generale abbastanza bene, ma con risultati meno precisi di tutti gli altri (per i valori grandi che ho testato). Fornendo sempre risultati più piccoli del valore corretto riesce a continuare a dare risultati fino a \(n = 519\). Sui valori piccoli immagino che potrebbe ugualmente non essere molto preciso per via dell'uso massiccio delle funzioni come il logaritmo e l'esponenziale che sono imprecise per natura (anche le funzioni si devono approssimare).
Apatriarca grazie del tempo che stai buttando con me.
Allora vada per il salvataggio; mi pare che è quello che mi consigliate. A me servirà al massimmo a 200 ma visto che le salviamo credo si possa ingrandire un pochino ma non serve tanto.
Ma voi parlate di un salvataggio definitivo sull hard e poi ogni volta che dovrò utilizzare un codice con i binomiali andare a caricarlo nel file e quindi a richiamarlo in ram? Se dico cavolate scusate.
A parte questa domanda, trovo subito problemi nello scrivere un codice che faccia tartaglia.
Mi date qualche dritta?
Edit: Aggiornamento: lo ho fatto così:
Adesso sopravviene il problema del salvataggio ed anche di escludere un pezzo di triangolo che è inutile.
Allora vada per il salvataggio; mi pare che è quello che mi consigliate. A me servirà al massimmo a 200 ma visto che le salviamo credo si possa ingrandire un pochino ma non serve tanto.
Ma voi parlate di un salvataggio definitivo sull hard e poi ogni volta che dovrò utilizzare un codice con i binomiali andare a caricarlo nel file e quindi a richiamarlo in ram? Se dico cavolate scusate.
A parte questa domanda, trovo subito problemi nello scrivere un codice che faccia tartaglia.
Mi date qualche dritta?
Edit: Aggiornamento: lo ho fatto così:
int Array[10][10];
for (int i=0; i<10; i++)
{
Array[i][0]=1;
Array[i][i]=1;
for (int j=1; j<i; j++)
{
Array[i][j]=Array[i-1][j]+Array[i-1][j-1];
}
}
Adesso sopravviene il problema del salvataggio ed anche di escludere un pezzo di triangolo che è inutile.
Ciao,
per il codice:
sbagli nei cicli for:
Alcue note:
- in C/C++ negli array i valori disponibili sono $[0,n-1]$ su un'allocazione di $n$ celle. Perciò se vuoi che il tuo algoritmo effettivamente ti restituisca il valore di $((n),(k))$ perciò $A[n][k]$ dovrai allocare $n+1$ celle.
- consiglio di allocare la matrice in esterno e passare il puntatore come parametro alla funzione. Ovviamente l'$n$ della funzione è quello del coefficiente binomiale, non quello effettivo della matrice (vedi riga sopra).
- per memoriazzare il tutto, biosogna salvari una qualche struttura dati in un file di testo, con una strutturazione di funzioni di lettura, se vuoi calcolarli una volta, poi dovrai saperli leggere adeguatamente in un colpo.
I file vengono effettivamente copiati in memoria al momento dell'utilizzo, ma questo va oltre le conoscenze del C++ (sistemi operativi). Quello che ti basta sapere/utlizzare è le funzioni read/write, nulla di complicato. Puoi anche stampare sul file la tabella così comè con uno spazio. Poi ci sono le conversioni dei tipi in stringhe...
- per il fatto che utilizzi solo metà matrice, non puoi farci niente. Effettivamente ci sono dei trucchi per memoriazzare solo ciò che utilizzi, ma non ne vale la pena, tanto anche se allochi un mostro di matrice, in memoria rimarrà solo una parte.
ci sarebbe molto altro da dire, intanto cerchiamo di far funzionare l'algoritmo di tartaglia, il resto viene dopo
per il codice:
sbagli nei cicli for:
coefficiente_Binomiale(int n,type[][] A){
for(int i=0;i<=n;i++){
A[i][0] = 1;
A[i][i] = 1;
}
for(int i= 2;i<=n;i++){
for(int j =1;j<=i-1;j++){
A[i][j] = A[i-1][j-1] + A[i-1][j];
}
}
}
Alcue note:
- in C/C++ negli array i valori disponibili sono $[0,n-1]$ su un'allocazione di $n$ celle. Perciò se vuoi che il tuo algoritmo effettivamente ti restituisca il valore di $((n),(k))$ perciò $A[n][k]$ dovrai allocare $n+1$ celle.
- consiglio di allocare la matrice in esterno e passare il puntatore come parametro alla funzione. Ovviamente l'$n$ della funzione è quello del coefficiente binomiale, non quello effettivo della matrice (vedi riga sopra).
- per memoriazzare il tutto, biosogna salvari una qualche struttura dati in un file di testo, con una strutturazione di funzioni di lettura, se vuoi calcolarli una volta, poi dovrai saperli leggere adeguatamente in un colpo.
I file vengono effettivamente copiati in memoria al momento dell'utilizzo, ma questo va oltre le conoscenze del C++ (sistemi operativi). Quello che ti basta sapere/utlizzare è le funzioni read/write, nulla di complicato. Puoi anche stampare sul file la tabella così comè con uno spazio. Poi ci sono le conversioni dei tipi in stringhe...
- per il fatto che utilizzi solo metà matrice, non puoi farci niente. Effettivamente ci sono dei trucchi per memoriazzare solo ciò che utilizzi, ma non ne vale la pena, tanto anche se allochi un mostro di matrice, in memoria rimarrà solo una parte.
ci sarebbe molto altro da dire, intanto cerchiamo di far funzionare l'algoritmo di tartaglia, il resto viene dopo
Ciao Ham_burst; grazie infinite della pazienza.
Perchè sono sbagliati gli indici?
Il risultato con il mio codice da questo:
e quindi si che partono da 0 gli indicatori di righe e colonne ma anche i binomiali $((n),(k))$ li ho definidti per $n=0,,,N$ e $k=0,...,n$ quindi anche gli indici partono da 0. Ad esempio Array[6][4] mi restituisce 15 che è uguale a $((6),(4))$. Ovviamente arriva fino a 9 e non a dieci quindi se era N grannde che è sciftato OK
Per richiamarli avevo fatto come dici te una funzione con variabile puntatore:
però non sembra essere una soluzione adeguata perchè invece di fare così sembra mi convenga fare Array[6][4] direttamente nel codice e via e forze è la soluzione migliora magari cambiandogli nome.
Venedo al tuo codice non capisco questa forma di definizione:
coefficiente_Binomiale(int n,type[][] A){
Cosa è una funzione o un oggetto (sembrerebbe una funzione di interi ma a che dimensinone? libera?)
Non lo ho testato ma sembrerebbe che la seconda riga (i=1) non venga definita? Refuso? però se fai partire i da 1 alla fine viene uguale al mio codice tanto il secondo for (quello in j) per i=0,1 non fa nulla perchè la condizione di verifica è falsa.
Quindi problemi aperti:
non ho capito cosa intendevi con la correzione degli indici;
cosa intendi con: coefficiente_Binomiale(int n,type[][] A){
e connesso se in questa maniera si evita di buttare spazio visto che nela mia matrice quasi metà rimane inutilizzata;
come si salva e si ricarica per l'utilizzo;
una volta ricaricata che forma di lettura è da utilizzare per prendere il numero.
A quest'ultima come dicevo prima uno potrebbe anche chiamare Array come Coefficiente_Binomilae e ogni qualvolta serva fare Coefficiente_Binomiale[n][k].
Grazie; Bye.
Perchè sono sbagliati gli indici?
Il risultato con il mio codice da questo:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
e quindi si che partono da 0 gli indicatori di righe e colonne ma anche i binomiali $((n),(k))$ li ho definidti per $n=0,,,N$ e $k=0,...,n$ quindi anche gli indici partono da 0. Ad esempio Array[6][4] mi restituisce 15 che è uguale a $((6),(4))$. Ovviamente arriva fino a 9 e non a dieci quindi se era N grannde che è sciftato OK
Per richiamarli avevo fatto come dici te una funzione con variabile puntatore:
int *ptrArray = &Array[6][4];
cout << choose(ptrArray);
int choose(int *ptrArray)
{
int z = *ptrArray;
return z;
}
però non sembra essere una soluzione adeguata perchè invece di fare così sembra mi convenga fare Array[6][4] direttamente nel codice e via e forze è la soluzione migliora magari cambiandogli nome.
Venedo al tuo codice non capisco questa forma di definizione:
coefficiente_Binomiale(int n,type[][] A){
Cosa è una funzione o un oggetto (sembrerebbe una funzione di interi ma a che dimensinone? libera?)
Non lo ho testato ma sembrerebbe che la seconda riga (i=1) non venga definita? Refuso? però se fai partire i da 1 alla fine viene uguale al mio codice tanto il secondo for (quello in j) per i=0,1 non fa nulla perchè la condizione di verifica è falsa.
Quindi problemi aperti:
non ho capito cosa intendevi con la correzione degli indici;
cosa intendi con: coefficiente_Binomiale(int n,type[][] A){
e connesso se in questa maniera si evita di buttare spazio visto che nela mia matrice quasi metà rimane inutilizzata;
come si salva e si ricarica per l'utilizzo;
una volta ricaricata che forma di lettura è da utilizzare per prendere il numero.
A quest'ultima come dicevo prima uno potrebbe anche chiamare Array come Coefficiente_Binomilae e ogni qualvolta serva fare Coefficiente_Binomiale[n][k].
Grazie; Bye.
Si può memorizzare il triangolo di tartaglia in metà dello spazio utilizzando la sua simmetria. Nonché eliminare in teoria qualche riga banale (ma forse queste ultime ad un costo computazionale non accettabile).
Non lascerei all'utente della libreria l'onere di gestire lo stato. Idealmente, l'utente non dovrebbe neanche sapere dell'esistenza di questo stato. Inoltre, generare tutti i binomiali potrebbe non essere ottimale se abbiamo bisogno solo di alcuni di essi. Una soluzione alternativa potrebbe essere quella di memorizzare solo quelli che ci servono. Lo stato verrà invece memorizzato in modo da non essere visibile dall'utente (ci sono diversi metodi) ma solo dalla funzione.
ti rispondo in merito alle tue domande:
ho notato adesso che hai sostituito le condizioni dei for, ci penso su, diciamo che ora non ho molta voglia di analizzare codice
EDIT 12/9:
i codici sono equivalenti, cambia il comportamento ed il momento in cui viene inizializzat la matrice. A mio modo di vedere ci sono piccoli fattori constanti in più nel tuo codice. Gli indici sono "diversi" solo se consideriamo l'allocazione e il valore $N$ che parlavi negli altri post.
questo era proprio quello che volevo farti evitare. Quando calcoli il binomiale, non devi pensare che la tua funzione calcola $n-1$ ricordandoti che ai allocato $n$ celle. Ti allochi $n+1$ celle così ti calcoli esattamente il binomiale $C(n,k)$.
Poi sta alla tua sensibilità
e quando mai avrei proposto una "meraviglia" del genere
leggi il commento di apatriarca in merito a questo problema
il succo del consiglio: (*)
cioè non dare accesso diretto all'array all'utente, ma solo tramite una funzione che legge il valore che cerchi.
vedi sopra (cioè ci penso su)
è una funzione, ma c'è un piccolo refuso, dovuto alla notazione di pseudo-codice, cioè non essendoci ritorno di nessun valore manca il "void"
vedi sopra (cioè ci penso su)
vedi sopra (se non è chiaro basta dirlo)
vedi consiglio di vict85 $^^$ apatriarca
puoi salvarla su un file di testo esattamente come la hai stampata a triangolo prima.
Cioè con uno " ". Per leggerli viene il bello, puoi scriverti una funzione che legga una stringa lunga $log_2((n!)/((n-k)!k!))$ cifre, e convertirlo in numero intero. Ci sono funzioni apposite per farlo, se vuoi scriverla te, ti si da una mano
Il resto basta decidere un po' come salvare i dati
qua stesso consiglio (*), ma puoi benissimo fare come hai scritto.
Nota che coefficiente_Binomiale (per chiarire) è una funzione, coefficiente_Binomiale[n][k] non è nulla di dichiarato, al massimo puoi fare A[n][k].
se hai dubbi basta chiedere
"DajeForte":
Perchè sono sbagliati gli indici?
ho notato adesso che hai sostituito le condizioni dei for, ci penso su, diciamo che ora non ho molta voglia di analizzare codice
EDIT 12/9:
i codici sono equivalenti, cambia il comportamento ed il momento in cui viene inizializzat la matrice. A mio modo di vedere ci sono piccoli fattori constanti in più nel tuo codice. Gli indici sono "diversi" solo se consideriamo l'allocazione e il valore $N$ che parlavi negli altri post.
Ovviamente arriva fino a 9 e non a dieci quindi se era N grannde che è sciftato OK
questo era proprio quello che volevo farti evitare. Quando calcoli il binomiale, non devi pensare che la tua funzione calcola $n-1$ ricordandoti che ai allocato $n$ celle. Ti allochi $n+1$ celle così ti calcoli esattamente il binomiale $C(n,k)$.
Poi sta alla tua sensibilità
Per richiamarli avevo fatto come dici te una funzione con variabile puntatore:
int *ptrArray = &Array[6][4]; cout << choose(ptrArray); int choose(int *ptrArray) { int z = *ptrArray; return z; }
però non sembra essere una soluzione adeguata perchè invece di fare così sembra mi convenga fare Array[6][4] direttamente nel codice e via e forze è la soluzione migliora magari cambiandogli nome.
e quando mai avrei proposto una "meraviglia" del genere
leggi il commento di apatriarca in merito a questo problema
il succo del consiglio: (*)
private int A[][];
int f(int n, int k) {
return A[n][k]
}cioè non dare accesso diretto all'array all'utente, ma solo tramite una funzione che legge il valore che cerchi.
Venedo al tuo codice non capisco questa forma di definizione:
coefficiente_Binomiale(int n,type[][] A){
Cosa è una funzione o un oggetto (sembrerebbe una funzione di interi ma a che dimensinone? libera?)
Non lo ho testato ma sembrerebbe che la seconda riga (i=1) non venga definita? Refuso? però se fai partire i da 1 alla fine viene uguale al mio codice tanto il secondo for (quello in j) per i=0,1 non fa nulla perchè la condizione di verifica è falsa.
vedi sopra (cioè ci penso su
)coefficiente_Binomiale(int n,type[][] A){ è una funzione, ma c'è un piccolo refuso, dovuto alla notazione di pseudo-codice, cioè non essendoci ritorno di nessun valore manca il "void"
void coefficiente_Binomiale(int n,type[][] A){
...
}
Quindi problemi aperti:
non ho capito cosa intendevi con la correzione degli indici;
vedi sopra (cioè ci penso su
)cosa intendi con: coefficiente_Binomiale(int n,type[][] A){
vedi sopra (se non è chiaro basta dirlo
)
e connesso se in questa maniera si evita di buttare spazio visto che nela mia matrice quasi metà rimane inutilizzata;
vedi consiglio di vict85 $^^$ apatriarca
come si salva e si ricarica per l'utilizzo;
puoi salvarla su un file di testo esattamente come la hai stampata a triangolo prima.
Cioè con uno " ". Per leggerli viene il bello, puoi scriverti una funzione che legga una stringa lunga $log_2((n!)/((n-k)!k!))$ cifre, e convertirlo in numero intero. Ci sono funzioni apposite per farlo, se vuoi scriverla te, ti si da una mano
Il resto basta decidere un po' come salvare i dati
una volta ricaricata che forma di lettura è da utilizzare per prendere il numero.
A quest'ultima come dicevo prima uno potrebbe anche chiamare Array come Coefficiente_Binomilae e ogni qualvolta serva fare Coefficiente_Binomiale[n][k].
qua stesso consiglio (*), ma puoi benissimo fare come hai scritto.
Nota che coefficiente_Binomiale (per chiarire) è una funzione, coefficiente_Binomiale[n][k] non è nulla di dichiarato, al massimo puoi fare A[n][k].
se hai dubbi basta chiedere
Non sono con il mio computer, e quindi non posso controllare e testare cose.
Riprenderò il tutto lunedì mattina; nel frattempo volevo ringraziavi.
Buon Sabato/Domenica.
Riprenderò il tutto lunedì mattina; nel frattempo volevo ringraziavi.
Buon Sabato/Domenica.
Allora ragazzi dopo un giorno perso, sono stremato e mi rivolgo a voi.
Sto provando ad usare boost ma mi arresto immediatamente in partenza.
Dopo aver scaricato il file.tz ed averlo installato (in una directory da me scelta) ho provato a fare questo
Ovviamente la riga #include fa un casino: a volte non trova e mi scrive
Boost_1.cpp:3:28: error: boost/random.hpp: No such file or directory
a volte parte con una sfilza di no such file or directory, se magari ho modificato l'indirizzo.
Ho provato un po' tutto: installare a destra e a manca boost, a spostarlo a cercare la path di #include, a metterlo dove sta iostream (se non ricordo male /usr/local). Insomma sono esausto.
Avreste qualche consiglio.
P.S Qualora dovesse servire qualche ulteriore chiarimento chiedete.
Grazie mille.
Ciao.
Sto provando ad usare boost ma mi arresto immediatamente in partenza.
"apatriarca":
Usa Boost Random. Per scaricare e usare boost (che è un insieme di librerie in C++ molto diffuse e usate) puoi leggerti le istruzioni presenti in questa pagina del manuale online o verificare se la tua distribuzione fornisce già dei pacchetti per questa libreria (potrebbero anche essere già installati se in alcune distro hai chiesto di installare gli strumenti di sviluppo per il C++).
Dopo aver scaricato il file.tz ed averlo installato (in una directory da me scelta) ho provato a fare questo
#include <iostream>
#include <boost/random.hpp>
using namespace std;
int main()
{
cout << endl;
char f;
cin >> f;
return 0;
}
Ovviamente la riga #include
Boost_1.cpp:3:28: error: boost/random.hpp: No such file or directory
a volte parte con una sfilza di no such file or directory, se magari ho modificato l'indirizzo.
Ho provato un po' tutto: installare a destra e a manca boost, a spostarlo a cercare la path di #include, a metterlo dove sta iostream (se non ricordo male /usr/local). Insomma sono esausto.
Avreste qualche consiglio.
P.S Qualora dovesse servire qualche ulteriore chiarimento chiedete.
Grazie mille.
Ciao.
Ciao DajeForte 
così ad occhio direi proprio che non hai passato al compilatore (linker) la path corretta della libreria.
Che codice scrivi per compilare (penso utilizzi gcc/g++)?
Nel post scritto da apatriarca c'è il link a come scrive e compilare, hai dato un'occhiata a questo:
- Build a Simple Program Using Boost
- Link Your Program to a Boost Library
"DajeForte":
Boost_1.cpp:3:28: error: boost/random.hpp: No such file or directory
così ad occhio direi proprio che non hai passato al compilatore (linker) la path corretta della libreria.
Che codice scrivi per compilare (penso utilizzi gcc/g++)?
Nel post scritto da apatriarca c'è il link a come scrive e compilare, hai dato un'occhiata a questo:
- Build a Simple Program Using Boost
- Link Your Program to a Boost Library
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo