[Pokud Vas zajima pouze format vstupu - Go To: Vstup&Vystup]

Uloha:
Nasobeni velkych (prirozenych) cisel - 'skolskou' metodou a Karacubovou metodou


Reprezentace dat:
Dynamicke pole - struktura, kde je ulozena velikost pole (integer)
a ukazatel na samotne pole (prvky typu signed char).
Pozor, velikost cisla je pocet cifer, ale pole v jazyce C se indexuje od nuly
(tzn. posledni cifra, nejvyssi rad, ma index (velikost pole - 1) ).


Reseni:
Skolske nasobeni znamena prenasobeni kazde cifry jednoho cisla kazdou cifrou
druheho cisla a secteni jednotlivych vysledku (tzv. 'pod sebe').
Karacubova metoda je zalozena na nasledujicim pozorovani:
Necht a, b jsou dve prirozena cisla delky n = m = 2^k (nejake prirozene k;
tohoto lze dosahnout pridanim potrebneho poctu nul na zacatek). Pak lze psat
a = r * B^(n/2) + s, b = t * B^(n/2) + u
a * b = r*t * B^n + (r*t + (r-s)*(u-t) + s*u) * B^(n/2) + s*u
vyhoda teto metody je v tom, ze staci spocitat misto soucinu a * b
tri souciny polovicni delky (r*t, (r-s)*(u-t), s*u), pricemz tyto souciny opet
pocitame Karacubovou metodou.


Princip programu:
Ze vstupu se nacita cislo po cifrach, ktere se ulozi do dynamickeho pole.
Toto se nasledne otoci, aby nejmensi rad mel nejmensi index pole.
Standardni nasobeni se provede dvojitym for cyklem (pruchod vsech cifer jednoho
i druheho cisla), pricemz se scitani provadi za chodu - soucin prave vynasobenych
cifer se pricte k tomu, co uz je ve vyslednem poli. Je treba osetrit, abych pracoval 
s ciframi (moduleni 10).

Karacubova metoda se provede podle jednoduche osnovy:
1.a, b jednociferna => Return a*b
2.x = KaracubaNasobeni( r , t )
  y = KaracubaNasobeni(r-s,u-t)
  z = KaracubaNasobeni( s , u )
3.Return x * B^n + (x + y + z) * B^(n/2) + z

Jen je treba naprogramovat scitani a odcitani dlouhych cisel. Nasobeni bazi je jen 
pridani nul (prvku dyn. pole).


!!!Vstup & Vystup!!!:
Ve stejnem adresari, kde se nachazi zpustitelny soubor Karatsuba.exe
je treba mit soubor Input.txt (pocatecni i musi byt velke) s nasledujici
strukturou:
Na prvnim radku je pouze cislo, kolik PARU cisel bude. Dale vzdy na zvlastnim radku
jedno cislo (v desitkove soustave).
Doporucuji vyuzit prilozeneho (autorskeho) souboru Input.txt.
Program sam zalozi vystupni soubor Output.txt, kde budou vzdy uvedeny cinitele a
vysledny soucin pro kazdou z metod. A take cas v sekundach, jenz byl potreba k vypoctu
v pripade jednotlivych metod.


Opravdu to je rychlejsi?!
Ne. Presneji receno - ne v pripade 'normalne velkych' cisel. Jak uz bylo zmineno vyse
nejlepsi je pouzit autorsky Input soubor, ale ne ze by jen pro tech par cisel to fungovalo,
protoze vsak je tam jeden nebo dva pary cisel, jejichz soucin lze otestovat na Kalkulacce
ve Windows. A dalsi cisla jsou vytvorena tak, ze jejich delka se zdvojnasobuje:
a protoze teoreticky je slozitost standardniho nasobeni n^2, Karacubova n^1,58 (presneji ln3/ln2),
mel by se take cas potrebny pro vypocet dvojnasobne delsiho cisla v prvnim pripade prodlouzit
ctyrnasobne a v druhem pripade trojnasobne (2^1.58 = 3).

Jak to fungovalo pri beta-testingu:
zkouseno na trech ruznych strojich (ruzna Pentia IV, RAM 1024-2048) - na dvou bylo
Karacubovo nasobeni rychlejsi az v pripade OPRAVDU velkych cisel (posledni par v autorskem 
Input.txt), ale celkem presne fungovala asymptotika (2x vetsi vstup - 4x, resp. 3x delsi cas);
na tretim stroji Karacubovo nasobeni bylo rychlejsi uz pri 'mensich' cislech (posledni tri pary
v Input.txt)


Omezeni:
Vzhledem k neprilis velkym programatorskym zkusenostem je mozne, ze nejakou cast kodu (zvlast
v pripade Karacubova nasobeni) lze zefektvnit, kvuli cemuz se muze uzitecnost Karacubova nasobeni 
projevit az u vetsich cisel nez by melo byt z teoretickeho hlediska. 
Dale velikost pole, tj. pocet cifer, je max. hodnota typu integer (nejakych 4*10^9). 
Nakonec Karacubovo nasobeni je volano rekurzivne, a to ma taky svou hranici (omezeno nejak velikosti STACKu).