Piitä laskemaan

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Tein harjoitukseksi piin arvoa laskevan ruby-ohjelman.

Pitäisi saada tietää mikä on tarkasti laskettujen desimaalien ja laskukierrosten suhde kun käytetään tätä Baileyn laskukaavaa :

Tuohon on mm. siitä hyvä että uusi laskukierros aina tarkentaa edellistä kierrosta joten välituloksen voisi näyttää laskennan edetessä.

Tässä tämä koodi. Vauhtia laskentaan saisi muuttamalla laskukaavan binäärilaskennaksi.

#!/usr/bin/ruby -w
require "bigdecimal"

Big1=BigDecimal.new("1")
Big2=BigDecimal.new("2")
Big4=BigDecimal.new("4")
sum=BigDecimal.new("0")
n = ARGV[0].to_i

n.times do |j|
sum += (Big4/(8*j+1)-Big2/(8*j+4)-Big1/(8*j+5)-Big1/(8*j+6))/16**j
end

# Tarkkojen desimaalien lkm on noin 1.2 x n eli 6/5
lkm=6*n/5
string = sum.round(lkm).to_s("6F")
aika=Process.times
puts "User time : #{aika.utime}\nSys time : #{aika.stime}\n#{string}"

Sivut

Kommentit (17)

Vierailija

Eikö tuossa kannata käyttää potenssiinkorotuksen (16**j) sijasta muuttujaa, joka kerrotaan kullakin kierroksella tekijällä 16. On varmasti huomattavasti nopeampi. Ellei sitten kieli osaa sitä itse optimoida jollain tapaa.

Vierailija
korant
Eikö tuossa kannata käyttää potenssiinkorotuksen (16**j) sijasta muuttujaa, joka kerrotaan kullakin kierroksella tekijällä 16. On varmasti huomattavasti nopeampi. Ellei sitten kieli osaa sitä itse optimoida jollain tapaa.



Kielestä riippumatta mikäli halutaan nopeutta ja muuttujan (tässä tapauksessa j) maksimiarvo tiedetään, kannattaa mahdollisimman moni arvoista laskea etukäteen ja tallentaa ohjelmakoodiin konstantti-taulukoiksi. Tällöin vaihdetaan prosessoriaikaa muistin kulutukseen.

Esimerkiksi yksi taulukko voisi olla 8*j -taulukko josta löytyy laskutoimituksen 8*j tulos parametrin j mukaan indeksoituna. Toinen taulukko tuo 16**j.

Nämä ovat tietysti tällaisia implemntaatioon perustuvia juttuja, algoritmin muutokset yleensä tuovat isompia parannuksia nopeuteen.

Vierailija

Tein pari ehdotettua muutosta laskentaan. Tämä tulostaa mm. käytetyn ajan 100 kierroksen välein. Oli tarkoitus tehdä sellainen 'cool' versio joka tulostaa konsolille jatkuvasti lisää ratkenneita desimaaleja laskennan edetessä. Voisi myös tallettaa laskennan tiedostoon ja jatkaa edellisestä kohdasta. Onko c-kielelle saatavissa 64bittistä binäärilaskukirjastoa? Jos intoa riittää niin voisi tuon laskukaavan tehdä c-kielisenä 64 bittisillä binääriluvuilla. Ja jos sen jälkeen intoa riittää niin laskennan voisi jakaa neljälle prosessorille.

#!/usr/bin/ruby -w
require "bigdecimal"

Big1=BigDecimal.new("1")
Big2=BigDecimal.new("2")
Big4=BigDecimal.new("4")
sum = BigDecimal.new("0")
kasij=0
jakaja=1
n = ARGV[0].to_i
user_time=0
dtime=0

n.times do |j|
sum += (Big4/(kasij+1)-Big2/(kasij+4)-Big1/(kasij+5)-Big1/(kasij+6))/jakaja
kasij+=8
jakaja=jakaja*16
if j%100 == 0
dtime=user_time
user_time=Process.times.utime
dtime=user_time-dtime
puts "Kierros : #{j} Kok. aika : #{user_time} Delta time #{dtime}\n"
end
end

# Tarkkojen desimaalien lkm on noin 1.2 x n eli 6/5
lkm=6*n/5
string = sum.round(lkm).to_s("6F")
user_time=Process.times.utime
puts "User time : #{user_time}\n#{string}\n"

Vierailija

Tuota 16^i laskua ei oikein taulukoitua saa, kun sen i:n yläraja on ääretön. Helpompaa olisikin korvata tuo laskutoimitus muuttujalla, jossa on aina tallessa edellinen arvo ja kertoa se 16:lla joka kierroksella ja tallettaa uusi arvo. Näin välttyy laskemasta joka kierroksella yhä enemmän ja enemmän kertolaskuja.

