Discussione sul pi greco

[bertani]

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

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"

[arulbero]

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

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"

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) ?

[arulbero]

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.

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.

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.

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 ...)

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.

[a.denis1]

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  !

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):

Code:

for i:=1 to num_punti do
          begin
               x:= random ;
               y:= random ;

               if (x*x+y*y<1.0) then num_centri:=num_centri+1;
          end;


          num_centri_reale:=num_centri;
          num_punti_reale:=num_punti;

          stima_pi_greco:=4.0*num_centri_reale/num_punti_reale;
          writeln('');
          writeln('Stima di Pi greco dopo ',i,' punti: ', stima_pi_greco:1:9);

          pi_greco:=3.1415926535;
          writeln('Valore esatto Pi greco:                 ', pi_greco:1:9);

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.

[picchio]

(...)
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 (...)

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 ...

[arulbero]

(...)
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 (...)

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 ...

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.

[picchio]

Riesumiamo oggi questo 3d, oggi è il 3.14

[duesoldi]

Riesumiamo oggi questo 3d, oggi è il 3.14

Ti eri segnato un memo tre anni fa ?!?