Aktív témák

• #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.

Aktív témák