Topic: Discussione sul pi greco (Read 5314 times)

Ti eri segnato un memo tre anni fa ?!?   

Riesumiamo oggi questo 3d, oggi è il 3.14

Sicuramente è sufficiente una distribuzione uniforme di punti, anche non casuale, per la stima di pi greco. Ma a questo punto allora, se l'obiettivo è solo quello di determinare tante cifre decimali di pi greco, tanto vale usare una delle tante successioni individuate nell'analisi matematica che convergono a pi greco; di sicuro esse convergeranno molto più rapidamente sia del metodo Monte Carlo (che converge in senso probabilistico) sia di quello classico dell'analisi numerica proposto da picchio, i quali alla fine utilizzano entrambi una semplice forza "bruta".

L'aspetto interessante invece del metodo Monte Carlo sta proprio nello sperimentare quanto uniforme possa diventare una sequenza "quasi" casuale. Qualche post fa ad esempio io e picchio abbiamo discusso se, al netto dei problemi legati agli arrotondamenti derivanti dal lavorare con una macchina con una precisione finita, tramite il metodo Monte Carlo si arrivasse "sempre" ( o "sicuramente") ad una migliore approssimazione man mano che si generano i punti, proprio come succede per il caso della griglia sempre più fina dell'analisi numerica. Il fascino di questo metodo sta nel fatto che esso lega, in modo semplice ed elegante, precisione crescente (forse) e casualità, di norma concetti antitetici.

A me e' venuto in mente che forse non conviene neanche farla casuale tanto non ci interessa la sequenza dei valori, si stabilisce quanti punti (quadrato perfetto) e si stima il valore ...

