Keskustelu: Ohjelmointikysymykset: [VB.NET] Piin laskennan nopeutus

Moi!

Katsoin VB.NET:in koodivinkeistä Pitkä matikka -vinkkiä, sitten kopioin sen ja muokkasin sitä. Nyt sillä pystyy laskemaan noin 1200 - 1800 desimaalia. Ongelmana on hitaus. Se laskee minun koneellani (prosessori Intel® Core^TM i3-380M, 6 GB DDR3 muistia) 1024 desimaalia noin 20 minuutissa. Saako tuota nopeutettua (esim. säikeillä)?

Ohjelmassa on jo yksi säie, joka hoitaa konsoliin tulostamisen (siitä ei kyllä ole hyötyä kuin siinä, että konsoli ei ehdi niin nopeasti täyttyä, koska se sleeppaa välillä).

Saa sitä nopeutettua, yksinkertaisesti tekemällä järkevämmän pitkä matikka koodin. Tai löytyyhän niitä kunnollisia netistäkin.

Säikeistämisellä voi toki hakea suorituskykyä ainakin yhteen- ja vähennyslaksuissa, jakamalla luvun prosessoriytimien määrään. Huonolla tuurilla yksi prosessori joutuisi silti tekemään koko laskun. Sinänsä tuossa tulee niin paljon lisälogiikkaa, että tuskin kannattaa noin lyhyillä luvuilla mitä käytät. Lisäksi kun ihan bitarraystä vaikka 64-bittisten lukujen käyttöön siirtäminen toisi helposti 30 kertaisen tehonlisäyksen, niin tuskin kannattaa säikeistystä ensimmäiseksi miettiä, ellei sinulla ole yli 30 corea.

Mahtuuko 64 -bittiseen lukuun yli kaksi tuhatta numeroa? BitArrayt ovat hyviä erittäin suurten lukujen kanssa.
Ajattelin jos For...Next luupeissa vois tehdä näin:

'Esimerkki funktiosta MulBy2

Private Shared Function MulBy2(ByVal B As System.Collections.BitArray) As System.Collections.BitArray
        'MulBy2= B *2
        Dim K As Integer = MAXBITS - 1
        Dim A As New System.Collections.BitArray(MAXBITS)
        Dim i As Integer
        For i = K To 1 Step -2 'Hypätään kahdella
            A.Item(i) = B.Item(i - 1)
            If i = 1 Then Exit For
            A.Item(i - 1) = B.Item(i - 2)
        Next
        A.Item(0) = False
        Return A
    End Function

ErroR++ kirjoitti:

Mahtuuko 64 -bittiseen lukuun yli kaksi tuhatta numeroa? BitArrayt ovat hyviä erittäin suurten lukujen kanssa.

Mahtuuko 1-bittiseen lukuun yli kaksi tuhatta numeroa? LongArrayt (Long=64bit) ovat hyviä erittäin suurten lukujen kanssa.

Säilyttäisin siellä luultavasti 32 bittiä per alkio, koska kaksi 32-bittistä lukua voi kertoa keskenään jolloin saa 64-bittisen luvun ja yhteenlaskussakin taitaa olla kätevämpää laskea 32-bittisiä lukuja yhteen kun Carry-lippua ei kuitenkaan korkean tason kielissä pääse hypistelemään.

Oho, taidan siirtyä niihin. Eli nyt vain muuntamaan tuota BitArr -luokkaa LongArraylle.
Kiitos!

ErroR++ kirjoitti:

Se laskee minun koneellani (prosessori Intel® Core^TM i3-380M, 6 GB DDR3 muistia) 1024 desimaalia noin 20 minuutissa.

Juu, hidas on... ;-) Infernon mukana tulee Limbolla kirjoitettu toteutus, mikä laskee omalla koneellani 10 000 desimaalia vajaassa minuutissa.

Vinkkinä vaan, että tuo kääntynee kohtuullisen pienellä vaivalla Limbosta muillekin ohjelmointi kielille...

Ai niin, tuo toteutus löytyy siis Infernon /appl/math/ hakemistosta.

Ihan kuin .Netille ei löytyisi hyviä implementaatiota suoraankin, kuten ensimmäisessä viestissäkin mainitsin.

Grez kirjoitti:

Ihan kuin .Netille ei löytyisi hyviä implementaatiota suoraankin, kuten ensimmäisessä viestissäkin mainitsin.

No pistäpäs joku hyvä n. 400 rivin mittainen toteutus näkyville.

Mainitsit ensimmäisessä viestissä myös, että viestiketjun aloittajan kannattaisi vaihtaa BitArrayt LongArray:iksi. Eiköhän tavu ja int taulukoilla pärjää kuitenkin ihan hyvin...

Toki puolet tai kahdeksan kertaa pienempää voi käyttää, ei se ole kerto- ja jakolaskuissa kuin 4 tai 64 kertaa hitaampaa. Itse en vaan ihan hirveästi näe hyötyä käyttää pisintä käytännöllistä muuttujatyyppiä lyhyempää.