Vierailija
abskissa
Muistaakseni korantilla oli siihen jokin nopeasti suppeneva ja numeerisesti toimiva kehitelmä.
Se oli juuri tuo sama kuin Lydellä.

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008

No mutta. Muistini on yllättävän lyhyt.

Noissa BigDecimaleissakin on se ongelma, että tarkka laskenta ei välttämättä onnistu. Esim. 1/3:aa ei voi esittää BigDecimalina. Jos haluat tarkkoja tuloksia, laske koko homma rationaalisena, ja käytä osoittajalle ja nimittäjälle arbitrary precision(*) -kokonaislukuja (olisiko Rubylla BigInteger). Tuota tarkoitusta varten voi vaikka tehdä tai kaivaa jostain käyttöön BigRational-luokan, niin saa rationaalilukujen laskutoimitukset siististi (joskin luultavasti hitaasti) hallittua.

Jos epäilee, että kääntäjä (tai Rubyn tapauksessa tulkki) ei osaa oikein optimoida, niin nuo 2:n potensseilla kertomiset ja jakamiset voi tehdä ihan vaan bit-shifteillä.

Siis

x = x*16

-->

x = x << 4

(tai sinne päin -- mahdollisen etumerkin käyttäytymisen joudut selvittämään)

Shiftaus voi olla myös nopeampaa kuin taulukosta haku, sillä sitä vastaa suoraan yksinkertainen konekielioperaatio, kun taas taulukosta haku saattaakin olla Rubyn tapauksessa melko monimutkaista.

Ruby on kyllä näppärä kieli, mutta sen tulkkien suoritusnopeudesta on ainakin minulla suorastaan karmeita kokemuksia.

(*) Täällä ei saanut käyttää suomennosta "mielivaltainen tarkkuus", kun menee joillain heti herne nenään.

We're all mad here.

Vierailija
abskissa

Noissa BigDecimaleissakin on se ongelma, että tarkka laskenta ei välttämättä onnistu. Esim. 1/3:aa ei voi esittää BigDecimalina. Jos haluat tarkkoja tuloksia, laske koko homma rationaalisena, ja käytä osoittajalle ja nimittäjälle arbitrary precision(*) -kokonaislukuja (olisiko Rubylla BigInteger).



BigDecimal dokumentti kertoo ensimmäisellä rivillä :

BigDecimal provides arbitrary-precision floating point decimal arithmetic.

Juu. Homman voisi tehdä kokonaisluvuilla ja lopuksi tallettaa n, osoittaja ja nimittäjä. Noin voisi mukavasti aina jatkaa laskemista edellisestä tarkasta arvosta. Kokonaisluvuilla laskiessa sitten pitäisi olla nopea tapa selvittää suuren luvun alkutekijät (joiden avulla voi laskea pienimmän yhteisen jakajan).

abskissa

Jos epäilee, että kääntäjä (tai Rubyn tapauksessa tulkki) ei osaa oikein optimoida, niin nuo 2:n potensseilla kertomiset ja jakamiset voi tehdä ihan vaan bit-shifteillä.



Vaihdoinkin kasilla ja 16:sta kertomisen << toimintoon.

Vierailija
Lyde

Kokonaisluvuilla laskiessa sitten pitäisi olla nopea tapa selvittää suuren luvun alkutekijät (joiden avulla voi laskea pienimmän yhteisen jakajan).



Eipä tarttekkaan. Tässä lainaus sfnet keskusteluryhmästä :

"On tämmöinen: annetun lukujonon pienimpiin lukuihin lisätään toistuvasti vastaava alkuperäinen luku kunnes jonon alkiot ovat yhtä suuret, jolloin jono on alkuperäisen jonon (pyj, pyj, ..., pyj).

Wikipediassa (Least Common Multiple) oli selitys ja linkki.

Tiedostossa pyj.py:

def pyj(x0):
xm = x0
while min(xm) < max(xm):
xm = [ xmk if xmk > min(xm) else xmk + x0k
for (x0k,xmk) in zip(x0,xm) ]
return xm
"

Vierailija

Aloin tässä lomalla pohtimaan että millainen olisi piin laskemiseen digitaalitekniikan piireistä ja moduleista koottu kone tai kytkentä? Pitäisi siis toteuttaa muutama laskutoimitoimitus binäärimuodossa rekistereillä samoin kuin CPU tekee sisäisesti mutta rekisterit ja kytkennät olisi optimoitu pelkästään laskemaan piin arvoa. Esim. kaavassa esiintyvä 16 kertominen on vallan helppo tehdä lisäämällä binääriluvun perään nollia eli siirtämällä lukua rekisterissä vasemmalle 4 askelta. Jakolasku onkin sitten vaikeampi. Miten lienee jakolaskut toteutettu prosessorin sisällä? Vai onko ne tehty softalla eli prosessorit eivät tekisi jakolaskuja raudassa?

