fratii brothers

Cred ca ai uitat putin inmultirea. Sa incercam un exemplu: 1234 x 4567 ------------------- 8638 (4*7, 3*7, 2*7, 1*7, 4 INMULTIRI + 3 adunari (depasirile) 7404 (alte 4 inmultiri, adunarile nu le mai pun la socoteala) 6170 (inca patru inmultiri) 4936 (ultimele 4 inmultiri) ------------------- 5635678 (4 x 4 inmultiri) Generalizind, la inmultirea a 2 numere de N si respectiv M cifre, cu acest algoritm vei avea de facut NxM operatii de inmultire si un numar variabil de adunari ale "tinutului in minte" care se poate calcula cu o formula complicata, cazul cel mai rau fiind de (N-1)xM adunari. Avem astfel total = NxM + (N-1)xM = (2N - 1)xM operatii matematice (in cel mai defavorabil caz) Daca numerele au numar egal de cifre (din nou, in cel mai nefavorabil caz) totalul devine (2N - 1)xN = 2N^2 - N operatii. Ignora 2 si -N, retine doar N^2. Numarul de operatii de efectuat creste EXPONENTIAL (cu exponent 2, ridicare la patrat) cu marimea setului de intrare. Altfel spus avem de-a face cu un algoritm din clasa de complexitate temporala O(n^2). (spun temporala pentru ca mai exista si o clasificare dupa complexitatea spatiala, altfel spus, cita memorie necesita algoritmul respectiv; aici inmultirea scolareasca sta destul de bine, fiind O(log n)) Desigur, nu totdeauna vei avea de-a face cu cel mai nefavorabil caz; de exemplu daca inmultesti un numar de 100 de cifre cu o singura cifra, va merge destul de repede. Daca insa vei face un numar astronomic de inmultiri intre numere aleatoare si vei face media, vei vedea (statistic) ca timpul necesar pentru inmultirea a doua numere creste exponential (exponentul va fi undeva intre 1.8 si 1.9 functie de algoritmul care-ti livreaza numerele aleatoare). Deci nu chiar 2, dar pe aproape si tot functie exponentiala va fi. Ajungind aici, vei fi poate surprins sa afli ca exista procedee de a inmulti doua numere care necesita considerabil mai putin timp si mai important, timpul necesar creste LOGARITMIC, nu EXPONENTIAL cu marimea setului de intrare. Mai concret, presupunind ca N = 100, in primul caz ai avea de efectuat in medie 10000 de pasi iar in al doilea aproximativ 60 (algoritmul Schonhage-Strassen cu complexitate O(N*logN*loglogN). Acum, ca exercitiu de programare, o librarie care opereaza pe numere de precizie arbitrara e ceva util. Ca produs final, "de pus pe sourceforge" insa, ma vad nevoit sa te dezamagesc patrunjel: exista zeci daca nu sute si TOATE utilizeaza concepte pe care mi-e teama ca nu le posezi. N-o lua personal; e doar o opinie pe care as fi bucuros sa mi-o infirmi. State of the art in domeniu este GMP: GNU Multi-precision Library. Au o pagina despre algoritmii folositi: Algorithms - GNU MP 5.0.1 Daca te pasioneaza domeniul, e un bun punct de plecare pentru documentare. Un curs de algebra superioara ar fi util pentru intelegerea unor concepte. Succes!

Esti constient ca inmultirea "ca pe foaie" a doua numere cu N cifre presupune N la puterea a doua operatii?

patrunjel, cum te-ai gindit sa inmultesti doua numere mari d-astea?