Oma AMD Athlon 64 3500+ laski piin 10 000 desimaalia Pythonilla about sekunissa. Alku ainakin näyttää ihan piiltä.

http://en.literateprograms.org/Pi_with_Machin­'s_formula_(Python)

Macro kirjoitti:

Oma AMD Athlon 64 3500+ laski piin 10 000 desimaalia Pythonilla about sekunissa. Alku ainakin näyttää ihan piiltä.

Tuo mainitsemani Inferno toteutus pääsee JIT-käännös päällä omalla koneellani suurinpiirtein samoihin aikoihin. Normaalisti en pidä tuota JIT-käännöstä päällä, kun se vaikeuttaa ohjelmien debuggausta ja omassa käytössäni nopeusero merkityksetön.

Grez kirjoitti:

yhteenlaskussakin taitaa olla kätevämpää laskea 32-bittisiä lukuja yhteen kun Carry-lippua ei kuitenkaan korkean tason kielissä pääse hypistelemään.

Monessa korkeamman tason kielessä tuon carryn voi onneksi emuloida. Esimerkiksi itse toteutin PL/I:llä datatähden ykköstehtävän suurien lukujen laskennan harrastemielessä:

PL/I:ssä löytyy desimaali datatyypit ja tuki picture formaatille. Merkkijonoilla voi yhteenlaskentaa tehdä helposti 17 numeroa kerrallaan. Käyttämäni PL/I kääntäjä käyttää desimaaliluvuilla laskemiseen FPU:ta ja maksitarkkuus on tällöin 18 numeroa. Laskemalla luvusta yhteen 17 numeroa kerrallaan, voidaan tulos sijoittaa 18 numeron mittaiseen picture formaatti esitykseen. Tästä esityksestä saadaan carry kopioimalla ensimmäinen merkki ja esityksen loput 17 merkkiä ovat tietenkin lasketut tuloksen 17 numeroa. Nämä 17 numeroa picture formaatista liitetään tulos merkkijonoon, haetaan luvun seuraavat 17 numeroa ja lisätään carry...

Niin, eli teit tuon saman: Jätit muuttujaan tilaa.

Tietty pelkkää yhteenlaskua ajatellen voisi käyttää 63-bittisiä, mutta kun ajattelin myös kertolaskua jossa kaksi 32-bittistä keskenään kerrottaessa saadaan 64-bittinen, niin saman tien sitten välttää turhaa shiftailua ja säätämistä ja tallettaa vain 32 bittiä.

Macro kirjoitti:

Oma AMD Athlon 64 3500+ laski piin 10 000 desimaalia Pythonilla about sekunissa. Alku ainakin näyttää ihan piiltä.

http://en.literateprograms.org/Pi_with_Machin­'s_formula_(Python)

Ainakin sata ensimmäistä desimaalia meni oikein (varmaankin muutkin meni oikein).
Tuota tarvitsinkin, muutan sen nyt VB:lle.
Kiitos kuitenkin kaikille!

Voisiko joku muuntaa tuon VB:lle? En itse saanut sitä oikein muunnettua. Koodi näytti ihan hyvältä, mutta kun debuggasin niin tuli joku runtime-errori. Yritin muuntaa viisi kertaa.

Miksi jonkun pitäisi muuntaa se VB:lle? Jos haluat valmiin ohjelman, niin niitä löytyy netistä, vaikka SuperPI. Tai mikset käytä sitä python-koodia. Tuskin tarvitset piin laskentaa osana jotain muuta sovellusta, joka olisi tehty VB.Netillä, koska tarkkoja piin arvoja nyt ei käytännössä tarvitse mihinkään konkreettiseen.

"joku runtime-errori"? XD

Voisiko virhe olla overflow? Python käsittääkseni sisältää isojen lukujen tuen, joten jos porttaat sen VB.Netille, niin hommaa sille isojen lukujen kirjasto ja tee laskut sitä käyttäen.

Visual Studio 2010 kirjoitti:

OverflowException was unhandled

Kyllähän pythonillakin pärjää.

EDIT: Ja muuten on .NET Frameworkissakin suurten lukujen kirjasto, laitat sieltä Project -valikosta Add Reference ja siirryt välilehdelle .NET Components tms. Sieltä valitset vain System.Numerics ja painat OK -nappia.

Imports System.Numerics
Module PIModule
  Sub Main()
    Dim a As BigInteger = New BigInteger(1024) 'uusi bigInteger
    Dim b As New BigInteger(1024) 'alustetaan arvolla 1024 joka kyllä mahtuu jopa Shortiin
    Dim c As BigInteger = BigInteger.Subtract(a, b) 'vähennys
    If c Is BigInteger.Zero Then 'jos nolla
      System.Console.Write("Tämä tulostuu.")
    Else 'jos ei
      System.Console.Write("Nyt jotain meni kyllä pieleen!")
    End If
  End Sub
End Module