Ciao, mi sto cimentando nell'implementazione delle 4 operazioni tra big int.
Tempo fa lo avevo già fatto utilizzando come contenitori per i big int delle stringhe e come algoritmi per le operazioni quelli classici insegnati a scuola (con alcune piccole modifiche).
Per migliorare le prestazioni, nella nuova libreria che sto scrivendo, ho pensato di considerare più cifre alla volta e quindi ho utilizzato come contenitore dei big int un vector<uint32_t>: in pratica partendo da destra divido il big int in gruppi di nove cifre che saranno contenute all'interno di un uint32_t. Il motivo per cui utilizzo interi senza segno a 32 bit è che poi posso effettuare il prodotto (e quindi anche la somma e la differenza) tra due uint32_t utilizzando un uint64_t .
Quindi, a differenza della versione con le stringhe, dove effettuo i calcoli in base 10, qui effettuo i calcoli in base 10^9.
Poi, per migliorare ulteriormente le prestazioni, ho deciso di effettuare i calcoli non in base 10^9, ma in base 2^32, in modo da poter sfruttare la maggior efficienza di n>>32 (dove n è un uint64_t) rispetto a n/10^9 e di (uint32_t)n rispetto a n%10^9.
Relativamente a +, - e * ho riscontrato un netto miglioramento delle prestazioni (per la moltiplicazione si potrebbero anche usare algoritmi come quello di Karatsuba , ma per per il momento mi accontento del codice che ho già scritto). Per la divisione intera, invece, la situazione mi sembra un po' più complicata... cerco di fare il punto della situazione:
- l'algoritmo di divisione che sto utilizzando, tralasciando le varie versioni implementate e le varie ottimizzazioni (si spera) adottate, è quello della classica divisione in colonna che viene insegnata alle elementari;
- le singole cifre q_i del quoziente Q, a seconda della base b adottata, varieranno nell'intervallo [0;b-1]. Una volta assicuratoci con un semplice confronto che q_i!=0, possiamo facilmente fissare q_i_MAX, ossia il massimo valore che quella determinata cifra del quoziente può assumere. Fissato q_i_MAX, per giungere al q_i effettivo bisognerà ovviamente fare dei "tentativi", e il punto è proprio questo, ossia: maggiore è la base b adottata, maggiori saranno in media i tentativi da fare per giungere al valore di q_i corretto;
- partendo dalla suddetta osservazione, ho pensato che la cosa migliore sarebbe stata quella di eliminare i "tentativi" effettuando la divisione in base 2, dove infatti q_i, una volta escluso lo 0 con un semplice confronto, non può che essere 1.
Siete d'accordo, almeno in linea di massima, con questo mio ragionamento?
Per effettuare la divisione in base 2 ho convertito il big int da vector<uint32_t> in un vettore di valori booleani (inizialmente ho utilizzato un vector<bool>, ma poi l'ho sostituito con un vector<uint16_t> che, malgrado il maggior consumo di memoria, presenta tempi di accesso nettamente inferiori).
Alla fine della fiera però, facendo un test su una divisione tra un numero a 8400 cifre ed uno a 1100 cifre, la vecchia versione con le stringhe in base 10 impiega 170ms, mentre quella nuova in base 2 circa 320ms (ovviamente misurando solo l'esecuzione delle funzioni di divisione).
Di seguito il codice, e la spiegazione dell'algoritmo utilizzato, relativo alle due versioni:
- versione con le stringhe in base 10:
#include <iostream>
#include <algorithm>
#include <chrono>
#include <string>
using namespace std;
using namespace std::chrono;
string addition(const string &s1, const string &s2)
{
string s3;
unsigned int n = 0;
for(unsigned int i = 0; i < s1.size() || i < s2.size() || n; ++i)
{
if(i < s1.size())
{
n += s1[s1.size() - 1 - i] - '0';
}
if(i < s2.size())
{
n += s2[s2.size() - 1 - i] - '0';
}
s3.push_back(n % 10 + '0');
n /= 10;
}
reverse(s3.begin(), s3.end());
return s3;
}
string subtraction(const string &s1, const string &s2)
{
string s3;
unsigned int n = 10;
for(unsigned int i = 0; i < s1.size(); ++i)
{
n = 10 + s1[s1.size() - 1 - i] - '0' - (n < 10);
if(i < s2.size())
{
n -= s2[s2.size() - 1 - i] - '0';
}
s3.push_back(n % 10 + '0');
}
for(unsigned int i = s3.size() - 1; i && s3[i] == '0'; --i)
{
s3.pop_back();
}
reverse(s3.begin(), s3.end());
return s3;
}
string multiplication(const string &s1, const string &s2)
{
string s3 = "0";
string temp;
for(unsigned int i = 0; i < s1.size(); ++i)
{
temp.resize(0);
unsigned int n = 0;
for(unsigned int j = 0; j < s2.size(); ++j)
{
n = (s1[s1.size() - 1 - i] - '0') * (s2[s2.size() - 1 - j] - '0') + n / 10;
temp.push_back(n % 10 + '0');
}
if(n > 9)
{
temp.push_back(n / 10 + '0');
}
reverse(temp.begin(), temp.end());
for(unsigned int j = 0; j < i; ++j)
{
temp.push_back('0');
}
s3 = addition(s3, temp);
}
return s3;
}
int compare_abs(const string &s1, const string &s2)
{
if(s1.size() != s2.size())
{
return((int)s1.size() - s2.size());
}
unsigned int i;
for(i = 0; i < s1.size() - 1 && s1[i] == s2[i]; ++i);
return((int)s1[i] - s2[i]);
}
string division(const string &s1, const string &s2, const bool flag_quotient)
{
string quotient;
string rest;
unsigned int i;
for(i = 0; compare_abs(rest, s2) < 0; ++i)
{
rest.push_back(s1[i]);
}
while(true)
{
unsigned int q;
int relation = compare_abs(rest, s2);
if(relation <= 0)
{
q = !relation;
if(!relation)
{
rest = "0";
}
}
else
{
unsigned int r = rest[0] - '0';
if(rest.size() > s2.size())
{
r = r * 10 + rest[1] - '0';
}
q = r / (s2[0] - '0');
if(q > 9)
{
q = 9;
}
while(q > 1)
{
bool flag = true;
unsigned int a = r;
for(unsigned int j = 0; j < s2.size(); ++j)
{
unsigned int b = q * (s2[j] - '0');
if(a < b)
{
--q;
flag = false;
break;
}
if(a - b >= q)
{
break;
}
if(j != s2.size() - 1)
{
a = (a - b) * 10 + rest[j + 1 + (rest.size() > s2.size())] - '0';
}
}
if(flag)
{
break;
}
}
rest = subtraction(rest, multiplication({char(q + '0')}, s2));
}
quotient.push_back(q + '0');
if(i == s1.size())
{
break;
}
if(rest[0] == '0')
{
rest.resize(0);
}
rest.push_back(s1[i++]);
}
return(flag_quotient ? quotient : rest);
}
int main()
{
string a("123456789987654321");
string b("157988");
auto start1 = high_resolution_clock::now();
string q = division(a, b, true);
auto stop1 = high_resolution_clock::now();
auto duration1 = duration_cast<milliseconds>(stop1 - start1);
string r = division(a, b, false);
cout << q << endl << endl;
cout << r << endl << endl;
cout << duration1.count() << " ms" << endl;
}
- versione con il vettore di booleani in base 2:
#include <iostream>
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <string>
#include <vector>
using namespace std;
using namespace std::chrono;
const uint8_t N = 32;
const uint32_t S_10 = 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 << N) + v_2[j];
if(i || r / S_10)
{
v_2[i++] = r / S_10;
r %= S_10;
}
}
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 * S_10 + v_10[j];
if(i || r >> N)
{
v_10[i++] = r >> N;
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(const string &s)
{
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');
}
}
return(from_10_to_2(v_10));
}
void print(vector<uint32_t> v_2)
{
reverse(v_2.begin(), v_2.end());
vector<uint32_t> v_10 = from_2_to_10(v_2);
for(unsigned int i = 0; i < v_10.size(); ++i)
{
if(i)
{
for(int32_t j = S_10 / 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;
}
vector<uint16_t> to_v_bool(const vector<uint32_t> &v)
{
vector<uint16_t> b(v.size() * N);
for(uint32_t i_v = 0; i_v < v.size(); ++i_v)
{
for(uint32_t i_b = (i_v + 1) * N - 1, n = v[v.size() - 1 - i_v]; n; n >>= 1)
{
b[i_b--] = bool(1 & n);
}
}
return b;
}
vector<uint32_t> from_v_bool(const vector<uint16_t> &b)
{
vector<uint32_t> v(b.size() / N);
for(uint32_t i_v = v.size() - 1, i_b = 0; i_b < b.size(); --i_v)
{
for(uint32_t n = (uint32_t)1 << N - 1; n; n >>= 1)
{
if(b[i_b++])
{
v[i_v] |= n;
}
}
}
return v;
}
vector<uint32_t> division_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2, const bool flag_q)
{
vector<uint16_t> b1 = to_v_bool(v1);
vector<uint16_t> b2 = to_v_bool(v2);
vector<uint16_t> q(b1.size() - b2.size() + N);
uint64_t sx_2 = 0;
for(; !b2[sx_2]; ++sx_2);
uint64_t n_b2 = b2.size() - sx_2;
for(uint64_t sx_1 = 0, dx_1 = n_b2 - 1; dx_1 < b1.size(); ++sx_1, ++dx_1)
{
uint64_t i = sx_1 && b1[sx_1 - 1] ? n_b2 : 0;
for(; i < n_b2 && b1[sx_1 + i] == b2[sx_2 + i]; ++i);
if(i == n_b2 || !b2[sx_2 + i])
{
q[dx_1 + N - b2.size()] = 1;
for(uint64_t j = 0; j < n_b2; ++j)
{
if(b2[b2.size() - 1 - j])
{
for(uint64_t k = dx_1 - j; b1[k] = !b1[k]; --k);
}
}
}
}
return(flag_q ? from_v_bool(q) : from_v_bool(b1));
}
int main()
{
vector<uint32_t> a = from_string("123456789987654321");
vector<uint32_t> b = from_string("157988");
auto start1 = high_resolution_clock::now();
vector<uint32_t> q = division_2(a, b, true);
auto stop1 = high_resolution_clock::now();
auto duration1 = duration_cast<milliseconds>(stop1 - start1);
vector<uint32_t> r = division_2(a, b, false);
print(q);
cout << endl;
print(r);
cout << endl;
cout << duration1.count() << " ms" << endl;
}
Detto ciò, è vero che il vettore booleano è circa 3,3 volte più lungo della stringa, ma nella versione con le stringhe ci sono comunque varie operazioni con interi, senza dimenticare poi la parte relativa ai "tentativi"... probabilmente non mi resta che arrendermi all'evidenza, ma nella mia ignoranza trovo questa differenza nelle prestazioni abbastanza controintuitiva,
che ne pensate?