/* Adica A[i]=A[i]-(B[i]+T);
       if (A[i]<0) T=1; else T=0;
       if (T) A[i]+=10; */

  while (!A[A[0]]) A[0]--;

  while (!A[A[0]]&&A[0]>1) A[0]--;

}
==

== code(c)|
void MultHuge(Huge A, Huge B, Huge C)
/* C <- A x B */

{I int i,j,T=0;

{ int i,j,T=0;

  C[0]=A[0]+B[0]-1;
  for (i=1;i<=A[0]+B[0];) C[i++]=0;

Atunci se poate scrie relatia:

**$A$ x $B$ = ({$C$} x $10^N/2^$ + $D$) x ({$E$} x $10^N/2^$ + $F$) = $CE$ x $10^N^$ ({$CF$} + $DE$) x $10^N/2^$ + $DF$**

**$A$ x $B$ = ({$C$} x $10^N/2^$ + $D$) x ({$E$} x $10^N/2^$ + $F$) = $CE$ x $10^N^$ + ({$CF$} + $DE$) x $10^N/2^$ + $DF$**

Pentru a putea calcula produsul $A$ x $B$ avem, prin urmare, nevoie de patru produse partiale, de trei adunari si de doua inmultiri cu puteri ale lui $10$. Adunarile si inmultirile cu puteri ale lui $10$ se fac in timp liniar. Daca efectuam cele patru produse partiale prin patru inmultiri, rezulta formula recurenta de calcul **T({$N$})=4T({$N$}/{$2$})+O({$N$})** care duce prin eliminarea recurentei la <tex>T(N)\in O(N)^2</tex>. Cu alte cuvinte, inca n-am castigat nimic. Trebuie sa reusim cumva sa reducem numarul de inmultiri de la $4$ la $3$, chiar daca prin aceasta vom mari numarul de adunari necesare. Sa definim produsul **$G$ = ({$C$} + $D$) x ({$E$} + $F$) = $CE$ + $CF$ + $DE$ + $DF$ = $CE$ + $DF$ + ({$CF$} + $DE$)**
Atunci putem scrie: **$A$ x $B$ = $CE$ x $10$^{$N$}^ + ({$G$} - $CE$ - $DF$) x $10$^{$N$}/{$2$}^ + $DF$**

O prima varianta ar fi cautarea binara a radacinii, prin injumatatirea intervalului. Initial se porneste cu intervalul ({$1$},{$A$}), deoarece radacina cubica se afla undeva intre $1$ si $A$ (evident, incadrarea este mai mult decat acoperitoare; ea ar putea fi mai limitativa, dar nu ar reduce timpul de lucru decat cu cateva iteratii). La fiecare pas, intervalul va fi injumatatit. Cum, probabil ca stiti deja; se ia jumatatea intervalului, se ridica la puterea a treia si se compara cu $A$. Daca este mai mare, inseamna ca radacina trebuie cautata in jumatatea inferioara a intervalului. Daca este mai mica, vom continua cautarea in jumatatea superioara a intervalului. Daca cele doua numere sunt egale, inseamna ca am gasit tocmai ce ne interesa. Prima varianta a pseudocodului este:

[ce fac cu secventa de cod in pseudocod???]

== code(c)|
citeste A cu N cifre
  Lo <- 1, Hi <- A, X <- 0
  cat timp X=0
    Mid <- (Lo+Hi)/2
    daca Mid^3<A
      atunci Lo <- Mid+1
      altfel daca Mid^3>A
               atunci Hi <- Mid-1
               altfel X <- Mid
==
 

In cazul cel mai rau, algoritmul de mai sus efectueaza $log ~2~ A$ injumatatiri de interval, fiecare din ele presupunand o adunare, o impartire la $2$ si o ridicare la cub. Dintre aceste operatii, cea mai costisitoare este ridicarea la cub, O( $N$^{$2$}^ ). Complexitatea totala este prin urmare O( $N$^{$2$}^ $log ~2~ A$ ). Deoarece $A$ are ordinul de marime $10$^{$N$}^, rezulta complexitatea O( $N$^{$3$}^ $log 10$ )= O( $N$^{$3$}^ ), adica mai proasta decat cea ceruta (de altfel, un algoritm cu aceasta complexitate nici nu s-ar incadra in timp pentru $N$={$1000$}). Daca timpul ne permite, trebuie sa cautam alta metoda.

Procedeul general este urmatorul: dandu-se un numar $A$ cu $N$ cifre, il completam cu zerouri nesemnificative pana cand $N$ se divide cu $3$ (poate fi necesar sa adaugam maxim doua zerouri). Numarul de cifre semnificative ale radacinii cubice este $M$={$N$}/{$3$}. Aflam pe rand fiecare cifra, incepand cu cea mai semnificativa. Sa presupunem ca am aflat cifrele $X$ ~$M$~, $X$ ~$M-1$~,..., $X$ ~$K+1$~. Cifra $X$~$K$~ este cea mai mare cifra pentru care numarul <tex> \overline{(X_MX_{M-1}...X_{K+1}X_K00...00)}^3\leq A</tex>. Cifra $X$~$K$~ este unica, deoarece exista, in general, mai multe cifre care verifica proprietatea ceruta, dar una singura este "cea mai mare". O a doua versiune a pseudocodului este deci:

[cod in pseudocod]

== code(c)|
citeste A cu N cifre
  X <- 0; T <- 0
  cat timp N%3<>0 adauga un 0 nesemnificativ
  repeta de N/3 ori
    adauga la T urmatoarele 3 cifre din A
    adauga la X cea mai mare cifra astfel incat X^3<= T
==
 

Sa evaluam complexitatea acestei versiuni. Linia $1$ se executa in timp liniar, O({$N$}). Liniile $2$ si $3$ se executa in timp constant. Linia $5$ se executa in O({$N$}), iar linia $6$ presupune adaugarea unei cifre (O({$N$})) si o ridicare la cub, adica doua inmultiri (O({$N$}^{$2$}^)). Deoarece liniile $5$ si $6$ se executa de $N$/{$3$} ori (linia $4$), rezulta o complexitate de O({$N$}^{$3$}^). Iata ca nici acest algoritm nu a adus imbunatatiri si pare si ceva mai greu de implementat. El poate fi totusi modificat pentru a-i scadea complexitatea la O({$N$}^{$2$}^).

Presupunand ca avem calculate toate puterile de la $1$ la $p$ ale lui $OldX$, se poate calcula noua valoare a lui $X$^{$p$}^ folosind numai adunari si inmultiri cu scalari. In felul acesta se pot calcula in timp liniar valorile lui $X$, $X$^{$2$}^, $X$^{$3$}^, ...., $X$^{$K$}^.

h2. Problema
 
|_. Timp de implementare|_. Timp de rulare|_. Complexitate|
|1h 30'|10 secunde|**O(N^2^)**|
 
Se da un numar natural cu $N$≤{$1000$} cifre. Se cere sa se extraga radacina cubica a numarului. Se garanteaza ca numarul citit este cub perfect.
Fisierul $INPUT.TXT$ contine un singur rand, terminat cu $EOF$, pe care se afla numarul, cifrele fiind nedespartite.
In fisierul $OUTPUT.TXT$ se va tipari radacina cubica a numarului, pe o singura linie terminata cu $EOF$.
 
|_. INPUT.TXT|_. OUTPUT.TXT|
|2097152|128|
 
h2. Rezolvare
Problema este cat se poate de simpla din punct de vedere matematic; dificultatea apare la implementare, atat datorita structurilor de date necesare, cat mai ales datorita complexitatii cerute. Despre lucrul cu numere intregi (chiar si $Longint$) nici nu poate fi vorba, iar la lucrul cu numere reale apar erori de calcul.
Structura de date propusa pentru abordarea acestui gen de probleme este urmatoarea: numerele vor fi reprezentate printr-un vector de cifre zecimale. Prima pozitie (pozitia $0$) din vector este rezervata pentru a memora numarul de cifre. Definitia C a tipului de date este:
== code(c)|
typedef int Huge[1001];
==
 
Iata cum s-ar memora numarul "1997" intr-un asemenea vector:
 
!lucrul-cu-nr-mari?pb1.jpg!
 
Se observa ca vectorul este oarecum "intors pe dos". Totusi, aceasta forma este cea mai convenabila, pentru ca ea permite implementarea cu o mai mare usurinta a operatiilor aritmetice.
 
Mai trebuie remarcat ca pe fiecare pozitie $K$ in vector se afla cifra care il reprezinta pe $10$^{$K-1$}^ in numarul reprezentat: in V[1] se afla cifra unitatilor ({$10$}^{$0$}^), in V[2] se afla cifra zecilor ({$10$}^{$1$}^), in V[3] se afla cifra sutelor ({$10$}^{$2$}^) s.a.m.d. Formatul zecimal nu este cea mai fericita (a se citi "eficienta") alegere. El ocupa doar patru biti din cei opt ai unui octet, deci face risipa de memorie. Daca am alege baza de numeratie $256$, am folosi la maximum memoria, si in plus operatiile ar fi cu mult mai rapide (deoarece $256$ este o putere a lui $2$, inmultirile si impartirile la $256$ sunt simple deplasari la stanga si la dreapta ale reprezentarilor binare). Sa facem urmatorul calcul ca sa vedem cate cifre are in baza $256$ un numar care are $1000$ de cifre in baza $10$:
 
<tex>10^{1000} = 10 \cdot (10^3)^{333} \approx 10 \cdot (2^10)^{333} \approx 10 \cdot (2^8)^{335} = 10 \cdot 256^{335}  </tex>
 
Asadar, numarul de cifre s-a redus cam de trei ori. Un algoritm liniar ar functiona de trei ori mai repede pe reprezentari in baza $256$, iar unul patratic ar functiona de noua ori mai repede. Inconvenientul major este dificultatea depanarii unui program care opereaza intr-o baza aritmetica atat de straina noua. Vom ramane deci la baza $10$, cu mentiunea ca acei mai temerari dintre voi pot incerca folosirea bazei $256$.
 

public

protected