BigOperation - operatii numere mari

Adunarea in implementarea aceea este de 12 ori mai rapida ca implementarea mea,
la inmultire diferentele nu sunt asa da mari, banuiesc ca din cauza faptului ca utilizeaza karatsubaMultiply.
Metoda karatsuba este eficienta doar pentru numere colosale daca imi aduc bine aminte.

Cu ce-ti propui sa continui?

IvanMihai, on 05 aprilie 2020 - 11:12, said:

Pe sistemul meu, dupa masuratori precise, e doar de 2.1x mai rapida decat naive_add al tau.

Printre cauze:

• Te plimbi prin tot vectorul in GetSign/SetSign
  
• Ajungi sa efectuezi impartiri pentru naive_add (in cadrul finalize)

Inca o observatie: cand faci adunare x + y cu returnarea unui z ma astept sa nu modifici x si y, sa ramana constante.

Edited by dani.user, 05 April 2020 - 12:05.

dani.user, on 05 aprilie 2020 - 11:45, said:

Masuratorile mele au inclus initial si convertirea in big integer din string: string_to_vector("3...") respectiv bigint("3...")
aici sunt diferente mari.
Ca valori bigints am utilizat ce ai postat tu intr-un post anterior.
Daca ignori convetirea string_to_vector, de fapt nu este mai rapida ca implementarea mea.

"dupa masuratori precise" - ce intelegi prin masuratori precise???
Ce-i drept eu am utilizat doar:

clock_t time_req;
time_req = clock();
// first_store_add(one, two);
time_req = clock() - time_req;
printf("Orig   took %f seconds\r\n",(float)time_req/CLOCKS_PER_SEC);

Quote

Ma plimb la inceputul vectorului pana gasesc o valoare diferita de zero: aceasta valoare diferita de zero pastreaza semnul.
De ce contine zerouri la inceput: din moment ce dimesiunea vectorului rezultat este aproximata.
GetSign/SetSign este utilizat doar de cateva ori deci nu ar trebui sa fie diferente mari.

Quote

Da, adunarea are acelasi "finalize" ca inmutirea la acest punct.

Quote

Daca te referi la declararea x si y ca const nu o sa fac asta din moment ce este nevoie de valoarea absoluta a lui x si y abs(x)/abs(y) acestea fiind mai usor de calculat direct in x si y prin inlaturarea semnului decat crearea a unui nou vector care pastreaza abs.
La sfarsit seteaza semnul inapoi.

Daca ar fi sa ignor partea cu convertirea din string a biginteger, implementarea pare ok.

Da, am masurat doar adunarea. Urmeaza sa masor si conversia.

Masuratori precise:

• Am folosit std::chrono::high_resolution_clock
  
• Am rulat adunarea de 1000x intr-o bucla pentru a aduce timpu buclei macar in zona milisecundelor
  
• Am rulat de 1000x bucla si am facut o medie

GetSign ia cam 8-9% din timp, nu e chiar neglijabil. S-ar face si mai repede si mai simplu daca ai stoca separat semnul.

Cel mai mult te costa impartirea, o operatie foarte costisitoare. Iar, pentru adunare cel putin, poti scapa foarte usor de ea.

Conversia e cam de 1.4x mai rapida in cazul bigint decat string_to_vector:

• bigint proceseaza grupe de base_digits pentru a nu da peste
  
• tu tii evidenta dupa fiecare caracter daca n-ai dat peste

Edited by dani.user, 05 April 2020 - 14:59.

Am rezolvat problema cu viteza convertirii din string in big integer, mai ramane problema cu viteza adunarii (din moment ce am utilizat aceasi metoda ca la inmutire), si problema cu impartirea (ceva nu este bine cu implementarea mea a impartirii).

@dani.user:
Din moment ce metoda pe care ai utilizat-o pentru masurare este diferita si nu o pot reproduce, vreau sa te rog sa compari scaderea (-) intre implementarea mea si implemetarea gasita pe NET.

