Vanha 30.05.12, 10:29   #1 (linkki)
 
Rekisteröitynyt: 08/2009
Viestejä: 203
9 potenssiin 9 potenssiin 9

Hei, näin tällaisen ketjun tiede.fi-sivustolla ja päätinpä tehdä tänne samanlaisen, josko täältä löytyisi hyviä koodareita...

Eli esittäkää täydellinen vastaus otsikon kysymykseen. Vinkki: vastauksen pituus on yli 300 miljoonaa numeroa, että kannattaa varmaan tehdä tekstitiedosto ja linkata se tänne.

Kuka ratkaisee nopeiten ja parhaimmalla algoritmilla.

Itse värkkäsin C# koodin, joka yrittää ratkaista ongelmaa, tunnin on kone nyt laskenut mutta en ole vielä vastausta saanut. Saa nähdä kauanko kestää. Postaan vastauksen tänne kun sen saan (jos saan).

Tässä oma koodini, kehitelkää lisää:

Koodi:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.IO;


namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger luku = new BigInteger();

            luku = BigInteger.Pow(9, 387420489);

            TextWriter tw = new StreamWriter("luku.txt");

            // write a line of text to the file
            tw.Write(luku);

            // close the stream
            tw.Close();

            Console.WriteLine("Homma ok");
            Console.ReadLine();

        }
    }
}
  Vastaa lainaten
Vanha 30.05.12, 10:35   #2 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Mikäs on tähän mennessä paras tulos?

Ilmeisesti siis halutaan laskea 9 ^ (9^9) eikä (9^9)^9 kuten otsikosta voisi päätellä.
  Vastaa lainaten
Vanha 30.05.12, 10:38   #3 (linkki)
 
Rekisteröitynyt: 08/2009
Viestejä: 203
Lainaus:
Alkuperäinen kirjoittaja Grez Näytä viesti
Mikäs on tähän mennessä paras tulos?
En tiedä, kunhan mielenkiinnosta kyselen.
Jos nyt joku keksii algoritmin joka ratkaisee tuon vaikka tunnin aikana niin olis jo kova sana.
  Vastaa lainaten
Vanha 30.05.12, 10:40   #4 (linkki)
 
Rekisteröitynyt: 08/2009
Viestejä: 203
Lainaus:
Alkuperäinen kirjoittaja Grez Näytä viesti
Mikäs on tähän mennessä paras tulos?

Ilmeisesti siis halutaan laskea 9 ^ (9^9) eikä (9^9)^9 kuten otsikosta voisi päätellä.
9^9^9 menee laskusääntöjen mukaan juuri 9 ^ (9^9).
  Vastaa lainaten
Vanha 30.05.12, 10:51   #5 (linkki)
 
Rekisteröitynyt: 05/2012
Viestejä: 1173
Päässälaskuna vaan...
__________________
Ostetaan: Aurelia Magenta/Aniara
Eat clean stay lean
  Vastaa lainaten
Vanha 30.05.12, 10:53   #6 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Mä veikkaan että tolla sun koodilla menee noin 670 tuntia. (Tai siis menis mun koneen prossulla).

Jollain HD6900:llä tai vastaavalla varmaan sais laskettua helposti alle tunnissa.
  Vastaa lainaten
Vanha 30.05.12, 10:56   #7 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Lainaus:
Alkuperäinen kirjoittaja Slaya83 Näytä viesti
9^9^9 menee laskusääntöjen mukaan juuri 9 ^ (9^9).
Joo, 9^9^9 eli toki meneekin, mutta myös (9^9)^9 voisi lukea kuten otsikossa. Riippuu missä kohdassa pitää tauon.
  Vastaa lainaten
Vanha 30.05.12, 10:58   #8 (linkki)
 
Rekisteröitynyt: 08/2009
Viestejä: 203
Lainaus:
Alkuperäinen kirjoittaja Grez Näytä viesti
Mä veikkaan että tolla sun koodilla menee noin 670 tuntia. (Tai siis menis mun koneen prossulla).

Jollain HD6900:llä tai vastaavalla varmaan sais laskettua helposti alle tunnissa.
Miten laskit tuon 670 tuntia? Olis kiva tietää, että sammutanko jauhamisen saman tien vain annanko oman koneeni yrittää...

ja HD6900??? mikä se on? näytönohjain?? wat?
  Vastaa lainaten
Vanha 30.05.12, 11:24   #9 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Lainaus:
Alkuperäinen kirjoittaja Slaya83 Näytä viesti
Miten laskit tuon 670 tuntia? Olis kiva tietää, että sammutanko jauhamisen saman tien vain annanko oman koneeni yrittää...
Ihan peruslogiikalla:
Koodi:
9^3^8 took 1 ms
9^3^9 took 7 ms
9^3^10 took 69 ms
9^3^11 took 666 ms
9^3^12 took 4736 ms
9^3^13 took 47114 ms
9^3^14 took 415067 ms
(Ajoin nyt eri koneella).
Eli seuraava eksponentti kestää noin 8 kertaa pidempään kuin edellinen joten 9^3^18 kestäisi noin 415067ms*8^4 = 1700114432ms = noin 470 tuntia.

