Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Incalzire in pardoseala etapizata

Suprataxa card energie?!

Cum era nivelul de trai cam din a...

probleme cu ochelarii
 Impozite pe proprietati de anul v...

teava rezistenta panou apa calda

Acces in Curte din Drum National

Sub mobila de bucatarie si sub fr...
 Rezultat RMN

Numar circuite IPAT si prindere t...

Pareri brgimportchina.ro - teapa ...

Lucruri inaintea vremurilor lor
 Discuții despre TVR Sport HD.

Cost abonament clinica privata

Tremura toata, dar nu de la ro...

Renault Android
 

BigOperation - operatii numere mari

- - - - -
  • Please log in to reply
57 replies to this topic

#37
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Visual Studio are si profiler, care-ti arata care linii dureaza cel mai mult.

O provocare: folosirea instructiunilor speciale ale unor procesoare pentru a aduna/scadea/inmulti 4-8-16 valori deodata pentru si mai multa viteza

#38
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
Locatia proiectului original:
http://gist.github.c...ak-garg/4007974
sau
https://beet-aizu.gi...bigint.cpp.html

Inmultirea clasica este de compexitate O(n^2),
pe cand cea karatsuba este aproximativ O(n^1.5);
cu alte cuvinte karatsuba este mai eficienta decat inmultirea clasica,
intrebarea este ce este in neregula cu implementarea din proiectul asta ???
din moment ce viteza este mai lenta chiar si decat inmultirea clasica.

Edited by IvanMihai, 10 April 2020 - 14:09.


#39
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Care inmultire zici ca-i lenta? Ce timpi ai obtinut?

Edited by dani.user, 10 April 2020 - 14:42.


#40
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016

Quote

Care inmultire zici ca-i lenta?
inmutirea karatsuba din linkurile postate anterior,
Aceeasi cu https://github.com/t...ster/bigint.cpp
Cel putin de doua ori mai slaba ca inmultirea clasica,

Implementarea asta de exemplu are viteza buna:
https://github.com/9...master/bigint.c

#41
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Ce timpi ai obtinut? Pentru ce numere? In mod Release? Ce zice profilerul ca ar dura cel mai mult?

#42
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
In Relase mode, compar clasicul:
static bigint naive_mul(const bigint &x, const bigint &y) {
// Select the biggest length of two numbers
int len = max(x.a.size(), y.a.size());
int RealLen = len+len;
vll res(RealLen);
	
	 for (int i = 0; i < (int)x.a.size(); ++i) {
		 for (int j = 0; j < (int)y.a.size(); ++j) {
			 res[i+j] += (long long)x.a[i] * (long long)y.a[j];
		 }
	 }
bigint f_res; // final result
	 f_res.sign = x.sign * y.sign;
	 for (int i = 0, carry = 0; i < RealLen; i++) {
		 long long cur = std::abs(res[i]) + carry;
		 f_res.a.push_back(cur % base);
		 carry = (int) (cur / base);
	 }
f_res.trim();
	 return f_res;
}

cu metoda karatsubaMultiply din postarile anterioare,
intodeauna naive_mul este mari rapid (de 2 ori) ca karatsubaMultiply,
desi ar trebui ca karatsubaMultiply sa fie mai rapid.
Rularea profiler nu ajuta prea mult din moment ce este numai metoda karatsubaMultiply,
cel mai mult timp spune ca ia asta:
if (n <= 32) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
}

ceea ce nu ai cum sa schimbi!

Edited by IvanMihai, 10 April 2020 - 19:09.


#43
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Asta e tot algoritmul clasic, pentru n <= 32 cel putin.

Pana la urma incepe sa-mi scape care-i scopu proiectului..

#44
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
karatsubaMultiply utilizeaza inmultirea clasica: in toate implemetarile pe care le-am vazut.
Un singur lucru se mai poate face utilizarea unui array (new int[size]) in loc de vector<int> cand fac inmultirea
static bigint naive_mul(const bigint &x, const bigint &y) {
  // Select the biggest length of two numbers
  int x_size = x.a.size();
  int y_size = y.a.size();
  int len = max(x_size, y_size);
  int RealLen = len+len;
	   
  int* x2 = new int[x_size];
  int* y2 = new int[y_size];
  for (int i=0;i<x_size;i++)
  x2[i] = x.a[i];
  for (int i=0;i<y_size;i++)
  y2[i] = y.a[i];
  long long* res = new long long[RealLen];
  memset(res, 0, RealLen*sizeof(long long));
 
		for (int i = 0; i < x_size; ++i) {
			for (int j = 0; j < y_size; ++j) {
				res[i+j] += (long long)x2[i] * (long long)y2[j];
			}
		}
  delete x2;  // dealocate x2
  delete y2;  // dealocate y2
  bigint f_res;  // final result
		f_res.sign = x.sign * y.sign;
		for (int i = 0, carry = 0; i < RealLen; i++) {
			long long cur = std::abs(res[i]) + carry;
			f_res.a.push_back(cur % base);
			carry = (int) (cur / base);
		}
  delete res;
  f_res.trim();
		return f_res;
}


