![[RSS]](http://tweakimg.net/g/if/v2/icons/rss_small.png){kind=icon}
Pi datumvinder
Laat ik nou eindelijk, na al die tijd, de magische grens van 5k karma hebben overschreden. Hoezee.
Tijd dus om een blog te starten om jullie tweakers te voorzien van leesvoer.
De post van vandaag: een recent geschreven programmaatje dat een flinke berg decimalen van pi doorzoekt naar een ingevulde reeks getallen, een geboortedatum bijvoorbeeld.
Hier een kort filmpje dat demonstreert wat 't programma doet.
Het is eigenlijk ontzettend simpel om zoiets in elkaar te zetten maar het is wel leuk om er even mee te spelen. Momenteel heb ik het geschreven in VB.net maar ik ga het herprogrammeren naar Python, dan heb ik gelijk een leuke manier om spelenderwijs de taal machtig te worden.
De werking is als volgt:
Eerst heb ik met het programma Ycruncher ruim 5 miljard decimalen van pi berekend en deze in een .txt bestand gezet.
Dit alles duurde net iets meer dan 6 uur op mijn Phenom X4 met 8GB ram.
Het programma dat ik geschreven heb leest vervolgens deze lange sliert getallen in in blokken van 2000 decimalen (een vrij willekeurig gekozen getal), legt blok N en blok N-1 naast elkaar en kijkt of de opgegeven reeks getallen voorkomt in deze 2 blokken.
Het in 1x inlezen van een reeks getallen van 5GB is namelijk niet haalbaar en het naast elkaar leggen van de blokken is gedaan om te voorkomen dat je bijvoorbeeld een blok [141] en een blok [592] hebt en je zoekt naar de reeks getallen '15' dat het getal niet voorkomt in noch blok 1 noch in blok 2 en het gezochte getal dus niet wordt gevonden.
Uiteindelijk kan dit programma 1 miljard decimalen doorzoeken in ongeveer 16 seconden. Vanzelfsprekend is dit verre van optimaal maar er is dan ook nog zat ruimte voor verbetering.
Omdat er maar 10 verschillende cijfers mogelijk zijn in de deelverzameling decimalen van pi en er 256 asciicodes zijn is het mogelijk 2 decimalen in 1 asciicode te stoppen en de benodige hardeschijfruimte te halveren, in ruil voor een iets complexere berekening.
in de trend van het ruilen van hardeschijfruimte voor rekenkracht zal ik nog kijken naar een manier de getallen te indexeren. Hoewel het natuurlijk mogelijk is dit te googlen ga ik er eerst nog even voor zitten zelf een manier te bedenken dit te realiseren. Het schenkt me veel meer genoegen zelf manieren te bedenken het programma sneller te maken en het zelf ook te schrijven dan het voorgekauwd krijgen.
Ook is het doorzoeken van 5 miljard decimalen nogal overbodig als je kijkt naar de kans dat een 8 cijferige geboortedatum voorkomt in een N decimalen lange reeks decimalen van pi.
Laat het zo zijn dat je altijd zoekt naar een 8-cijferig getal, dan zijn er dus 10^8 mogelijke getallen.
De kans dat deze voorkomt in een 8 cijferig getal is logischerwijs 1 op 10^8.
De kans dat een reeks van 8 cijfers voorkomt in een reeks van 1 miljard cijfers is echter 0.9999, namelijk:
de kans dat de gezochte reeks cijfers NIET voorkomt op plek 1, 1-(1/10^8), maal de kans dat de gezochte reeks niet voorkomt op plek 2 etc. tot plek 1 000 000 000 is (1-(1/10^8)) ^ (10^9)
is een grafische weergave van kansen. op de X as de lengte van de string die je zoekt, op de Y as de hoeveelheid decimalen van pi en de uitkomst is de kans dat jouw string voorkomt in Y decimalen.
concluderend zijn 5 miljard decimalen onnodig veel om elke denkbare datum of reeks getallen te zoeken.
Ten slotte lijkt het me nog leuk om veel meer 'weet'jes' over de ingevoerde geboortedatum te geven. Onder andere getal e en wortel 2 kan ik op dezelfde manier doorzoeken maar ook de berekening of jouw geboortedatum priem is zou leuk zijn als uitvoer.
Tijd dus om een blog te starten om jullie tweakers te voorzien van leesvoer.
De post van vandaag: een recent geschreven programmaatje dat een flinke berg decimalen van pi doorzoekt naar een ingevulde reeks getallen, een geboortedatum bijvoorbeeld.
Hier een kort filmpje dat demonstreert wat 't programma doet.
Het is eigenlijk ontzettend simpel om zoiets in elkaar te zetten maar het is wel leuk om er even mee te spelen. Momenteel heb ik het geschreven in VB.net maar ik ga het herprogrammeren naar Python, dan heb ik gelijk een leuke manier om spelenderwijs de taal machtig te worden.
De werking is als volgt:
Eerst heb ik met het programma Ycruncher ruim 5 miljard decimalen van pi berekend en deze in een .txt bestand gezet.
Dit alles duurde net iets meer dan 6 uur op mijn Phenom X4 met 8GB ram.
Het programma dat ik geschreven heb leest vervolgens deze lange sliert getallen in in blokken van 2000 decimalen (een vrij willekeurig gekozen getal), legt blok N en blok N-1 naast elkaar en kijkt of de opgegeven reeks getallen voorkomt in deze 2 blokken.
Het in 1x inlezen van een reeks getallen van 5GB is namelijk niet haalbaar en het naast elkaar leggen van de blokken is gedaan om te voorkomen dat je bijvoorbeeld een blok [141] en een blok [592] hebt en je zoekt naar de reeks getallen '15' dat het getal niet voorkomt in noch blok 1 noch in blok 2 en het gezochte getal dus niet wordt gevonden.
Uiteindelijk kan dit programma 1 miljard decimalen doorzoeken in ongeveer 16 seconden. Vanzelfsprekend is dit verre van optimaal maar er is dan ook nog zat ruimte voor verbetering.
Omdat er maar 10 verschillende cijfers mogelijk zijn in de deelverzameling decimalen van pi en er 256 asciicodes zijn is het mogelijk 2 decimalen in 1 asciicode te stoppen en de benodige hardeschijfruimte te halveren, in ruil voor een iets complexere berekening.
in de trend van het ruilen van hardeschijfruimte voor rekenkracht zal ik nog kijken naar een manier de getallen te indexeren. Hoewel het natuurlijk mogelijk is dit te googlen ga ik er eerst nog even voor zitten zelf een manier te bedenken dit te realiseren. Het schenkt me veel meer genoegen zelf manieren te bedenken het programma sneller te maken en het zelf ook te schrijven dan het voorgekauwd krijgen.
Ook is het doorzoeken van 5 miljard decimalen nogal overbodig als je kijkt naar de kans dat een 8 cijferige geboortedatum voorkomt in een N decimalen lange reeks decimalen van pi.
Laat het zo zijn dat je altijd zoekt naar een 8-cijferig getal, dan zijn er dus 10^8 mogelijke getallen.
De kans dat deze voorkomt in een 8 cijferig getal is logischerwijs 1 op 10^8.
De kans dat een reeks van 8 cijfers voorkomt in een reeks van 1 miljard cijfers is echter 0.9999, namelijk:
de kans dat de gezochte reeks cijfers NIET voorkomt op plek 1, 1-(1/10^8), maal de kans dat de gezochte reeks niet voorkomt op plek 2 etc. tot plek 1 000 000 000 is (1-(1/10^8)) ^ (10^9)
is een grafische weergave van kansen. op de X as de lengte van de string die je zoekt, op de Y as de hoeveelheid decimalen van pi en de uitkomst is de kans dat jouw string voorkomt in Y decimalen.concluderend zijn 5 miljard decimalen onnodig veel om elke denkbare datum of reeks getallen te zoeken.
Ten slotte lijkt het me nog leuk om veel meer 'weet'jes' over de ingevoerde geboortedatum te geven. Onder andere getal e en wortel 2 kan ik op dezelfde manier doorzoeken maar ook de berekening of jouw geboortedatum priem is zou leuk zijn als uitvoer.