Mi ricordo che anch'io avevo fatto qualcosa di simile beh ormai stiamo parlando di una ventina di anni fa !!! 
Intanto fai bene ad affermare pseudo-casuali e non casuali altrimenti è come cercare di schiacciare le mosche con un bazzuca .
Comunque quello di cui hai bisogno è una distribuzione uniforme non centra niente quanto sia "casuale" hai bisogno di una sequenza molto lunga il più uniforme possibile ( o perlomeno di conoscere esattamente quale sia la distribuzione della sequenza ) , anzi si potrebbe pure fare il contrario individuare quanto una sequenza sia uniforme in funzione di quanto il risultato si discosti da pigreco.
Questo direi che è il più importante dei problemi . La precisione con cui potrai calcolare pigreco sarà in funzione delle conoscienza della distribuzione e della sua lunghezza .
Il secondo problema è tecnico , devi utilizzare delle gestioni numeriche che vadano ben oltre quelle fornite dall' hardware e per questo esistono un bel po' di librerie che ti possono aiutare .
Infine direi che una implementazione su OpenCL ( giusto per andare poi un po' ovunque al contrario di cuda ) sarebbe molto adatta ad un problema di questo tipo , penso che potrestio arrivare ad una fattore di velocià pari 1000x rispetto alla cpu.
Beh sono un po' in ritardo spero che queste semplici dritte saranno utili per il prossimo pi day  !

Ho trovato in rete questo software per leggere i blocchi https://code.google.com/p/blockchain/, qui un articolo dell'autore http://codesuppository.blogspot.it/2014/01/how-to-parse-bitcoin-blockchain.html. Non l'ho provato, ma potresti usarlo per la stima di pi greco con il tuo metodo.


Anch'io non sono del tutto convinto dal sistema pow, che rischia di favorire alla lunga solo pochi minatori ( i più bravi e meglio organizzati ) rispetto a tutti gli altri. Inoltre tutto questo crescente "work" a garanzia del valore della moneta prima o poi lo pagheremo tutti, infatti quando le ricompense per blocco scompariranno o si ridurranno considerevolmente, temo che le commissioni che dovremo pagare per le transazioni aumenteranno di molto.
L'idea di distribuire la probabilità di minare un blocco sugli indirizzi alla fine non penso funzionerebbe, proprio perché come hai giá notato tu un singolo minatore potrebbe mettersi a generare miliardi e miliardi di indirizzi.
Secondo me la questione che sta alla base é che tutto quello che ruota intorno al mondo bitcoin ( i bitcoin, gli indirizzi, la capacitá computazionale / work, e quindi il concetto stesso di fiducia che sta alla base di ogni tipo di moneta, matematica o no) non "vede" i singoli individui, nel senso che uno stesso individuo può avere 1, 10, 10000 indirizzi / bitcoin / terahash di potenza, il suo "voto" quindi nel processo di verifica della correttezza delle transazioni  (quale che sia il metodo scelto per farlo "esprimersi" sulla correttezza delle transazioni, proof of work, proof of stake, ... ) vale quanto quello di altri 1000 individui messi insieme, in altre parole il bitcoin ( e non solo lui ) non si basa su un processo democratico.

Certo, così è chiarissimo 

Ma la stima di pi greco si fermava solo alla prima cifra decimale? Quanti punti generavi per ottenere quella stima? Velocità (num punti al secondo) ?

https://github.com/bertani/piProject/blob/master/functions.inc#L163

Rileggendolo, a parte lo shifting nell'intervallo I-J desiderato direi che facevo circa questo:
"considera il contenuto preesistente del registro W, fa due left shifting di 1 bit, se il quarto bit e' 0 fa uno xor, se il terzo bit e' 0 fa un altro xor"

Carino l'oggetto :-), non capendo di assembler ti chiedo, come generavi i numeri casuali?

Ops, mi ero perso il thread  

Nostalgia! Cinque anni fa avevo scritto un programmino per fare proprio questo (senza multithreading, in asm, per un microcontrollore a 8 bit, pic16f628a); se qualcuno vuole farsi 2 risate, ecco il sorgente: https://github.com/bertani/piProject/blob/master/pi_project.asm  

In probabilità si parla di evento quasi certo quando esso accade con probabilitá 1, di evento certo se esso accade sempre, sicuramente, e per gli eventi contrari vale lo stesso concetto.

Esempio del tipo 1: se hai un generatore di una distribuzione uniforme di numeri reali tra 0 e 1, la probabilità che esca un numero qualsiasi, per esempio 0,458 é 0, nel senso che é minore di una qualsiasi altra probabilitá positiva ( é minore di 0,1, di 0,00001, di 0,00000000001 ... semplicemente perché c'é un solo caso favorevole su infiniti possibili ) ma non é certo impossibile che esca; quindi si dice che l'evento "esce 0,458" é un evento che quasi certamente non accadrá ( o che accadrá con probabilitá 0 )

Esempio del tipo 2: se lancio un dado l'evento "esce un numero maggiore di 6" é un evento che certamente non accadrá.

Qui si sta usando la probabilitá in senso assiomatico, e in particolare si inquadra nel contesto della teoria della misura. I problemi nascono quando devi confrontare uno spazio degli eventi favorevoli discreto e finito con uno spazio degli eventi possibili infinito e/o continuo, oppure due spazi infiniti di diverse dimensioni. Di solito nel caso dell'esempio 1 non si calcola mai la probabilitá di un evento "0-dimensionale" se sei in uno spazio degli eventi 1-dimensionale ( il segmento ) ma si parla di densitá di probabilitá oppure di probabilitá che esca un valore all'interno di un certo intervallo.

Dai un'occhiata qui
https://it.m.wikipedia.org/wiki/Quasi_certamente
EDIT: ti ricorda qualcosa il bersaglio circolare? 

A quale definizione di probabilità fai riferimento?
Per come capisco direi quella soggettiva che, pur piacendomi, non ho mai approfondito a dovere, a pelle direi che e' quella che potrebbe dare maggiori soddisfazioni.
Mi fa strano pensare ad un evento che ha probabilità 0 (zero) ma si puo' verificare.

Sì, 100% corrisponde a p(E)=1, ma io preferisco utilizzare quest'ultima notazione perchè mi sembra che quando si dice 100% lo si usi come sinonimo di "certo, sicuro" il che non è corretto.
Se un evento non può accadare allora sicuramente ha probabilità 0, viceversa se un evento ha probabilità 0 non è detto che non possa verificarsi. Analogamente, se un evento accadrà sicuramente allora ha probabilità 1, ma se un evento ha probabilità 1 non è detto che si verifichi sicuramente.

Nel nostro caso, in che senso la nostra successione di stime di pi greco converge con probabilità 1 a pi greco? Nel senso che fissato un epsilon piccolo a piacere, da un certo valore N in poi l'insieme dei valori della successione per cui la stima di pi greco esce dall'intorno di raggio epsilon di pi greco ha misura 0, cioè può benissimo capitare che per qualche valore dopo N punti la successione si discosti dalla sua direzione principale (direzione che la teoria ci assicura esistere e verso la quale la nostra successione deve puntare), ma il numero di questi valori è trascurabile rispetto agli infiniti altri valori per i quali la successione starà in quell'intorno di pi greco.

Soprattutto quello che importa è che la nostra successione mostra chiaramente di localizzare in intervalli sempre più ristretti il suo "obiettivo", per cui è chiaro che se a un certo punto dovesse accadere (e ripeto, questo fatto può accadere solo con probabilità 0) che per qualche punto la successione smetta di convergere ed inizi a oscillare a caso, questo fenomeno sarebbe facilmente riconoscibile ed eliminabile, essendo il suo trend principale facilmente individuabile.
 

100% è esattamente p(E)=1. Comunque siamo OT, ci vorrebbe un forum di matematici e se ne potrebbero vedere delle belle, rimanendo in topic potremmo approfondire gli altri aspetti ...
Un giorno, se sapro' leggere la chain con qualche software,  provo a stimare pi con gli hash casuali della chain con griglia k*k, magari sarebbe bello trovare una funziona f(k, blocco) e vedere come si comporta ...
E un algoritmo pow/pos o prova di esistenza che coinvolga pi greco non sarebbe male.

Certo al 100% forse no, ma con probabilità 1 sì  
Tu dici che all'infinito potrebbe accadere che si presenti una successione che sconvolga il dato complessivo, io dico che più si va avanti più é improbabile che questo accada, e per improbabile intendo che é più facile indovinare una chiave privata da una chiave pubblica che dopo una successione di 1000 miliardi di punti ti trovi una stima di pi greco di 2,5!

Perfetto. Su questo ci siamo ...
Secondo me il metodo Monte Carlo è solo una specie di "gioco" che non puo' servire a dire con certezza quale sia l'ennesima cifra di pi greco (neanche se n=1) in quanto nessuno puo' escludere che prima o poi, andando oltre con i punti, la stima ottenuta con tale metodo non cambi tale cifra (per poi rientrare ma come fai ad essere sicuro?). Anzi, mi aspetto che all'infinito ci sia una sequenza tale che possa cambiare il valore della cifra che hai scelto di stimare.
Ma credo che non se ne possa uscire facilmente, fior fiore di matematici hanno parlato di infinitesimi e hanno dato vita all'analisi matematica ... bisognerebbe capire se con la definizione assiomatica di probabilità https://it.wikipedia.org/wiki/Probabilit%C3%A0#Definizione_assiomatica si può arrivare a qualcosa di "certo" ma io non ho sicuramente le competenze per approfondire tale argomento.

Allora cerco di spiegare meglio qual è il mio pensiero.
Sicuramente la probabilità che esca una sequenza di infiniti (1,1) è uguale alla probabilità che esca una qualsiasi specifica altra sequenza casuale: questa probabilità è 0 (il che non vuol dire che non possa accadere).  Quello che succede però è che la probabilità che esca una sequenza dall'insieme delle sequenze la cui proprietà è quella di convergere a pi greco è molto più alta (a occhio direi è una probabilità = 1, il che non vuol dire certezza assoluta ma quasi) della probabilità che esca una sequenza dall'insieme delle sequenze che convergono a 0. In altre parole se genero in modo casuale e uniforme miliardi e miliardi di punti con coordinate tra -1 e 1, appare evidente che i punti "dovrebbero" distribuirsi uniformemente sul quadrato e nel cerchio generando la proporzione di 3,14, mentre non avrebbe senso che tutti i punti andassero ad addensarsi in un angolo fuori dal cerchio generando il valore 0.

Provo con un esempio più classico: se simulo il lancio di una moneta, all'aumentare dei lanci mi aspetto che la frequenza relativa di uscita della "testa" converga a 0,50 (cioè alla sua probabilità di uscita a ogni lancio come prevede la definizione frequentista di probabilità). Questo dice la teoria, non mi aspetto certo che la frequenza di uscita sia 0 perchè escono infinite "croci". In questo senso si dice un po' impropriamente che ha probabilità 0 la sequenza di sole "croci", poichè ha una proprietà (il tendere al valore di 0 teste) che va contro la definizione di probabilità (e infatti ce l'ha solo lei quella proprietà), mentre una sequenza che presenta un numero di "teste" e "croci" più equilibrate ha una "probabilità di uscita molto maggiore" - anche qui un po' impropriamente - semplicemente perchè è quella proprietà che è più probabile (nel senso che quest'ultima sequenza condivide questa proprietà con molte altre sequenze).  
E se uscissero improvvisamente 20000 croci di seguito? La teoria dice che potrebbero benissimo uscire, ma con una probabilità così bassa (1 volta ogni 2^20000 casi) che con ogni probabilità (quindi probabilità 1) questo accadrebbe solo dopo aver generato talmente tanti miliardi di punti, che questa sottosequenza speciale di uscite non sposterebbe di una virgola il dato complessivo.

Sono invece d'accordo sul fatto che qui non si tratta di una convergenza proprio come quella dell'analisi, nel senso che non è possibile definire a priori, data una certa epsilon, un valore N della successione oltre al quale tutti i valori della successione sono localizzati in un intorno di raggio epsilon del valore limite.

Immagina per finire di non conoscere il valore vero di pi greco: come faresti a stimarlo? Genereresti miliardi e miliardi di punti, i quali porterebbero a una successione di stime di pi greco che oscillerebbero (con oscillazioni sempre meno ampie) intorno a un valore limite, una specie di asintoto orizzontale che sarebbe per te il valore di pi greco. Più punti generi più ti avvicini (a meno di qualche ovvia oscillazione ma di decrescente ampiezza, come fanno anche le successioni dell'analisi peraltro) al valore limite. In questo senso intendo dire che l'algoritmo converge da qualche parte, perchè è proprio così, e più lo fai girare meglio è (con ogni probabilità )

A pelle i pow non mi convincono molto, non ho le idee ben chiare e ritengo interessante un dialogo, il sistema che hai descritto mi convince (simile a come l'avevo pensato anche io) ma non so quanto sia dispendioso generare la sequenza.
Tenderei ad aggiungere l'indirizzo BTC del minatore in modo che ciascuno abbia probabilità legate al proprio address e forse si distribuirebbe la probabilità di minare anche a chi non ha macchine performanti, temo che una procedura del genere avrebbe come controindicazione una proliferazione di indirizzi al fine di minare ...

Ad esempio (idee alla rinfusa ...): mina il blocco chi ha hash(address) piu' "vicino" ad hash("qualcosa legato al blocco precedente+seed/nonce") e forse si potrebbe inserire il pi greco ... eventualmente si potrebbe far aumentare la distanza consentita qualora dopo 10 minuti non venga generato il blocco (ma credo sia un casino ...)

In caso cambia anche subject :-)

Si, hai capito la stessa cosa alla quale pensavo. Aggiunta: al fine di non favorire i numeri bassi bisognerebbe iniziare a contare dall'ultimo estratto.
Non bisogna esagerare con il valore di k (per dare modo all'hash di fare "qualche giro") e per ogni valore di k si otterrebbe una stima (potenzialmente) differente del valore di pi.
Lotterie basate sull'hash in realtà calcolano l'sha512 dell'hash e dividono quello e non l'hash stesso in modo da avere numeri piu' grandi e non soggetti a riduzioni eccessive causate dall'aumento dela difficoltà (alla fine generano numeri sempre piu' piccoli).
Potenzialmente si potrebbero estrarre piu' numeri casuali dallo stesso hash dividendo il quoziente per k^2 ed iterando la procedura fino ad ottenere quoziente nullo. Esattamente come fare la trasformazione di base in base k^2.
Rimane il problema di come si puo' determinare k in modo "coerente" ... si potrebbe legare sia al numero di blocchi che alla difficoltà ed eventualmente si cambia ogni 2016 blocchi, oppure si vede come cambiano le stime per diversi valori di k. Qui' non ho avuto idee in merito.

Hai dei riferimenti teorici in merito? Io non riesco a concepire se non una probabilità che sia "minore di" e non vedo come una sequenza casuale possa garantire che la successione sia convergente al 100%. Infatti, se uscissero infinite coppie (1, 1) stimeremmo pi con valore 0 e la sequenza con tutte coppie (1, 1) ha la stessa probabilità della sequenza casuale che usi ... allo stesso modo nessuno puo' impedire che si presenti una successione che per ad un certo punto presenti una serie di centri eccessiva che porterebbe il valore della stima fuori dal termine epsylon che ti sei prefisso a priori (anche qui' spero di essermi spiegato). Ossia: con il casuale non credo si possa ragionare come con l'analitico, che poi di veramente casuale non c'è modo di simularlo e che prima interviene la precisione delle macchine son d'accordo. Ma dal punto di vista teorico sei sicuro ci sia una dimostrazione matematiche che garantisce la convergenza?

Un'idea potrebbe essere :
Difficoltà = numero di cifre del pigreco da "indovinare" (tipo 15 o 20)
Parametro n = numero massimo di punti che si possono generare (tipo 10000) per ottenere una stima entro tale margine di errore

A questo punto si genera l'hash di un blocco, che è il seed, e utilizzando una funzione random (uguale per tutti) si generano fino a 10000 punti. Se non si trova un'approssimazione di pi greco alla 15^ cifra, si modifica il blocco (come succede adesso), si ottiene un nuovo hash, a questo punto si prova la nuova serie (al massimo 10000 lanci) e così via.

In questo modo sarebbe molto dispendioso trovare la soluzione, ma molto facile verificarla.


EDIT: mi sono accorto che ormai l'argomento del thread è cambiato, ho chiesto a HostFat di spostare questo thread per non perdere i contributi di chi vi ha partecipato da una parte, e non utilizzare uno spazio inappropriato in quanto dedicato ai "Servizi" dall'altra

L'algoritmo dal mio punto di vista converge quasi come fosse un limite, da un certo punto in poi l'errore è "sempre" (con "sempre" intendo con probabilità 1) minore di un certo valore e così via, potremmo dire che la successione di stime di pi greco che si aggiorna dopo ogni lancio è una successione di Cauchy (fino al punto in cui subentrano gli errori dovuti alla precisione finita della macchina) che converge a pi greco.


Se ho capito, riassumendo:
1) dividi il quadrato 1x1 in una griglia regolare di k^2 punti
2) si prende l'hash di ciascun blocco (modulo k^2) e si ottiene così quale è il punto estratto (che corrisponde a uno dei vertici di questa griglia e solo a uno di questi, ad esempio il numero 7512 che corrisponde a una certa posizione nel quadrato)
3) alla fine di tutti i blocchi si calcola la stima di pi greco (che si otterrà di fatto dividendo il numero di centri ottenuti per il numero di blocchi presenti nella blockchain fino a quel momento)
4) ora abbiamo ottenuto una stima di pi greco, e il fatto notevole è che ogni punto è stato generato usando un seed diverso (l'hash del blocco corrispondente)

Ogni nuovo blocco "genera" un nuovo punto nel quadrato (con la limitazione che può essere sempre solo uno di quei k^2 punti). Bella idea!


Questa è la parte che mi intriga di più, la difficoltà sta nell'ideare un'operazione collegata ai blocchi difficile da effettuare in un senso ma facile da verificare nell'altro 

Ciao
solo alcune considerazioni/domande:
- ha senso parlare di convergenza del algoritmo parlando di numeri casuali? Al massimo si parla di probabilità di commettere un errore minore di x dopo n lanci. Un pochettino come il chi quadro ...
- quando ho lanciato il programmino che ho fatto ho pensato anche io ad una moneta che ha come sistema di minig qualcosa collegato al numero pi greco, secondo me qualcuno ci ha gia' pensato ... se riesco provo a cercare ...  non sarebbe male ...
- riflettevo anche su pi greco e blockchain e potrebbe essere interessante studiare un sistema che usa come generatore casuale gli hash dei blocchi e dia come risultato la stima di pi greco della chain. Si potrebbe applicare una griglia al quadrato 1*1 di k*k linee che danno luogo a k^2 punti nel quadrato, poi si conta dal primo a sinistra in basso verso destra salendo una volta arrivato alla x>=1 (non so se mi son spiegato ...), in sostanza si ottiene un intero per ciascuo degli k^2 punti. SI prende il primo hash della chain, si fa modulo k^2 e si determina il primo estratto. Questo e' il primo lancio. Poi si procede come al solito. Ogni blocco abbiamo un aggiornamento del valore.
La stima dipenderà ovviamente anche dal valore di k. Se ci sono idee su come sceglierlo, magari usando qualcosa legato alla difficoltà...

Ciao picchio e buon pi greco day a tutti!
Stamattina  3 / 14 / 15 alle 9:26:53 secondi sono state "festeggiate" le  prime 9 cifre decimali del pi greco! Succede 1 volta ogni 100 anni  

Per quanta riguarda il tuo programmino ho trovato interessante l'idea che hai avuto; mi spiego meglio, tu vuoi vedere dopo quanto tempo si arriva entro un certo limite di errore, effettivamente da come l'ha impostato tu  questo ricorda molto da vicino il concetto di difficoltà dei bitcoin.
Ovviamente se dovessimo usare veramente il programma per vedere quanto il metodo Monte Carlo funziona nella stima di pi greco (la velocitá di convergenza dell'algoritmo al risultato) non avrebbe molto senso fare così, poiché affermare di riuscire a fare un errore dell'ordine di e-09 / e-10 solo con poche decine di migliaia di punti sarebbe un po' come ricavare dal fatto che un certo blocco é minato in 30 secondi una stima per eccesso della propria velocità di risoluzione del problema.

La grossa differenza tra il mining e la stima di pi greco é che con il pi greco tu sai che piú calcoli fai, migliore diventa l'approssimazione (almeno fino a un certo punto), mentre con il mining si é costretti a parlare di probabilitá di trovare una soluzione. Io per arrivare a una stima "stabile" delle prime 6 cifre di pi greco ho dovuto generare centinaia di miliardi di punti, se per caso dopo 10000 punti ottengo le prime 5 cifre corrette e al 10001 punto la stima risulta corretta solo fino alla 4^ cifra, l'algoritmo allora non ha localizzato la soluzione, l'ha semplicemente solo "indovinata".

Sarebbe possibile, almeno a livello teorico,  fare il mining sostituendo il problema di ottenere la famosa stringa con un tot di 0 iniziali con quello di approssimare pi greco fino alla x-esima cifra decimale ?  
Con il pi greco bisognerebbe trovare l'accoppiata seed  / numero di punti generati per dimostrare di avere trovato la soluzione richiesta, ma forse tutti dovrebbero usare una stessa funzione random?
Sarebbe piú facile "barare" e fornire una soluzione al problema che non richieda molti calcoli?

EDIT: mi é venuto in mente che come minimo bisogna trovare però almeno un modo per collegare il calcolo del pi greco alle transazioni contenute nel blocco da validare ...

Ho fatto un programma in c++ che, chiesto l'errore assoluto desiderato "spara" fino a che non raggiunge quella precisione.
Io l'ho compilato su GNU/Linux e funziona, non ci mette molto ad ottenere valori di qualche decimale...
Non so se gli errori di calcolo alla fine hanno la meglio ... se qualcuno puo' intervenire ben venga!
Devo dire che a lanciarlo si ha come la sensazione di "minare" in quanto a volte si ferma dopo pochi cicli, a volte dopo migliaia.
Feedbak benvenuti e buon pi greco day.
EDIT:
Qualche esempio di esecuzione:

Sono d'accordo, non é sicuramente il metodo più efficace né quello che converge più rapidamente, ma ormai mi ha preso e voglio vedere se almeno é possibile arrivare a un errore di non più di una parte su un miliardo.
Tieni conto che se si potessero generare effettivamente dei numeri reali e quindi dei veri punti 0-dimensionali ( e non dei numeri su una macchina con una precisione finita che quindi corrispondono a dei rettangolini, un po' come l'impronta di una freccia fisica su un bersaglio) non potrebbe succedere certo di generare milioni di punti uguali 

La parte che mi intriga di più é proprio quella della generazione pseudocasuale dei numeri, che é tutt'altro che scontata quando si tenta di parallelizzare la procedura (ad esempio, quattro sequenze di numeri casuali generati da 4 thread paralleli mantengono le stesse proprietá statistiche di un'unica sequenza di numeri casuali? Non é scontato, bisogna vedere come é implementata la funzione random che si utilizza).

D'altronde in un forum dedicato al bitcoin un po' di curiosità per le sequenze stocastiche e le loro proprietà ci sta bene.

A mio avviso il metodo ha molto senso se lo fai con figure irregolari e per una stima di massima, se vuoi affinare la stima a qualche decimale credo non sia il massimo accanirsi ma senza queste prese di posizione forse saremmo ancora al tempo della pietra :-)

Con la mia cpu Core2 Duo P8700 e programma compilato con free pascal riesco a fare 1 miliardo di punti in poco più di 1 minuto, pensando di portare il programma su altri pc più potenti e con più core la strada migliore mi sembra proprio il multithread.

Grazie a tutti per l'aiuto!

EDIT: se qualcuno vuole provare il mio programmino è questo https://dl.dropboxusercontent.com/u/134071847/Stimapigreco2.exe, è per Windows, basta cliccarci su, inserire il numero di punti (provate 10000000000) dovrebbe impiegarci meno di 10 minuti. Non ci sono virus!

Vuoi mettere la sensazione di lanciare tante freccette contro un bersaglio, contare quante entrano e quante no nel cerchio, e da questa pseudocasualitá simulata ricavare la stima di pigreco?  

E fare una griglia di punti al posto del casuale, ti risparmieresti la generazione di numeri casuali che per milioni di punti temo crei alla fine sempre gli stessi. Svolgeresti tantissimi calcoli ripetuti e forse inutili.

Python è un linguaggio molto versatile e può essere considerato sia interpretato che compilato allo stesso tempo, visto che in esecuzione genera automaticamente il bytecode come qualsiasi altro compilato.

Riguardo il parallelo basta aggiungere una manciata di codice e sei apposto.


FaSan



EDIT : ho fatto un piccolo test su una macchina virtuale, ed ho ottenuto il risultato PI con 1miliardo di punti in 8 minuti, sfruttando una singola cpu (virtualizzata). Dopo cena ho un pò più di tempo e ci applico il multithread, vediamo come và

Anch'io in poche righe mi sono scritto un programma che funziona, ma cercavo qualcosa di molto efficiente ( voglio generare migliaia di miliardi di punti) quindi mi serve un programma

1) compilato e non interpretato
2) che sfrutti in parallelo tutti i core della cpu

