vict85 ha scritto:Mi sembra sospetto che tu abbia bisogno di usare questo tipo di approccio per fare una divisione di interi. bitset ha altri scopi. Non ho però avuto tempo di guardare il tuo codice. Immagino che tu stia usando un approccio sbagliato per la base \( 10^9 \).
Cerco di fare il punto sulla questione della divisione tra "big_int" che ho introdotto negli ultimi post:
- 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 a scuola (la cosiddetta "divisione lunga");
- 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.
Siete d'accordo con questa cosa, oppure sto dicendo una sciocchezza?- 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$. Nel precedente post ho improvvisato una versione con i bitset per interi a 64 bit; nel frattempo credo di essere riuscito ad implementare la divisione binaria anche tra "big_int" ricorrendo a
vector<bitset<32>> (visto che le funzioni di +,-,* già implementate sfruttano
vector<uint32_t>), ecco il codice (ho omesso le funzioni non necessarie):
Testo nascosto, fai click qui per vederlo
- Codice:
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <limits>
#include <string>
#include <vector>
using namespace std;
const uint8_t N = 32;
const uint32_t S_10 = 1000000000;
const uint64_t S_2 = (uint64_t)numeric_limits<uint32_t>::max() + 1;
#define FUN(b, i) b[(i) / N][N - 1 - (i) % N]
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));
}
vector<bitset<N>> to_bitset(const vector<uint32_t> &v)
{
vector<bitset<N>> b;
b.reserve(v.size());
for(unsigned int i = 0; i < v.size(); ++i)
{
b.push_back(bitset<N>(v[v.size() - 1 - i]));
}
return b;
}
vector<uint32_t> from_bitset(const vector<bitset<N>> &b)
{
vector<uint32_t> v;
v.reserve(b.size());
for(unsigned int i = 0; i < b.size(); ++i)
{
v.push_back(b[b.size() - 1 - i].to_ulong());
}
return v;
}
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<uint32_t> division_2(vector<bitset<N>> b1, const vector<bitset<N>> &b2, const bool flag_q)
{
vector<bitset<N>> q(b1.size() - b2.size() + 1);
uint64_t b1N = b1.size() * N;
uint64_t b2N = b2.size() * N;
uint64_t b2_i = 0;
for(; !FUN(b2, b2_i); ++b2_i);
uint64_t b2_n = b2N - b2_i;
for(uint64_t i = b2_n - 1, b1_i = i + 1 - b2_n; i < b1N; ++i, ++b1_i)
{
uint64_t j = b1_i && FUN(b1, b1_i - 1) ? b2_n : 0;
for(; j < b2_n && FUN(b1, b1_i + j) == FUN(b2, b2_i + j); ++j);
if(j == b2_n || !FUN(b2, b2_i + j))
{
FUN(q, i + N - b2N) = true;
for(uint64_t k_1 = 0; k_1 < b2_n; ++k_1)
{
if(FUN(b2, b2N - 1 - k_1))
{
for(uint64_t k_2 = i - k_1; FUN(b1, k_2) = !FUN(b1, k_2); --k_2);
}
}
}
}
return(flag_q ? from_bitset(q) : from_bitset(b1));
}
int main()
{
vector<uint32_t> a = from_string("1234567890556677889925450987654321");
vector<uint32_t> b = from_string("835792468007");
vector<uint32_t> q = division_2(to_bitset(a), to_bitset(b), true);
vector<uint32_t> r = division_2(to_bitset(a), to_bitset(b), false);
print(q);
cout << endl;
print(r);
cout << endl;
}
Il codice sembra funzionare, ma considerazioni e consigli al riguardo sarebbero davvero ben accetti;
- passiamo ora alle note dolenti... ero abbastanza soddisfatto della divisione appena postata, tuttavia confrontandola con la versione postata
qui (divisione in base $10$ che fa parte di una vecchia libreria sui "big_int" basata sulle stringhe, che ho implementato tempo fa), ne esce sconfitta, e anche di parecchio! Per esempio nella divisione tra un numero a 4180 cifre ed uno a 556 cifre, la vecchia versione con le stringhe impiega 50ms, mentre questa nuova 110ms (misurando solo l'esecuzione delle funzioni di divisione).
Eppure la funzione appena postata mi sembra abbastanza "compatta", priva di "tentativi" e basata su operazioni "veloci"...
secondo voi dove possono celarsi le criticità che la rendono più lenta della vecchia versione basata sulle stringhe?