De cam 1.7x mai rapida varianta de pe net. GetSign + SetSign peste 1/3 din timp.

Edited by dani.user, 05 April 2020 - 21:22.

@dani.user: Multumesc mult.
Am reusit sa rezolv totul. Voi revenii cu o noua versiune.

Edited by IvanMihai, 06 April 2020 - 14:56.

Buna. O noua versiune (v2) a acestui program atasata.
Acelasi mod de utilizare ca originalul, doar implementarea s-a schimbat.

Totusi adunarea nu este dacat cu putin mai rapida decat cea din clasa luata de pe NET,
am rezolvat si acum nu mai inmulteste pentru carry (metoda finalize) la adunare,
Scaderea pe de alta parte este de aproximativ doua ori mai rapida decat cea din clasa luata de pe NET,
inca nu inteleg de ce exista asa de mare diferente intre adunare si scadere.

Pe de alta parte inmutirea este mult mult mai lenta ca adunarea/scaderea, si nu stiu daca o voi putea imbunatatii: de exemplu renuntarea la "/" si "%" in impartire - nu stiu daca este chiar si posibil.

GetSign/SetSign este tot acolo, motivul pe care poate fi lent este ca vectorul contine 0 la inceput ceea cred ca poate fi evitat cumva. (nu este facut in versiunea curenta).

Sper ca de data asta cel putin nu mai produce rezultate eronate.
Cateva teste valori si teste viteza nu ar strica.

IvanMihai, on 07 aprilie 2020 - 17:05, said:

Baza putere de 2 si transforma compilatorul / si % in operatii pe biti.

dani.user, on 07 aprilie 2020 - 17:40, said:

Multumesc pentru ajutorul acordat, poate ma insel dar ca timpul metodei void finalize(vector<long long>& res)
este neglijabil. Operatia de inmultire insasi este cea care ia mult timp, ceea ce este logic din moment ce face asta:

vector<long long> res(2 * len);  // result takes twice size
		for (int i = 0; i < len; ++i) {
			for (int j = 0; j < len; ++j) {
				res[i + j] += x[i] * y[j];
			}
		}

IvanMihai, on 07 aprilie 2020 - 17:05, said:

Tot clasa de pe net e mai rapida pentru scadere. Cam de 1.3x.

GetSign/SetSign tot afecteaza (nu inteleg de ce tii cu dintii de ele). Nici greater_or_equal nu e optim.

Inmultirea e foarte lenta fiindca ai un algoritm O(N²)

dani.user, on 07 aprilie 2020 - 18:40, said:

Nu cum pot sa reproduc rezultatul asta??
Este ceva in neregula cu ce am facut eu ???:

clock_t time_req;
time_req = clock();
for (int i=0;i<2768;i++)
{
bigint div = bigint("30194693...");
bigint divby = bigint("280000...");
bigint res = (div)+(divby);
}
//std::cout << res;
time_req = clock() - time_req;
printf("\r\nNew   took %f seconds\r\n",(float)time_req/CLOCKS_PER_SEC);

Am incercat si cu QueryPerformanceCounter - aproximativ acelasi rezultat!

Masori si parsarea nu doar adunarea.

Ai rulat in mod Debug sau Release?

In debug mode pana acum.
In release mode timpul este mult mult mai mic.
Ceva nu are sens, adica in debug mode vitezele sunt inversate: in release mode sub dureaza cel mai mult, in debug mode sub dureaza cel mai putin.

Masuratorile de timp se fac doar in release. Ce rezultate obtii in release, pentru i < 100000 sa zicem?

for (int i=0;i<332768;i++)
....

add de pe NET: 10.53, 10.73 secunde
add de mine: 12.43, 12.27 secunde
sub de mine: 12.95, 12.79 secunde

Am setat GetSign cu "return 1" si SetSign cu "return;" si timpul este de 12 secunde,
1 secunda ia faptul ca am "vector<long long>" in loc de "vector<int>"