Lainaus:
Alkuperäinen kirjoittaja Slaya83 Näytä viesti
ja HD6900??? mikä se on? näytönohjain?? wat?
Joo, näytönohjain. Arvio pohjautui puhtaasti siihen, että se laskee vahvasti rinnakkaistuvaa kokonaislukulaskentaa noin 1000 kertaa PC:n CPU:ta nopeammin. Vai olikohan se 100 kertaa.. No anyways, ero on suuri.
  Vastaa lainaten
Vanha 30.05.12, 13:30   #10 (linkki)
 
Rekisteröitynyt: 12/2011
Viestejä: 8
Hmm.. tarvii laskea 58 kertolaskua max tuota varten. Menisköhän muutama millisekuntti siinä.

Jos Y = A + B
Niin X^Y = X^(A+B) = X^A * X^B

9^(9^9) = ?
9^9 = 387420489
9^387420489 == 9^(1+8+64+256+4096...jne kaikki kahden potenssit)
== 9^1 * 9^8 * 9^64...
9^1 = 9
9^2 = (9^1)^2
9^4 = (9^2)^2
9^8 = (9^4)^2
9^16 = (9^8)^2
9^32 = (9^16)^2
eli saadaan aina aiemmasta toiseen potenssiin. Joten 29:n kertolaskun jälkeen on laskettuna kaikki kahden kertotaulun potenssit mitä tarvitaan tuota 9^387420489 varten, jonka jälkeen tarvitsee vain kertoa ne, joiden kohdalla 387420489:n binääriesitys on yksi, keskenään, jolloin saadaan tuo 9^(9^9). Ja hommaan on käytetty yhteensä <58 kertolaskua.

Tuossa lähde Calculating Large Exponents - Algorithms / Advanced Math
  Vastaa lainaten
Vanha 30.05.12, 13:55   #11 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Lainaus:
Alkuperäinen kirjoittaja vmatikainen Näytä viesti
Hmm.. tarvii laskea 58 kertolaskua max tuota varten. Menisköhän muutama millisekuntti siinä.
Kerropas miten nopeasti lasket vaikka 100 miljoonaa numeroa pitkän luvun ja 200 miljoonaa numeroa pitkän luvun tulon (eli "yhden kertolaskun").

Kyllähän tuon saa ihan triviaalisti tehtyä 36 kertolaskulla, mutta niissä menee aikaa. Toki alle tunnin voi saada prossullakin, jos käyttää kehittyneempiä kertolaskualgoritmeja. Ei kiinnosta niin paljoa alkaa laskemaan että kokeilisin. Kunhan kommentoin tuota aloittajan bignum-kirjastoa käyttävää algoritmia ja sen nopeutta.
  Vastaa lainaten
Vanha 30.05.12, 14:17   #12 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Aloittajan käyttämää System.Numerics.BigInteger kirjastoa käyttämällä 36 kertolaskun tekemisessä kestää suuruusluokkaa yhtä kauan kuin suorassa potenssilaskussakin:
Koodi:
Round 9 took 7 ms
Round 10 took 65 ms
Round 11 took 600 ms
Round 12 took 5394 ms
Round 13 took 48562 ms
Koodi:
  Vastaa lainaten
Vanha 30.05.12, 14:19   #13 (linkki)
 
Rekisteröitynyt: 04/2011
Viestejä: 214
Tähänkin on valmis ratkaisu:
C# BigInteger Class - CodeProject
  Vastaa lainaten
Vanha 30.05.12, 14:24   #14 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Aloittajallakin oli valmis ratkaisu. Vai oliko sinulla kenties käytössäsi joku faktatieto että tuo linkittämäsi bignum-kirjasto on merkittävästi nopeampi, kuin aloittajan käyttämä?
  Vastaa lainaten
Vanha 30.05.12, 14:36   #15 (linkki)
 
Rekisteröitynyt: 08/2009
Viestejä: 7407
Lainaus:
Alkuperäinen kirjoittaja vmatikainen Näytä viesti
Hmm.. tarvii laskea 58 kertolaskua max tuota varten. Menisköhän muutama millisekuntti siinä.

9^387420489 == 9^(1+8+64+256+4096...jne kaikki kahden potenssit)
Valitan huimaa kontribuutiotani ja nollatutkimusta, mutta nuo on neljän potensseja.
__________________
We're now tickling the ninja, who just ran and hid behind a cherry blossom tree.
  Vastaa lainaten
Vanha 30.05.12, 14:51   #16 (linkki)
 
Rekisteröitynyt: 12/2011
Viestejä: 8
hsalonen, ne on myös kahden potensseja ja sattumalta tuon 387420489 ensimmäiset bitit osuu noille kohdin.

grez, aivan totta. Isojen lukujen kertolaskujen kompleksisuus on luokkaa O(n ln(n)), joka pitää vielä kertoa tuolla vastauksen pituuden binääriesityksellä, eli tuloksen laskeminen ei noiden 200 miljoonaisten lukujen kohdalla ole enää välitön, kuten virheellisesti väitin, mutta noin näppituntumalta sanoisin ettei se niin kovin raskas kuitenkaan ole. Pitänee tehdä kokeiluja miten nopeaa nuo luvut saa murskattua.
  Vastaa lainaten
