Numere mari- Proiect, C++

[Patrunjel]

Am vazut un topic legat de asta, da abea azi am scapat de ban, deci acuma abea pot sa postez

Baietii de dinainte vroiau sa faca tot in java, si practic sa faca o aplicatie (cu gui&stuff)

Eu m-am gandit la o librarie (nu aplicatie) in C++ care se va denumi MathShit si va cuprinde tot felu de cacaturi de-astea. Totul porneste de la ideea de lista dublu inlantuita alocata dinamic, deci singura limitatie e memoria ram a calculatorului (in ce priveste marimea numerelor).

Eu m-am gandit la o clasa care sa functioneze ca int, numai ca pe numere foarte mari (si fara operatorii prea complicat de implementat), si o clasa gen float, unde dupa virgula intra cacalau cifre.

Ce sper eu este sa facem ceva demn de sourceforge, in vacanta asta, da na...nu se stie

Daca e vreunu interesat si vrea mai multe detalii poate sa posteze linistit si sa intrebe. Nu trebuie sa fii cine stie ce scula de programator ca sa intri in echipa, daca stii ce inseamna constructor, deconstructor, stii sa scri niste operatori si sa folosesti -> esti valabil Oricum, nu-i cine stie ce greutate...mai mult tine de supradefinire, ca sa putem sa facem niste clase cat de cat decente.

Deci, daca vrea careva sa se implice, e invitat sa posteze,eventual pentru mai multe detalii, la fel.

Nustiu daca are vreo importanta, insa cam toate cacaturile care apar (ca si design, etc) in creearea librariei vor ajunge la mine pe blog(trafic-trafic-trafic )

[Andrei]

De ce nu folosesti STL? E mai simplu si te poti axa pe clasa in sine, sau vrei totul hardcode?

[Patrunjel]

Eu cred ca singurul loc in care STL e util e atunci cand scrii un program pentru a face bani.

In rest, cel putin dupa parerea mea, trebuie sa ma descurc fara.

Si, pana la urma, nu exista un termen-limita, practic n-am nicio limitare, de ce nu m-as descurca fara STL? Intr-adevar, ma cacai mai mult decat cu STL, dar invat ceva in plus, si pana la urma asta-i ideea

Edited April 15, 2011 by Patrunjel

[Paul4games]

Daca ai fi in delphi te-as ajuta cu cea mai mare placere dar la C++ sunt noob...a da si cum vrei prelucra numerele ca strngs sau cum?

[Patrunjel]

mhm, string, char, ceva de genu, nustiu, nu-i nimic batut in cuie, cum le-o fi mai usor celor care vor sa se implice (daca e careva )

Insa de dimineata ma tot gandesc cum sa fac sa scap de ghilimelele alea la initializari (sau cand vreau sa adun cu un numar de genu' )

[Nytro]

O lista dublu inlantuita presupune un pointer catre elementul anterior si unul catre elementul urmator. Asta inseamna 8 octeti pentru fiecare cifra (cred ca vrei sa memorezi cifrele in lista dublu inlantuita). In plus, ca sa ajungi la cifra 100, trebuie sa pornesti de la prima cifra, si sa treci prin celelalte 99, adica si viteza foarte mica.

Ai inceput proiectul? Vreau sa vad un inceput, apoi discutam.

[Patrunjel]

Bine, nu toate cifrele vor intra in memoria ram, vor fi si alte variabile, insa, daca e s-o luam asa, cine naiba are nevoie de o variabila de 2 giga? (cam 2 giga ram are lumea in calculator)

Daca am o adresa de inceput si una de sfarsit simplific foarte, foarte mult lucrurile Si oricum n-as avea vreun motiv sa ajung direct la numarul din mijloc, de exemplu.

M-am apucat aseara sa scriu clasa pentru lista, fiindca de facut oricum il fac, da ma gandeam ca na, poate vrea sa se mai bage careva, invatam unu de la altu', si in plus ar fi si mai interesant decat sa lucrez singur.

Edited April 15, 2011 by Patrunjel

[Nytro]

De ce liste dublu inlantuite?

[Patrunjel]

Ma gandesc sa folosesc short, fiindca se lucreaza mai lejer cu el... Singura optiune din libraria standard ar fi char, da' eu zic ca nu merita munca depusa pentru un byte.

Tipul perfect de date ar fi pe 4 biti, da' nu cred ca lucreaza procesoarele bine cu 4 biti, si nici n-am vreun tip standard pe 4 biti... (desi ar fi o chestie interesanta de facut asa ceva)

Da am zis mai sus, astea sunt ideile mele, si nu-s batute in cuie, orice sugestie e binevenita

[Nytro]

Sugestie: char * alocat dinamic pe blocuri. Ai un octet pentru cifra, e de ajuns.

Adica, aloci 1024 de octeti, adica suficient pentru un numar de 1024 de cifre. Apoi, daca e nevoie de mai mult, mai aloci 1024. Ca daca faci o alocare pentru fiecare cifra in plus se alege praful. La listele tale, aloci memorie pentru fiecare cifra, deci pauza viteza.

[fratii brothers]

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

[Nytro]

Inmultirea se face ca pe foaie. Se ia ultima cifra, se inmulteste cu ultima de la celalalt numar, si se memoreaza intr-o variabila "depasirea", de exemplu pentru 5 * 7 = 35, se pastreaza 5 si se "tine minte" 3, care se aduna la inmultirea cifrelor urmatoare.

[fratii brothers]

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

[Nytro]

De ce n ^ 2? Va fi o inmultire, a cifrelor, o atribuire a valorii de tinut minte si o adunare cu valoarea de tinut minte de la cifra precedenta. Ceea ce inseamna 3 * n operatii, si cred ca nu e rau deloc. Adica nu vor fi multi care vor folosi clasa pentru numere cu milioane de cifre.

[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!

[Nytro]

Da, ai dreptate. Pfff, nu mai stiu sa fac o inmultire

Da, oricum nu cred ca va folosi cineva aceasta clasa pentru numere extraordinar de mari, dar ar fi bun ca exercitiu de programare.