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 |
BigOperation - operatii numere mari
Last Updated: Jun 20 2020 12:59, Started by
MihaiProg
, Apr 03 2020 13:53
·
0
#37
Posted 08 April 2020 - 13:26
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
Posted 10 April 2020 - 14:09
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
Posted 10 April 2020 - 14:41
Care inmultire zici ca-i lenta? Ce timpi ai obtinut?
Edited by dani.user, 10 April 2020 - 14:42. |
#40
Posted 10 April 2020 - 16:27
Quote Care inmultire zici ca-i lenta? 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
Posted 10 April 2020 - 17:17
Ce timpi ai obtinut? Pentru ce numere? In mod Release? Ce zice profilerul ca ar dura cel mai mult?
|
#42
Posted 10 April 2020 - 19:09
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
Posted 10 April 2020 - 22:55
Asta e tot algoritmul clasic, pentru n <= 32 cel putin.
Pana la urma incepe sa-mi scape care-i scopu proiectului.. |
#44
Posted 13 April 2020 - 20:34
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
Posted 13 April 2020 - 20:38
33% imbunatatire cu array in loc de vector<int>? Foarte putin probabil in mod Release.
|
#46
Posted 13 April 2020 - 20:51
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. |
|
#48
Posted 13 April 2020 - 21:11
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 FilesEdited by IvanMihai, 13 April 2020 - 21:15. |
#49
Posted 13 April 2020 - 22:18
Nu-mi explic inca diferenta. Mai sap.
Compilat in 64-bit ruleaza cam de 2x mai repede. |
#50
Posted 14 April 2020 - 09:44
Nu are legatura cu modul de stocare (vector versus array)
ci cu faptul ca trebuie sa evaluam pointerul/dimensiunea in acele bucle. |
#51
Posted 14 April 2020 - 09:56
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
Posted 14 April 2020 - 14:04
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
Posted 14 April 2020 - 14:25
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
Posted 14 April 2020 - 17:13
Pe linux are aceeasi viteza si varianta cu array si cea cu vector.
Apoi, o comparatie cu gmp pentru inmultire (17680 loops):
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
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users