Questo, in python, fà esattamente quello che ti serve e in poche righe :


https://gist.github.com/jmateus/18f453b0e613e1667030




Ciao, FaSan

Tante belle idee, grazie! 

[OT]
Qui' ci sono approfondimenti sulle terne pitagoriche interessanti... puoi proporre agli alunni il quesito e rientra anche tutto il discorso della radice di un intero ... ovviamente essendo da 0 a 1 bisogna passare dai numeri Q ma il concetto è quello delle terne pitagoriche ...
Ad esempio 0.6^2+0.8^2=1 ...
[/OT]

Allora: a casa ho un portatile con un Intel Core 2 Duo 8700 2.53 Ghz (ha 6 anni), a scuola spero di avere qualcosa di meglio (anche se ovviamente a casa ho più tempo per fare esperimenti).
Dai tuoi tempi le prestazioni mi sembrano davvero scarse  , sarà merito anche del compilatore free pascal che dicono siano uno dei migliori quanto a efficienza del codice prodotto.


Sì, ma non cambierebbe nulla. La probabilità di generare un punto che sta "esattamente" su una circonferenza (quindi sul "contorno" del cerchio) è 0, nel senso che se stai lavorando con misure di superficie (come nel mio caso, aree di cerchi e aree di quadrati), la misura unidimensionale di una circonferenza ha una misura nulla rispetto alle altre.
Detto in altre parole, prova a far girare il tuo programma con la condizione x*x+y*y=1.0, e dopo 1 miliardo di tentativi guarda quanto vale num_centri... 

