Topic: Discussione sul pi greco (Read 5255 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?