Vanha 30.05.12, 15:22   #17 (linkki)
 
Rekisteröitynyt: 12/2011
Viestejä: 8
Kokeilin hyllystä vedettyä GMP libin kolmatta versiota ja se laski 9^38742048 (siis huomioi viimeisen puute) tuloksen 95.265 sekunnissa käyttäen yhtä 3.2ghz core 2 prosessoria ja näytti että se työmäärä olisi about 20-kertaistunut aina yhdellä dekadilla kasvatettaessa, joten varmaan rusikoi tuon OP:n tuloksen noin puoleen tuntiin, tässä siis käytetään tuon kirjaston oletus pow-funktiota, jonka algoritmista ei ole mitään tietoa.
  Vastaa lainaten
Vanha 30.05.12, 15:40   #18 (linkki)
jjx
 
Rekisteröitynyt: 12/2001
Viestejä: 11362
9^9^9 - Wolfram|Alpha

Ei tosin kerro tarkkaa vastausta, mutta faktaa suurusluokasta ja kymmenen viimeistä numeroa.
__________________
Laatikon levein pensseli
  Vastaa lainaten
Vanha 30.05.12, 16:06   #19 (linkki)
 
Rekisteröitynyt: 12/2011
Viestejä: 8
Elikkäs tuolla binäärisellä eksponenttialgoritmilla, jolla minimoidaan niiden kertolaskujen määrä, tuohon operaatioon meni 69.744 sekuntia ja tulos vastasi Wolfram Alphan tuloksen pituutta, joten oletan sen olevan täydellinen.

Pseudokoodina:
Koodi:
prod = 9
exp = 387420489
exp2 = 9
bitcount  = bitcountof(exp)  // == 29
for(count = 1; count <= bitcount; count++) {
  exp2 = exp2^2
  if (exp & 1<<count) {
    prod=prod*exp2
  }
}

Viimeinen muokkaaja vmatikainen; 30.05.12 16:07. Syy: tagays
  Vastaa lainaten
Vanha 30.05.12, 16:16   #20 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Käsittääkseni GMP käyttää FFT:tä isojen lukujen kertolaskuissa, joten tulos on jokseenkin odotettu.

Oliko kymmenen viimeistä lukua samat kuin Wolfram Alphan ilmoittamat? Luulisi sinänsä olevan, mutta joku tuolla Tiede-lehden palstalla laskenut oli saanut eri numerot.
  Vastaa lainaten
Vanha 30.05.12, 16:31   #21 (linkki)
 
Rekisteröitynyt: 12/2011
Viestejä: 8
Jep, GMP väittää olevansa tehokkain mitä löytyy. Tuo versio 3 löyty reposta, joten vaihtamalla vielä uudempaan tuo optimoituisi vielä ilmaiseksi.

Viimeiset desimaalit matchaa ja suoritusajassakaan ei näköjää oo varianssia, joten ~70 sekuntia yhdellä prossulla. Periaatteessa tuo optimoituisi heti ~30%, kun laskisi rinnan tuota exponenttia ja tuloa. Oliko tuo jokin kilpailu tiede.fi:ssä tms?
  Vastaa lainaten
Vanha 30.05.12, 20:56   #22 (linkki)
 
Rekisteröitynyt: 08/2009
Viestejä: 203
Mistä tuon GMP:n saa ja miten se pelaa?
  Vastaa lainaten
Vanha 30.05.12, 21:01   #23 (linkki)
 
Rekisteröitynyt: 04/2001
Viestejä: 3273
Jonkinlaista omatoimisuuttakin voi tietysti harkita, ainakin itsellä peräti toinen osuma jos kirjoittaa vaan googleen gmp

The GNU MP Bignum Library
  Vastaa lainaten
Vanha 30.05.12, 21:27   #24 (linkki)
 
Rekisteröitynyt: 08/2009
Viestejä: 203
Lainaus:
Alkuperäinen kirjoittaja Grez Näytä viesti
Jonkinlaista omatoimisuuttakin voi tietysti harkita, ainakin itsellä peräti toinen osuma jos kirjoittaa vaan googleen gmp

The GNU MP Bignum Library
No joo, sori löysinki ite ja asennettu jo visual studioon ja laskut pyörimässä jo Tuli hätäpäissään kyseltyä ennen ku etittyä ite
  Vastaa lainaten
Vanha 30.05.12, 21:37   #25 (linkki)
 
Rekisteröitynyt: 08/2009
Viestejä: 203
Hitto aika kauan jauhoi ja sit tuli "GNU cannot allocate memory".. Taitaa loppua mun masiinasta muisti kesken? On tässä RAM:ia 4GB ja tuplaydinprossu 2,8GHz
  Vastaa lainaten
Vastaa

Hae ketjusta:

Laajennettu haku

Hyppää alueelle:




Kaikki ajat ovat GMT +3. Kello on nyt 17:12.