/* 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$**

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