o_turunen
Seuraa 
Viestejä10596
Liittynyt16.3.2005

Eiköhän jakolasku ole tehty vähentämällä jakaja osoittajasta. Kun sopivasti siirretään jakajaa, niin lasku onnistuu sujuvasti. Joskus TKK:n fysiikan labrassa eräs neropatti pisti mekaanisen koneen jakamaan miljoonan ykkösellä. Puolessa päivässä kone oli päässyt suunnilleen 1E5 hujakoille; se kun ei osannut siirtää jakajaa sopivalle kohdalle.

intelin koneissa on ihan valmiina div-käsky. Varmaan monissa muissakin.

Korant: Oikea fysiikka on oikeampaa kuin sinun klassinen mekaniikkasi.
Korant: Jos olet eri mieltä kanssani olet ilman muuta väärässä.

Neutroni
Seuraa 
Viestejä26832
Liittynyt16.3.2005
Lyde
Aloin tässä lomalla pohtimaan että millainen olisi piin laskemiseen digitaalitekniikan piireistä ja moduleista koottu kone tai kytkentä?



Mikroprosessoria optimoidumpaa ei juuri ole. Tai GPU:ta, jos se lasku rinnakkaistuu, mutta ei se taida helposti rinnakkaistua. Toki noista voisi jättää joitain toimintoja pois.

Pitäisi siis toteuttaa muutama laskutoimitoimitus binäärimuodossa rekistereillä samoin kuin CPU tekee sisäisesti mutta rekisterit ja kytkennät olisi optimoitu pelkästään laskemaan piin arvoa.



Ihan samoilla operaatiolla piitä lasketaan kuin kaikkea muutakin.

Jakolasku onkin sitten vaikeampi. Miten lienee jakolaskut toteutettu prosessorin sisällä? Vai onko ne tehty softalla eli prosessorit eivät tekisi jakolaskuja raudassa?



Mikrokoodina, eli se prosessori tekee tietyn monivaiheisen algoritmin tiettyjen rekisterien välillä. Jakoalgoritmeja löytyy ainakin mikrokontrollerivalmistajien application noteista, koska niissä se pitää koodata ihan itse assemblerilla.

Vierailija
Neutroni

Mikroprosessoria optimoidumpaa ei juuri ole. Tai GPU:ta, jos se lasku rinnakkaistuu, mutta ei se taida helposti rinnakkaistua. Toki noista voisi jättää joitain toimintoja pois.



Kyllä laskutoimituksen helposti jakaa muutamaan säikeeseen. Tässä versio joka laskee neljässä säikeessä suurimmat kerto/jakolaskut. Tässä versiossa annetaan tiedostonimi parametrinä ja tulos pukataan 60s välein tiedostoon. Pitänee tutkia vielä GPU:n käyttöä kirjaston avulla.

#!/usr/bin/ruby -w
require "bigdecimal"

Big1=BigDecimal.new("1")
Big2=BigDecimal.new("2")
Big4=BigDecimal.new("4")
pii,s1,s2,s3,s4 = BigDecimal.new("0")
kasij=0
jakaja=1
tnimi = ARGV[0].to_s
user_time=0
dtime=0
j=0

while true do
j += 1
t1 = Thread.new { s1=Big4/((kasij+1)*jakaja) }
t2 = Thread.new { s2=Big2/((kasij+4)*jakaja) }
t3 = Thread.new { s3=Big1/((kasij+5)*jakaja) }
t4 = Thread.new { s4=Big1/((kasij+6)*jakaja) }
# Odotetaan välilaskujen valmistumista :
t1.join
t2.join
t3.join
t4.join
pii += (s1-s2-s3-s4)
kasij += 8
jakaja=jakaja<<4
if (dtime+60) > (Process.times.utime)
dtime=user_time
user_time=Process.times.utime
dtime=user_time-dtime
string = pii.to_s("6F")
open (tnimi,'w') {|f|
f.puts "Kierroksia : #{j}\nUser time : #{user_time}\nAika per kierros : #{dtime}\nPii : \n#{string}\n"
}
end
end

Vierailija
Neutroni
Lyde
Aloin tässä lomalla pohtimaan että millainen olisi piin laskemiseen digitaalitekniikan piireistä ja moduleista koottu kone tai kytkentä?



Mikroprosessoria optimoidumpaa ei juuri ole. Tai GPU:ta, jos se lasku rinnakkaistuu, mutta ei se taida helposti rinnakkaistua. Toki noista voisi jättää joitain toimintoja pois.

Varta vasten tiettyjä tehtäviä varten suunnitellut FPGA- ja ASIC-piirit ovat monta kertaluokkaa tehokkaampia juuri tälläisiä tehtäviä varten.

http://www.extremetech.com/computing/133110-are-fpgas-the-future-of-pass...

Sivut

Uusimmat

Suosituimmat