Quello che hai detto è giusto, ho comunque provato, per curiosità, a far girare il mio codice (in realtà leggermente cambiato per ottimizzarlo un po) e siamo su questi tempi:

Questo su un Intel(R) Core(TM) i5-4440 CPU @ 3.10GHz.

Diciamo che con 4 thread sono veloce come il tuo singolo circa però, se ad ora vuoi provarlo a farlo comunque girare, avendo tu 8 core, magari qualcosa di meglio di pascal ottieni, ma rimane molto "lento".

Oh se insisti a mandarli mandali eh   ma battute a parte, non l'ho fatto per i BTC


Sni.
I programmi per ati usano openGL in genere come libreria. Questa libreria è comunque supportata da nVidia, ma non è per nulla ottimizzata.
Infatti su nVidia bisognerebbe usare CUDA come scritto, che non va su ATI.

Per cui, se programmi in openGL puoi comunque farlo girare su nVidia ma le prestazioni sono pessime (Ed a volte se fai pesante uso di RAM non parte proprio).
E' il motivo per cui, per dire, cgminer (openGL) gira male su schede nVidia per minare, mentre ccminer (CUDA) è perfetto per nVidia ma non va sulle ATI.



PS.
Dal tuo codice:
if (x*x+y*y<1.0) then num_centri:=num_centri+1;
Ma non dovrebbe esser minore-uguale? Infatti, per dire, il punto (1,0) quindi uno dei vertici, fa come risultato dell'espressione proprio 1 quindi non soddisferebbe la funzione if, ma in realtà fa parte del cerchio essendo sulla circonferenza, no?

Ah, io per "pi song" intendevo semplicemente che chiederò agli studenti di provare a comporre loro qualcosa ispirandosi al pi greco, io non mi intendo molto di musica e quindi sulla conversione numeri-note non sarei di grande aiuto.


Abbiamo pensato anche a quello, ma è davvero sfuggente questa misura "curvilinea"! L'approssimazione migliore la dovremmo trovare facendo oscillare un pendolo molto lungo e invertendo la formula del periodo di oscillazione (il tempo si misura molto più facilmente)


Questo metodo non converge molto rapidamente, quindi non mi aspetto certo di determinare le prime 30 cifre decimali del pi greco (tra l'altro interverrebbero prima probabilmente anche aspetti di arrotondamento da studiarsi con l'analisi numerica).  Il mio obiettivo era 8-10 cifre (un errore di una parte su 10 miliardi non sarebbe affatto male!!), e generando fino a 500 miliardi di punti ho verificato che la stima continua a migliorare fino alla 5^ cifra decimale, quindi al momento mi concentro per aumentare la velocità di elaborazione, dopodichè lascerò girare il programma per un paio di giorni (se non mi si frigge la cpu  ) e solo allora potrò verificare se effettivamente il tutto funziona (secondo me per il tipo di precisione che cerco dovrebbe bastare).
Sarebbe anche interessante verificare quale sia il limite oltre al quale questa successione di approssimazioni  (dati i problemi da te citati sulla funzione random e quelli connessi all'analisi numerica) smetta di convergere a pi greco.

Una bimba, sentendola, mi ha detto ... ma non finisce piu' .... ci sono varie interpretazioni ma non ho mai provato effettivamente a suonarla ... a naso tenderei a trasformare il numero in base opportuna per le note musicali prima di suonarlo, se mai ci spostiamo di 3d e ne parliamo, non mi dispiacerebbe fare 4 chiacchiere su pi song ..


Battuta: se gli studenti non arrivano a risultati soddisfacenti li si puo' minacciare di farglieli rifare per l'altro pi greco day 22/7 (corso estivo di recupero) :-)

