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();
}
}
}
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
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.
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.
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.
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:
Koodi:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Diagnostics;
namespace _999
{
class Program
{
static void Main(string[] args)
{
var n = new BigInteger(9);
var s = new Stopwatch();
s.Start();
for (int i = 0; i < 18; i++)
{
n = (n * n) * n;
Console.WriteLine("Round {0} took {1} ms", i + 1, s.ElapsedMilliseconds);
s.Restart();
}
}
}
}
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ä?
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.
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.
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.
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.
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?
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
Tuli hätäpäissään kyseltyä ennen ku etittyä ite 
