S-a luat deci fiecare cifra a inmultitorului si s-a efectuat produsul partial corespunzator, corectand la fiecare pas rezultatul prin calculul transportului. Rezultatul pentru fiecare produs partial s-a scris din ce in ce mai in stanga, pentru a se alinia corect ordinele de marime. Acest procedeu este oarecum incomod de implementat. Se pot face insa unele observatii care usureaza mult scrierea codului:
* Prin inmultirea cifrei cu ordinul de marime $10i$ din primul numar cu cifra cu ordinul de marime $10j$ din al doilea numar se obtine o cifra corespunzatoare ordinului de marime $10i$+$j$ in rezultat (sau se obtine un numar cu mai mult de o singura cifra, caz in care transportul merge la cifra corespunzatoare ordinului de marime $10i$ + $j$ + $1$).
* Prin inmultirea cifrei cu ordinul de marime $10i$ din primul numar cu cifra cu ordinul de marime $10j$ din al doilea numar se obtine o cifra corespunzatoare ordinului de marime $10i$+{$j$} in rezultat (sau se obtine un numar cu mai mult de o singura cifra, caz in care transportul merge la cifra corespunzatoare ordinului de marime $10i$ + $j$ + $1$).
* Daca numerele au $M$ si respectiv $N$ cifre, atunci produsul lor va avea fie $M$ + $N$ fie $M$ + $N$ - $1$ cifre. Intr-adevar, daca numarul $A$ are $M$ cifre, atunci $10^M-1^$ ≤ $A$ < $10^M^$ si {$10^N-1^$} ≤ $B$ < $10^N^$, de unde rezulta $10^M+N-2^$ ≤ $A$ x $B$ < $10^M+N^$.
* La calculul produselor partiale se poate omite calculul transportului, acesta urmand a se face la sfarsit. Cu alte cuvinte, intr-o prima faza putem pur si simplu sa inmultim cifra cu cifra si sa adunam toate produsele de aceeasi putere, obtinand un numar cu "cifre" mai mari ca $9$, pe care il aducem la forma normala printr-o singura parcurgere. Sa reluam acelasi exemplu:
h2. Impartirea unui vector la un scalar
Ne propunem sa scriem o functie care sa imparta numarul $A$ de tip Huge la scalarul $B$, sa retina valoarea catului tot in numarul $A$ si sa intoarca restul (care este o variabila scalara). Sa pornim de la un exemplu particular si sa generalizam apoi procedeul: sa calculam catul si restul impartirii lui $1997$ la $7$. Cu alte cuvinte, sa gasim acele numere $C$ de tip Huge si <tex>R\in{0, 1, 2, 3, 4, 5, 6}</tex> cu proprietatea ca $1997$ = $7$ x $C$ + $R$.
Ne propunem sa scriem o functie care sa imparta numarul $A$ de tip Huge la scalarul $B$, sa retina valoarea catului tot in numarul $A$ si sa intoarca restul (care este o variabila scalara). Sa pornim de la un exemplu particular si sa generalizam apoi procedeul: sa calculam catul si restul impartirii lui $1997$ la $7$. Cu alte cuvinte, sa gasim acele numere $C$ de tip Huge si <tex>R\in\{0, 1, 2, 3, 4, 5, 6\}</tex> cu proprietatea ca $1997$ = $7$ x $C$ + $R$.
!lucrul-cu-nr-mari?impart1.jpg!
La fiecare pas se coboara cate o cifra de la deimpartit alaturi de numarul deja existent (care initial este $0$), apoi rezultatul se imparte la impartitor ($7$ in cazul nostru). Catul este intotdeauna o cifra si se va depune la sfarsitul catului impartirii, iar restul va fi folosit pentru urmatoarea impartire. Restul care ramane dupa ultima impartire este tocmai $R$ pe care il cautam. Procedeul functioneaza si atunci cand deimpartitul are mai multe cifre. La sfarsit trebuie sa decrementam corespunzator numarul de cifre al catului, prin neglijarea zerourilor create la inceputul numarului. Numarul maxim de cifre al catului este egal cu cel al deimpartitului.
La fiecare pas se coboara cate o cifra de la deimpartit alaturi de numarul deja existent (care initial este $0$), apoi rezultatul se imparte la impartitor ({$7$} in cazul nostru). Catul este intotdeauna o cifra si se va depune la sfarsitul catului impartirii, iar restul va fi folosit pentru urmatoarea impartire. Restul care ramane dupa ultima impartire este tocmai $R$ pe care il cautam. Procedeul functioneaza si atunci cand deimpartitul are mai multe cifre. La sfarsit trebuie sa decrementam corespunzator numarul de cifre al catului, prin neglijarea zerourilor create la inceputul numarului. Numarul maxim de cifre al catului este egal cu cel al deimpartitului.
== code(c)|
unsigned long Divide(Huge A, unsigned long X)
}
==
h2. Impartirea a doi vectori
Daca se dau doi vectori $A$ si $B$ si se cere sa se afle catul $C$ si restul $R$, etapele de parcurs sunt aceleasi ca la punctul precedent, numai ca operatorii "/" si "%" trebuie implementati de utilizator, ei nefiind definiti pentru vectori. Cu alte cuvinte, dupa ce "coboram" la fiecare pas urmatoarea cifra de la deimpartit, trebuie sa aflam cea mai mare cifra $X$ astfel incat impartitorul sa se cuprinda de $X$ ori in restul de la momentul respectiv. Acest lucru se face cel mai comod prin adunari repetate: pornim cu cifra $X$={$0$} si o incrementam, micsorand concomitent restul, pana cand restul care ramane este prea mic. Sa efectuam aceeasi impartire, $1997$:{$7$}, considerand ca ambele numere sunt reprezentate pe tipul Huge.
!lucrul-cu-nr-mari?impart2.jpg!
Cazul cel mai defavorabil (cand $X$={$9$}) presupune $9$ scaderi si $10$ comparatii, cazul cel mai favorabil (cand $X$={$0$}) presupune numai o comparatie, deci cazul mediu presupune $4$ scaderi si $5$ comparatii. Cautarea lui $X$ se poate face si binar, prin injumatatirea intervalului, ceea ce reduce timpul mediu de cautare la aproximativ $3$ comparatii si $3$ inmultiri, dar codul se complica nejustificat de mult (de cele mai multe ori).
== code(c)|
void DivideHuge(Huge A, Huge B, Huge C, Huge R)
/* A/B = C rest R */
{ int i;
R[0]=0;C[0]=A[0];
for (i=A[0];i;i--)
{ Shl(R,1);R[1]=A[i];
C[i]=0;
while (Sgn(B,R)!=1)
{ C[i]++;
Subtract(R,B);
}
}
while (!C[C[0]] && C[0]>1) C[0]--;
}
==
h2. Extragerea radacinii cubice
Vom sari peste prezentarea algoritmului de extragere a radacinii patrate, pe care il vom lasa ca tema cititorului, si ne vom indrepta atentia asupra celui de extragere a radacinii cubice, care este putin mai complicat, dar care poate fi usor extins pentru radacini de orice ordin. Problema este exact cea din enunt, asa ca vom porni de la exemplul dat. Sa notam <tex>A = 2.097.152</tex> si <tex> X = \sqrt[3]{A}</tex>. Cum se afla **$X$** ?
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:
== 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.
In exemplul ales, sa observam ca $106$≤{$A$}<{$109$}, de unde deducem ca $102$≤{$X$}<{$103$}. Cu alte cuvinte, $X$ are $3$ cifre. In cazul general, daca $A$ are $N$ cifre, atunci $X$ are [$N$/{$3$}] cifre (prin [$N$/{$3$}] se intelege "cel mai mic intreg mai mare sau egal cu $N$/{$3$}"). Care ar putea fi prima cifra a lui $X$? Daca $X$ incepe cu cifra $2$, atunci $200$≤{$X$}<{$300$} => $8.000.000$≤{$2.097.152$}<{$27.000.000$}, ceea ce este fals. Cu atat mai putin poate prima cifra a lui $X$ sa fie mai mare ca $2$. Rezulta ca prima cifra a lui $X$ este $1$. De altfel, pentru a afla acest lucru, putem sa si neglijam ultimele $6$ cifre ale lui $A$. Ne intereseaza doar prima cifra, cea a milioanelor, iar prima cifra a lui $X$ o alegem in asa fel incat cubul ei sa fie mai mic sau egal cu $2$.
Ce putem spune despre a doua cifra? Daca ar fi $3$, atunci $130$≤{$X$}<{$140$} => $2.197.000$≤{$2.097.152$}<{$2.744.000$}, fals (deci cifra este cel mult $2$). Daca ar fi $1$, atunci $110$≤{$X$}<{$120$} => $1.331.000$≤{$2.097.152$}<{$1.728.000$}, fals. Rezulta ca a doua cifra este obligatoriu $2$. Analog, putem neglija ultimele trei cifre ale lui $A$, iar a doua cifra a lui $X$ este cel mai mare $C$ pentru care <tex> \overline{1C}^3 \leq 2097</tex>. Pentru a afla ultima cifra, aplicam acelasi rationament: Daca ar fi $9$, atunci $X$={$129$} si ar rezulta $2146688$={$X$}^{$3$}^={$2097152$}, absurd. Daca consideram ca cifra este $8$, atunci calculul se verifica. Am aflat asadar ca $X$={$128$}.
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:
== 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$}^).
Principalul neajuns al sau este efectuarea ridicarii la cub, care se face in O({$N$}^{$2$}^). Daca am putea sa-l aflam la fiecare pas pe $X$^{$3$}^ fara a efectua inmultiri, adica in timp liniar, atunci intregul algoritm ar avea complexitate patratica. Bineinteles, prima intrebare care vine pe buzele cititorului este "cum sa ridicam la cub fara sa facem inmultiri?". Sa nu uitam insa ceva: ca noi nu-l cunoastem numai pe $X$. Il cunoastem si pe $X$ de la pasul anterior, care avea o cifra mai putin (il vom boteza $OldX$). Sa presupunem ca, printr-o metoda oarecare, am reusit sa-l ridicam pe $OldX$ la puterile a doua si a treia (si am obtinut numerele $OldX2$ si $OldX3$). Cum putem, cunoscand aceste trei numere, precum si noua cifra ce se va adauga la sfarsitul lui $X$ (sa-i spunem $C$ ), sa-l aflam pe $X$, patratul si cubul sau? Nu e prea greu:
<tex> X = 10 \cdot OldX + C </tex>
<tex> X^2 = (10 \cdot OldX + C)^2 = 100 \cdot OldX^2 + 20 \cdot OldX \cdot C + C^2 = 100 \cdot OldX2 + (20 \cdot C) \cdot OldX + C^2</tex>
Iata asadar ca pentru a afla noile valori ale puterilor $1$, $2$ si $3$ ale lui $X$, folosindu-le pe cele vechi, nu avem nevoie decat de adunari si de inmultiri cu numere mici (de ordinul miilor). Toate aceste operatii se fac in timp liniar, deci am reusit sa gasim un algoritm patratic. Iata mai jos sursa C:
== code(c)|
void FindDigit(Huge L,Huge NewL2,Huge NewL3,
Huge OldL,Huge OldL2,Huge OldL3,Huge Target)
{ Huge Aux;
L[1]=10;
do
{ L[1]--;
/* Trebuie calculat LA3. Se stiu OldL (L/10)
si noua cifra L[1]. Deci (OldL*10+L[1])A3=?
Se aplica binomul lui Newton. */
AtribHuge(NewL3,OldL3);Shl(NewL3,3);
AtribHuge(Aux,OldL2);Mult(Aux,300*L[1]);
Add(NewL3,Aux);
AtribHuge(Aux,OldL);Mult(Aux,30*L[1]*L[1]);
Add(NewL3,Aux);
AtribValue(Aux,L[1]*L[1]*L[1]);
Add(NewL3,Aux);
}
while (Sgn(NewL3,Target)==1);
/* Aceeasi operatie pentru LA2 */
AtribHuge(NewL2,OldL2);Shl(NewL2,2);
AtribHuge(Aux,OldL);Mult(Aux,20*L[1]);
Add(NewL2,Aux);
AtribValue(Aux,L[1]*L[1]);
Add(NewL2,Aux);
/* Noile valori devin 'vechi' */
AtribHuge(OldL2,NewL2);
AtribHuge(OldL,L);
AtribHuge(OldL3,NewL3);
}
void CubeRoot(Huge A, Huge X)
{ Huge Target,OldX,OldX2,OldX3,NewX2,NewX3;
int i;
/* Se initializeaza vectorii cu 0 (nici o cifra) */
OldX[0]=OldX2[0]=OldX3[0]=X[0]=0;
for (i=1;i<=(A[0]+2)/3;i++)
{ AtribHuge(Target,A);
Shr(Target,3*((A[0]+2)/3-i));
Shl(X,1);
FindDigit(X,NewX2,NewX3,OldX,OldX2,OldX3,Target);
}
}
==
Acum nu mai avem decat sa scriem rutinele de intrare/iesire si programul principal:
== code(c)|
#include <stdio.h>
#include <mem.h>
#define NMax 1000
typedef int Huge[NMax+3];
Huge A,X; /* A[0] si X[0] indica numarul de cifre */
void ReadData(void)
{ FILE *F=fopen("input.txt","rt");
int C,i;
A[0]=0;
do A[++A[0]]=(C=fgetc(F))-'0';
while (C!=EOF);
A[0]--;
fclose(F);
/* Intoarce vectorul pe dos */
for (i=1;i<=A[0]/2;i++)
A[i]=(A[i]AA[A[0]+1-i])A(A[A[0]+1-i]=A[i]);
}
void WriteSolution(void)
{ FILE *F=fopen("output.txt","wt");
int i=X[0];
while (!X[i]) i--;
while (i) fputc(X[i--]+'0',F);
fclose(F);
}
void main(void)
{
ReadData();
CubeRoot(A,X);
WriteSolution();
}
==
Pentru a extinde aceasta metoda la radacini de orice ordin $K$, trebuie numai sa tinem cont de expresia binomului lui Newton:
<tex> X^p = (10 \cdot OldX + C)^p = \sum_{\substack {0\leq i \leq p}} {10^i \cdot Oldx^i \cdot C^{p-i}} </tex>
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$.