asta este doar o imbunatatire de 33%.

Oricum timpul inmultirii tinde spre 0. afisarea rezultatului ia mult insa.
Timpul impartirii este de 0.015 secunde. (Testarea cu numerele mari postate de dani.user intr-un post anterior.)

#45
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
33% imbunatatire cu array in loc de vector<int>? Foarte putin probabil in mod Release.

#46
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
Da, in mod release. De fapt am facut de 768 acea inmultire :
for (int i=0;i<768;i++)
{
bigint res = div*divby;
}
pentru o singura inmultire timpul tinde spre zero.

768 ori acea inmultire:
0.593 secunde versus 0.359 secunde.

Ah, si faptul ca am schimbat x.a.size() cu variabila x_size, y.a.size cu y_size.

Edited by IvanMihai, 13 April 2020 - 20:56.


#47
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Pune tot codu sa rulez si la mine.

#48
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
Ok. Tot proiectul atasat + cele 2 (versiuni) exe generate.

In clasa bigint.cpp la sfarsit:
bigint operator*(const bigint &v) const {
  return naive_mul(*this, v);

versus:
bigint operator*(const bigint &v) const {
  return naive_mul_v1(*this, v);

Attached Files


Edited by IvanMihai, 13 April 2020 - 21:15.


#49
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Nu-mi explic inca diferenta. Mai sap.

Compilat in 64-bit ruleaza cam de 2x mai repede.

#50
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
Nu are legatura cu modul de stocare (vector versus array)
ci cu faptul ca trebuie sa evaluam pointerul/dimensiunea in acele bucle.

#51
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Dimensiunea o rezolvi usor, dar tot mai ramanea o diferenta la [] ulterior.

Ramane intrebarea: ce vrei sa faci mai departe cu proiectul?

Sa inveti sa scrii C++ curat?
Sa aprofundezi matematica pentru numere mari?

#52
MihaiProg

MihaiProg

    Member

  • Grup: Members
  • Posts: 345
  • Înscris: 08.02.2016
Se poate face ceva mai simplu:
static bigint naive_mul(const bigint &x, const bigint &y) {
...
const int* x2 = &x.a[0];
const int* y2 = &y.a[0];

Varianta finala a proiectului va fi publicata pe github.
Nu m-am gandit la restul,
in acest moment ma gandesc doar la viteza,
si nu stiu inca daca algoritmii avansati gen karatsuba sau toom-cook
chiar ajuta sau sunt doar o complicare fara rost.

#53
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Ca sa vezi daca se poate mai repede, cel mai usor e sa compari cu ceva existent de calitate. Daca biblioteca gmp de care ziceam e mult mai rapida, de exemplu, e clar loc de mai bine.
Ti-am mai zis si de baze ca puteri de 2, nu de 10.

#54
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,194
  • Înscris: 24.02.2007
Pe linux are aceeasi viteza si varianta cu array si cea cu vector.

Apoi, o comparatie cu gmp pentru inmultire (17680 loops):
  • GMP: 665369 us
  • naive_mul: 6254298 us
Adica GMP e de vreo 10x mai rapid la inmultire.

Cam asa arata codul de folosire al GMP
mpz_t a, b, c;
mpz_init(c);
mpz_init_set_str(a, "123", 10);
mpz_init_set_str(b, "234", 10);


mpz_mul(c, a, b);

std::string cStr(mpz_sizeinbase(c, 10) + 2, ' ');
mpz_get_str(cStr.data(), 10, c);

std::cout << cStr << "\n";

mpz_clear(a);
mpz_clear(b);
mpz_clear(c);



Anunturi

Second Opinion Second Opinion

Folosind serviciul second opinion ne puteți trimite RMN-uri, CT -uri, angiografii, fișiere .pdf, documente medicale.

Astfel vă vom putea da o opinie neurochirurgicală, fără ca aceasta să poată înlocui un consult de specialitate. Răspunsurile vor fi date prin e-mail în cel mai scurt timp posibil (de obicei în mai putin de 24 de ore, dar nu mai mult de 48 de ore). Second opinion – Neurohope este un serviciu gratuit.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate