Topic: Discussione sul pi greco - page 2. (Read 5321 times)

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.