Pitagora l'ha fatto con i poligoni iscritti e circoscritti, forse si potrebbe avvolgere uno spago sui cilindri n volte e si misura la lunghezza dello spago o del filo da pesca se non si allunga troppo o del filo di rame (quello dei trasformatori) ... o ...

Io lo facevo fare con libre office, non ho mai avuto esigenze particolari e la funziona casuale()
 in effetti non mi ha mai preoccupato, non volevo trovare una stima ma far vedere un approccio.

http://www.cplusplus.com/reference/cstdlib/rand/
...
Return Value
An integer value between 0 and RAND_MAX.
Dove:
Maximum value returned by rand
This macro expands to an integral constant expression whose value is the maximum value returned by the rand function.

This value is library-dependent, but is guaranteed to be at least 32767 on any standard library implementation.

Quindi mi sa che alla fine son pochi numeri, vanno fatte delle inizializzazioni e se qualcuno esperto volesse intervenire potrei approfondire volentieri (per imparare!), so che ci sono delle librerie e delle discussioni in merito, se vuoi giocare allora va bene ma se parli di avere parecchie cifre di pi greco allora credo ci voglia un ragionamento serio su tale aspetto altrimenti meglio lasciar perdere (NB: la mia e' una sensazione non una certezza).

Intendevo chiavi private (che poi generano quella pubblica), e mi pareva anche di averci pensato prima di scrivere :-)
EDIT: forse vanity gen puo' aiutare e lui genera effettivamente chiavi pubbliche :-)

