Aktív témák

• #21 Gyuri16 senior tag weiss #20

  2012-07-02 20:31:03 #21

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Gyuri16

  senior tag

  válasz weiss #20 üzenetére

  rekurzivan kell csinalni mint irtam, tehat a kapott szamokat ismet felosztod. van egy olyan erzesem, hogy szorzasnal gyorsabban nem lehet ezt megcsinalni, szoval ez jo irany lehet.

• #19 Gyuri16 senior tag weiss #15

  2012-07-02 19:24:37 #19

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Gyuri16

  senior tag

  válasz weiss #15 üzenetére

  ilyenen gondolkoztam par honapja, nem irtam kodot, de errefele indulnak:
  van egy nagy szam, probaljuk meg kisebbre redukalni
  x = a + b * k^n
  ahol |a| = |b| (nagyjabol). k a szamrendszer alapja. tehat a szamot felosztom ket reszre, ugy hogy eloszor az elso felet veszem majd a masodikat eltolva megfelelo hellyel balra (szovegkent veve a szamot ketteosztjuk a feleben)

  ezt meg lehet ismetelni rekurzivan (divide and conquer). ha mar eleg kicsit, akkor elvegzed a 3 szamon a trivialis szamrendszervaltos algoritmust (itt talan megeri valamilyen nagyobb szamrendszerben dolgozni - kihasznalni a 32 bites valtozokat -, avagy tobb szamjegyet egyszerre feldolgozni. erre lehetne tablazatokat elore szamolni, hogy gyors legyen), es aztan osszeszorozgatod visszafele. osszeadni egyszeru, szorzasra pedig vannak jofajta algoritmusok. egyszeru pl a karatsuba vagy aztan a bonyolultabb fast fourier transformot hasznalok.
  elobbi n^log2(3) ~= n^1.585 idoben fut, utobbival lehet majdnem n logn-t elerni.

• #18 Jester01 veterán weiss #17

  2012-07-02 17:17:44 #18

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Jester01

  veterán

  válasz weiss #17 üzenetére

  A GMP egymillió jegyes számot 13-asból 17-esbe kb. 0.4 másodperc alatt konvertált, 2.3GHz-es gépen. De gyanítom, hogy előbb kettesbe vagy tízesbe alakította és onnan vissza, tehát akár kétszer ilyen gyors is lehetne a közvetlen átalakítás.

  Nem tudom neked mi számít lassúnak (az persze tény, hogy algoritmikusan lassú).

• #16 Jester01 veterán weiss #15

  2012-07-02 16:40:48 #16

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Jester01

  veterán

  válasz weiss #15 üzenetére

  A naív algoritmus nagyon lassú? Maradékos osztás, ahogy általános iskolában tanították

Aktív témák