25/11/2021, 21:57
vict85 ha scritto:Sbagli, e anche di molto. Il tuo codice è ben poco performante ed è dominato dalle allocazioni di memoria. Per capire quanto sia pessimo...
#include <iostream>
#include <chrono>
#include <cstdint>
#include <vector>
using namespace std;
using namespace std::chrono;
vector<uint32_t> multiplication_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &v_1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &v_2 = v_1 == v1 ? v2 : v1;
vector<uint32_t> v3(v_1.size() + v_2.size(), 0);
for(unsigned int i = 0; i < v_1.size(); ++i)
{
uint64_t r1 = 0;
uint64_t r2 = 0;
v3.resize(i);
for(unsigned int j = 0; j < v_2.size() || r1 || r2; ++j)
{
if(j < v_2.size())
{
r1 += (uint64_t)v_1[i] * v_2[j];
}
r2 += v3[v3.size()] + r1 % 1000000000;
v3.push_back(r2 % 1000000000);
r1 /= 1000000000;
r2 /= 1000000000;
}
}
return v3;
}
void print_10(const vector<uint32_t> &v)
{
for(unsigned int i = 0; i < v.size(); ++i)
{
if(i)
{
for(int32_t j = 99999999; j && j >= v[v.size() - 1 - i]; j /= 10)
{
cout << "0";
}
}
cout << v[v.size() - 1 - i];
}
cout << endl;
}
int main()
{
cout << "calcolo di 12345^1000 (versione vector ottimizzata base 10): ";
vector<uint32_t> a = {12345};
vector<uint32_t> b = {1};
auto start1 = high_resolution_clock::now();
for(unsigned int i = 0; i < 1000; ++i)
{
b = multiplication_10(a, b);
}
auto stop1 = high_resolution_clock::now();
auto duration1 = duration_cast<milliseconds>(stop1 - start1);
cout << duration1.count() << " ms" << endl;
print_10(b);
}
calcolo di 12345^1000 (versione vector ottimizzata base 10): 2 ms
30980916979571261678037792640547069821046036601263871423172603964432880446620608
46921638204797951863536177399422240269688598440386160524113311366171137540029427
91772720296320086301939317723959165750831660314625504906217694965268441368838284
91469899680820312066142708028389393562630538115386600687343726225365416760557989
41423155494189268546531047348336572287590039126299044550768543719716900090002922
31442640702405997349818652846007594672121952993600612240375288011172203296667256
96103967654224628215610071281098978353840302864126825283500458106807878522509659
21789617648423284361266990316368590121427804100038121975738472719701414718604485
59701917501364026826498681300417013008430237787456258392796158010957510644217069
98341913428129617946641478177778534617429438982842385866806060632693349145018235
12239084719922296603840279509341320330116129246617953872657843763736914650433910
69947270507908425989612108500884562232290869386787877493097701502859303071373757
98655553418051305869563741235177332696717875374591544971368987407514335651644993
48432070402708303140803815093836661660356285937395020277788919864363825187404391
66973596854885177857972177954369036272112372120342169211179441034974532201077985
02955733113425832358515283713193528314018013484978895836581392051714102432880542
73520458521176241545142042871027819038633452778882009889151826115545711661170538
36747195908282969788810091869993349713112267938558757495744359548488837018005043
40690662067911606624152430636860695557307662212093813837874302080738361232336551
74575751749331919935735057962393028640196663750515631155647068114586019547125009
66722593376174534528998418559797925572480799490873627279344223127796375553240572
15862646352988229249067464618561571347927535747106152891191398219533463769254976
60439255056416164625808728071677859168160485698031944035324637075340851589197234
49415021308596978472922475070959635686086272975863164803202569864125951706329194
84682164033661640489555929737222661905985234140148505838990396502711735660674750
18401069005143388746198994486546761245453653960305361484058030629364813564938166
77996142347736230549290495923638437033343172179181801753570878708654257297687835
26965343706996729232760606845658227256991400912979153167112235978039183655623558
98974562226281554721134128093680325493342116410019082065191222152604701943612903
09012247981704105777443919500572258770469577053059340743175489359094192490153869
68801837378836637000835706292471984808215940621442162785226511155294831484513417
52199992248704863885652427271790306569255537274573369763448958846105089050305523
89745067153053340339925663961641409046696655149031934108909967069140051370963337
42293240129209862323592579138243170317263223252880934191859024800749271249770266
97005663041724543518495369422176498807371766396344183276476753948925774528804843
05655939076362259220197812625222643643191577117100739643427218343227279208350495
80217315761848037089866403378986967045064502829656583826962255738198354622836756
35667056382976855279913816549680982420288449166338344372060236443053987567633619
13498399705896830636029425918669043084740115869198785908560762760382332445251211
23130345477189333775791288130929475816834573933825566780851556546207567350921324
84252238947178033958197247843877788771142111236322569477645881902111263631757196
58176061228259719565346549780300325616948182208870465891192349276710668441048641
29975170039721209641075115717792256013191312063969737958364103235501978884662125
34511083901139702691409815298297037003389820841696983552075032727515727567122502
94394271855766758729580875496156304085099464372152797873952740789997020284489294
85834734357491174993595291833627475607319515601968664863128650348891298074261373
11630439976466542171620548090996899637416145616614625955318606438025388953080883
19814146640625180562801649749164640860829007177519736517996763714855878556975798
53551247141335832576720350019360024777873472945177760531417791020722451271496295
35007942765141973975166467388687997634230267335326011501002931165248908784123116
24139545280293494422725269869365974996851368188630938826921834561289870180189609
527587890625
Process returned 0 (0x0) execution time : 0.118 s
Press any key to continue.
vict85 ha scritto:prova a compilare e lanciare questa versione: ...
v
nel for più interno possa essere potenzialmente soggetta ad overflow.vector<uint32_t> multiplication_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &v_1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &v_2 = v_1 == v1 ? v2 : v1;
vector<uint32_t> v3(v_1.size() + v_2.size(), 0);
for(unsigned int i = 0; i < v_1.size(); ++i)
{
uint64_t r1 = 0;
uint64_t r2 = 0;
v3.resize(i);
for(unsigned int j = 0; j < v_2.size() || r1 || r2; ++j)
{
if(j < v_2.size())
{
r1 += (uint64_t)v_1[i] * v_2[j];
}
r2 += v3[v3.size()] + (uint32_t)r1;
v3.push_back((uint32_t)r2);
r1 >>= 32;
r2 >>= 32;
}
}
return v3;
}
26/11/2021, 00:02
26/11/2021, 00:21
utente__medio ha scritto:vict85 ha scritto:prova a compilare e lanciare questa versione: ...
Così su due piedi sembra che restituisca un risultato errato; non so se può entrarci in qualche modo quanto detto in precedenza, ossia che la variabilev
nel for più interno possa essere potenzialmente soggetta ad overflow.
26/11/2021, 09:28
apatriarca ha scritto:@ghira: il calcolo non è importante perché lo scopo era quello di confrontare le performance di due codici che fanno la stessa cosa.
26/11/2021, 10:33
ghira ha scritto:apatriarca ha scritto:@ghira: il calcolo non è importante perché lo scopo era quello di confrontare le performance di due codici che fanno la stessa cosa.
Ok, grazie. Volevo solo controllare perché mi ricordo di aver visto colleghi informatici anni fa che hanno dovuto calcolare la 47millesima potenza di qualcosa e qualcuno l'ha fatto con 47mila moltiplicazioni...
pow
non è disponibile, e trovo sia anche molto abusato dai principianti (usarlo per calcolare potenze basse è senza senso). Qualcosa come \(x^{1000}\) si può comunque fare con meno moltiplicazioni, o usando https://en.wikipedia.org/wiki/Exponenti ... y_squaring oppure con altri metodi simili.
26/11/2021, 11:00
vict85 ha scritto:Qualcosa come \(x^{1000}\) si può comunque fare con meno moltiplicazioni, o usando https://en.wikipedia.org/wiki/Exponenti ... y_squaring oppure con altri metodi simili.
26/11/2021, 14:15
resize
e del v3[v3.size()]
mi confonde un po'. Se al posto delle parentesi avessi usato la funzione at
avresti generato una eccezione. Il codice non fa nulla di sbagliato dal punto di vista della memoria, è solo un uso strano dell'interfaccia vector. Il tuo codice è assolutamente equivalente a questo, più leggibile:vector< uint32_t >
multiplication_10b( const vector< uint32_t >& v1, const vector< uint32_t >& v2 )
{
const vector< uint32_t >& v_1 = v1.size( ) < v2.size( ) ? v1 : v2;
const vector< uint32_t >& v_2 = v_1 == v1 ? v2 : v1;
vector< uint32_t > v3( v_1.size( ) + v_2.size( ), 0 );
uint64_t size = 0;
for ( unsigned int i = 0; i < v_1.size( ); ++i )
{
uint64_t r1 = 0;
uint64_t r2 = 0;
size = i;
for ( unsigned int j = 0; j < v_2.size( ) || r1 || r2; ++j )
{
if ( j < v_2.size( ) )
{
r1 += (uint64_t)v_1[ i ] * v_2[ j ];
}
r2 += v3[ size ] + r1 % 1000000000;
v3[ size++ ] = r2 % 1000000000;
r1 /= 1000000000;
r2 /= 1000000000;
}
}
v3.resize( size );
return v3;
}
27/11/2021, 15:12
#include <iostream>
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <string>
#include <vector>
using namespace std;
using namespace std::chrono;
const uint32_t N = 1000000000;
vector<uint32_t> from_2_to_10(vector<uint32_t> v_2)
{
vector<uint32_t> v_10;
do
{
uint64_t r = 0;
unsigned int i = 0;
for(unsigned int j = 0; j < v_2.size(); ++j)
{
r = (r << 32) + v_2[j];
if(i || r / N)
{
v_2[i++] = r / N;
r %= N;
}
}
v_2.resize(i);
v_10.push_back(r);
}
while(v_2.size());
return v_10;
}
vector<uint32_t> from_10_to_2(vector<uint32_t> v_10)
{
vector<uint32_t> v_2;
do
{
uint64_t r = 0;
unsigned int i = 0;
for(unsigned int j = 0; j < v_10.size(); ++j)
{
r = r * N + v_10[j];
if(i || r >> 32)
{
v_10[i++] = r >> 32;
r = (uint32_t)r;
}
}
v_10.resize(i);
v_2.push_back(r);
}
while(v_10.size());
return v_2;
}
vector<uint32_t> from_string_10(const string &s, bool flag = true)
{
vector<uint32_t> v_10;
unsigned int i = 0;
while(i < s.size())
{
unsigned int j_max = v_10.size() ? 9 : s.size() % 9;
v_10.push_back(0);
for(unsigned int j = 0; j < j_max; ++j)
{
v_10.back() = v_10.back() * 10 + (s[i++] - '0');
}
}
if(flag)
{
reverse(v_10.begin(), v_10.end());
}
return v_10;
}
vector<uint32_t> from_string_2(const char *s)
{
return(from_10_to_2(from_string_10(s, false)));
}
vector<uint32_t> multiplication_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
vector<uint32_t> v3(w1.size() + w2.size(), 0);
for(unsigned int i = 0; i < w1.size(); ++i)
{
uint64_t r1 = 0;
uint64_t r2 = 0;
v3.resize(i);
for(unsigned int j = 0; j < w2.size() || r1 || r2; ++j)
{
if(j < w2.size())
{
r1 += (uint64_t)w1[i] * w2[j];
}
r2 += v3[v3.size()] + r1 % N;
v3.push_back(r2 % N);
r1 /= N;
r2 /= N;
}
}
return v3;
}
vector<uint32_t> multiplication_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
vector<uint32_t> v3(w1.size() + w2.size(), 0);
for(unsigned int i = 0; i < w1.size(); ++i)
{
uint64_t r1 = 0;
uint64_t r2 = 0;
v3.resize(i);
for(unsigned int j = 0; j < w2.size() || r1 || r2; ++j)
{
if(j < w2.size())
{
r1 += (uint64_t)w1[i] * w2[j];
}
r2 += v3[v3.size()] + (uint32_t)r1;
v3.push_back((uint32_t)r2);
r1 >>= 32;
r2 >>= 32;
}
}
return v3;
}
void print_10(const vector<uint32_t> &v_10)
{
for(unsigned int i = 0; i < v_10.size(); ++i)
{
if(i)
{
for(int32_t j = N / 10 - 1; j && j >= v_10[v_10.size() - 1 - i]; j /= 10)
{
cout << "0";
}
}
cout << v_10[v_10.size() - 1 - i];
}
cout << endl;
}
void print_2(vector<uint32_t> v_2)
{
reverse(v_2.begin(), v_2.end());
print_10(from_2_to_10(v_2));
}
int main()
{
cout << "calcolo di 12345^1000 (versione vector ottimizzata base 10): ";
vector<uint32_t> a = from_string_10("43695595240774383441671015625");//12345^7
vector<uint32_t> b = from_string_10("12345");
auto start1 = high_resolution_clock::now();
for(unsigned int i = 0; i < 993; ++i)
{
a = multiplication_10(a, b);
}
auto stop1 = high_resolution_clock::now();
auto duration1 = duration_cast<milliseconds>(stop1 - start1);
cout << duration1.count() << " ms" << endl << endl;
print_10(a);
//-----------------------------------------------------------------------
cout << endl << "calcolo di 12345^1000 (versione vector ottimizzata base 2): ";
vector<uint32_t> c = from_string_2("43695595240774383441671015625");//12345^7
vector<uint32_t> d = from_string_2("12345");
auto start2 = high_resolution_clock::now();
for(unsigned int i = 0; i < 993; ++i)
{
c = multiplication_2(c, d);
}
auto stop2 = high_resolution_clock::now();
auto duration2 = duration_cast<milliseconds>(stop2 - start2);
cout << duration2.count() << " ms" << endl << endl;
print_2(c);
}
vict85 ha scritto:Il codice non fa nulla di sbagliato dal punto di vista della memoria, è solo un uso strano dell'interfaccia vector. Il tuo codice è assolutamente equivalente a questo, più leggibile: ...
30/11/2021, 16:37
vector<uint32_t> addition_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
vector<uint32_t> v3;
v3.reserve(w2.size() + 1);
uint64_t r = 0;
unsigned int i = 0;
for(; i < w1.size() || r; ++i)
{
if(i < w1.size())
{
r += (uint64_t)w1[i] + w2[i];
}
else if(i < w2.size())
{
r += (uint64_t)w2[i];
}
v3.push_back(r % N);
r /= N;
}
for(; i < w2.size(); ++i)
{
v3.push_back(w2[i]);
}
return v3;
}
vector<uint32_t> addition_10b(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
vector<uint32_t> v3;
v3.reserve(w2.size() + 1);
uint64_t r = 0;
for(unsigned int i = 0; i < w2.size() || r; ++i)
{
r += uint64_t(i < w1.size() ? w1[i] : 0) + uint64_t(i < w2.size() ? w2[i] : 0);
v3.push_back(r % N);
r /= N;
}
return v3;
}
const uint32_t N = 1000000000;
const uint64_t M = (uint64_t)numeric_limits<uint32_t>::max() + 1;
vector<uint32_t> subtraction_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
vector<uint32_t> v3;
v3.reserve(v1.size());
uint64_t r = N;
for(unsigned int i = 0; i < v1.size(); ++i)
{
r = N + v1[i] - (r < N);
if(i < v2.size())
{
r -= v2[i];
}
v3.push_back(r % N);
}
for(unsigned int i = v3.size() - 1; i && !v3[i]; --i)
{
v3.pop_back();
}
return v3;
}
vector<uint32_t> subtraction_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
vector<uint32_t> v3;
v3.reserve(v1.size());
uint64_t r = M;
for(unsigned int i = 0; i < v1.size(); ++i)
{
r = M + v1[i] - (r < M);
if(i < v2.size())
{
r -= v2[i];
}
v3.push_back((uint32_t)r);
}
for(unsigned int i = v3.size() - 1; i && !v3[i]; --i)
{
v3.pop_back();
}
return v3;
}
01/12/2021, 11:45
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
w1 == v1
fa il confronto tra vector e non di puntatori. Per confrontare i puntatori devi scrivere &w1 == &v1
.&w1 == &v1
si confrontano due registri.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.