Bella l'idea della pi greco song, te la rubo!


Anche se un po' OT, il mio collega di fisica sta cercando di ideare un esperimento fisico in cui si misura una circonferenza, il suo diametro, e facendo il rapporto si dovrebbe ottenere una stima di pi greco. E' difficilissimo anche ottenere solo 3,14!  (causa errori sulle misure)
Ovviamente la parte difficile è misurare con precisione una circonferenza (che è curva  ), mentre con il calibro si riesce ad avere un'incertezza piccolissima sul diametro. Facendo rotolare molte volte un cilindro lungo un percorso speriamo di minimizzare l'incertezza sull'errore di misura della circonferenza.



Per quanto riguarda la generazione di numeri pseudo-casuali, ovviamente l'implementazione di quella funzione è cruciale per una buona stima finale del pi greco. Ad esempio avevo sentito dire che la funzione rand() di excel da questo punto di vista è scarsa (riporto semplicemente delle voci).

Ma io mi fido che la funzione "random" del pascal ( o  la funzione analoga in c )  sia implementata a dovere, non è possibile controllare tutto!

Forse il grado di accuratezza della stima di pi greco potrebbe essere un modo indiretto per stabilire la bontà o meno di una funzione di generazione pseudo-casuale di numeri. Come collegare questo discorso alla generazione delle chiavi pubbliche ( perchè non quelle private? ) dei bitcoin sinceramente non saprei.

A naso direi che il problema piu' grosso e' gestire la precisione anche del sorteggio e soprattutto la generazione dei numeri casuali, prestate attenzione a questo aspetto e probabilmente si puo' prendere spunto dalla generazione delle chiavi pubbliche.
Per il pi day io facevo anche pi greco song che mi affascina parecchio ...

Perfetto, allora qualcosa ci capisco  

Molto gentile, certo che è da 1 anno e mezzo che sono nel mondo bitcoin e non sono ancora riuscito ad acquistare/pagare nulla con i bitcoin   !


Ma quindi mi confermi che i programmi che girano su nvidia non girano su ati e viceversa?


Ho a disposizione una nVidia Geforce GT 730, e quindi da questa pagina http://www.nvidia.it/object/geforce-gt-730-it.html#pdpContent=2 deduco che dovrei avere 96 core (o 384, non ho capito quale sia il mio modello)


Io ero partito per fare questo lavoro per la scuola per il pi greco day, poi mi sono appassionato ben più del necessario (per i miei studenti dubito farà molta differenza se riuscirò a determinare una o due cifre decimali esatte in più  )
Ho scelto questo metodo per determinare pi greco perchè mi sembra molto semplice (noi matematici diremmo "elegante"), comprensibile e alla portata di tutti, anche se sono stati sviluppati altri metodi (ad esempio delle serie) che convergono a pi greco molto più rapidamente. Ma l'eleganza (e la possibilità per gli studenti di capire che cosa sta succedendo) vuole la sua parte...

Infine mi sono reso conto che l'algoritmo si prestava molto bene per essere parallelizzato, ma le mie competenze informatiche sono quelle che sono...

Grazie ancora!

Non avevo capito il grado di complessità su cui volevo andare per quello te lo avevo fatto in PHP al volo.

Per quel che riguarda la velocità il PHP a sto punto non fa al caso tuo, rimane comunque troppo "lento".

Tranquillo che non voglio nulla, come detto erano 20 righe di codice... Se no non te lo postavo in chiaro! XD

Per quel che riguarda le GPU invece non cambia il programma a seconda delle GPU ma del tipo di librerie che usi.
In particolare sulle GPU nVidia si programma in c usando CUDA, mentre sulle ati usando opencl.
Sicuramente per quello che devo fare le GPU sono perfette sfruttando le loro memorie interne e facendo tornare al programma principale direttamente il count.

Posso provare nel week end a metterti giù un paio di righe su CUDA ma solo se poi tu hai questa tecnologia. Inoltre nel caso ti darei il sorgente c ma non ti saprei indicare come compilarlo su windows.

Non lo farei per il compenso ma per divertimento e interesse personale nel programmare con CUDA ma se ci riesco (e non è scontato, non ho molto tempo in questo periodo) poi sul come portarlo su windows sarebbe opera tua!

Un paio di osservazioni:

con il mio programmino, per poter ottenere 3,14152, cioè le prime 5 cifre decimali esatte, ho dovuto generare circa 500 miliardi di punti (circa 10 ore di lavoro-macchina)

Secondo i più esperti, parallelizzare il programma e farlo girare su una gpu invece che su una cpu incrementerebbe di molto la velocità? Immagino che in quel caso di sicuro aumenterebbe di molto anche la complessità del programma e si perderebbe inoltre in portabilità (schede video di marca diversa --> diverse implementazioni del programma), giusto?

Grazie per le risposte!
Ho dato per scontato che mi contattaste prima di mettervi al lavoro, vi avrei dato qualche indicazione più precisa.

Mi serve :
- il multithread per una questione di ottimizzazione (sul mio portatile il mio programmino fa circa 1 miliardo di iterazioni al secondo)
- il tecnico di informatica della scuola in cui lavoro mi ha detto che i processori nella mia scuola sono quad-core, ciascuno con due thread, quindi potenzialmente posso fare un x 8 di incremento di velocità
- è importante che il programma gestisca variabile intere e reali molto grandi (devo poter generare anche mille miliardi di punti senza i limiti derivanti da variabili di tipo int o real)
- per davvo: penso che per lo scopo che mi prefiggo php non sia adatto perchè interpretato e quindi più lento (correggimi se sbaglio)
- per golikcoin: mi serve non solo l'eseguibile ma anche il sorgente per poter poi fare eventualmente anche delle modifiche e con l'occasione imparare poi a capire come funziona il multithread, (NB: il Pascal è il linguaggio che conosco e di cui ho già installato compilatore e ambiente di sviluppo, se mi proponi qualcos'altro tipo C ecc. se mi dai una mano a capire quali software su windows installare per poterlo compilare   )



Quindi riassumendo:
- ringrazio davvo (inviami un tuo indirizzo e ti invio un piccolo riconoscimento per il lavoro svolto)
- chiedo a golikcoin : che linguaggio hai usato? il tuo programma contempla l'uso di variabili molto grandi? Mandami pure l'exe e poi ci mettiamo d'accordo sul compenso.

Grazie.

PS: il programma mi serve per sabato 14 marzo (mese 3, giorno 14, anno 15 --> 3,1415) giorno del "pi greco day"   !

EDIT:
per golikcoin: dall'immagine del tuo programma l'algoritmo viene fatto girare 10 volte; a me servirebbe che l'algoritmo girasse anche 1 sola volta, ma che stampasse a video ogni x punti generati la stima parziale di pi greco (per poter così visualizzare il fatto che con il crescere dei punti generati migliora la stima);
quindi se ad esempio voglio generare 10 miliardi di punti con una stampa a video della stima ogni miliardo di punti , il programma dovrebbe:
- dividere il primo miliardo di punti da generare in 4 (ad esempio) thread da 250 milioni di punti ciascuno
- alla fine del primo ciclo aggiornare la variabile comune a tutti i thread: num_centri
- stampare la stima parziale di pi greco dopo il primo miliardo di punti
- quindi ridividere il secondo miliardo di punti in 4 thread, ....
- così fino al 10^ miliardo di punti

Ecco il mio programmino:
 

se vuoi ti ho fatto un exe, semplice sepmlice non so se sia corretto cmq questo è l'output


questa l'interfaccia



se è corretto rispondi pure qui che ti mando diretto l'exe

Non ho capito sinceramente se lo volevi per forza in pascal o ti andava bene qualsiasi linguaggio.

Ora, se lo volevi in pascal passo, non è il mio linguaggio.
Se ti va bene in altro (vedi php) ti ho messo giù una bozza.

Certo, non è ottimizzata nella comunicazione tra i thread (scrivono su un file alla fine, non proprio bello ma funzionale).
Il programma sembra funzionare e sfrutta tutte le cpu di cui disponi in modo parallelo per fare la "pioggia" di puntini all'interno del quadrato. Ogni thread fa la sua pioggia e poi si sommano i valori.

Il codice è il seguente, commentato, dovrebbe esser semplice da capire:


Come detto, dove lo lanci crea un file result.txt in cui scrivo i vari risultati.
Basta che lo prendi, lo salvi su un qualsiasi server unix (windows è più complicato da usare come thread per php) e lo lanci con php5-cli.

L'output che genera è il seguente:

Cerco un programmatore disposto a modificare (o sarebbe meglio dire a riscrivere  ) un mio piccolissimo programmino (< 100 righe di codice!).  Ovviamente pago in btc.

Il programmino in questione non c'entra nulla con il mondo bitcoin, è una semplice implementazione del metodo Monte Carlo per la stima del valore di pi greco.

L'idea è molto semplice, il programma genera dei "punti" casuali nel primo quadrante del piano cartesiano (una coppia di variabili pseudo-casuali comprese tra 0 e 1). Tutti questi punti quindi cadono necessariamente in un quadrato immaginario di vertici (0,0),(1,0),(1,1),(0,1). Poi il programma calcola quanti di questi punti cadono anche nel settore circolare (x^2 + y^2 <= 1,x>=0, y>=0). Se genero molti punti, il rapporto tra il numero di punti che cadono nel quarto di cerchio e quelli totali che cadono nel quadrato è all'incirca uguale al rapporto tra le aree delle due figure, cioè pigreco / 4.

Qui di seguito l'algoritmo di base del programma (è in Pascal):


Il programma di per sè funziona, volevo  farne però una versione "multithread"*; non mi intendo affatto di questa tecnica di programmazione e per questo chiedo l'aiuto di qualcuno che se ne intenda.

(*Ho dato un'occhiata a questo http://wiki.freepascal.org/Multithreaded_Application_Tutorial e ho capito che non ho il tempo/voglia di studiarmi da solo la cosa).


Grazie.