Ciao,in questi giorni ho scritto un programma,e funziona abbastanza bene con numeri che hanno cifre comprese tra 0 e 30/31 con numeri più grandi ci mette troppo tempo(anche ore).
Il codice è una prima stesura,funziona ma vorrei dei consigli per migliorarlo,in particolare la velocità di esecuzione,ad esempio velocizzando le funzioni sostituendole con altre equivalenti ma con un costo (in tempo) minore.
l'idea comunque è questa:
es.
1-Numero:100 (Inserito in una stringa)
2-Con una funzione lo trasformo in un vettore contenente ogni sua singola cifra es.V=(1,0,0)
3.Chiamo una funzione decTobin_vec che dovrà restituire un vettore col numero iniziale in binario:
Questa funzione (utilizzandone altre),divide ogni cifra del numero,prese singolarmente dal vettore
V=(1,0,0),in binario,assegnando ad ogni numero binario lo stesso numero di cifre.
es.Vdec=(1,0,0)-> V[0]bin=(00000001) , V[1]bin=(00000000) , V[2]bin=(00000000) *Sempre 8 cifre,nel programma uso un costante VECPARTITION=128
Poi inserisco tutti i risultati in un unico vettore con un pushback, es.W=(000000010000000000000000)
4)Da questo punto in poi l'idea è la seguente:
Ndec=100=(1*10^2+0*10^1+0*10^0)=(1*2^2*5^2+0*2^1*5^1+0*2^0*5^0)=(00000001*00000100*00011001+00000000*00000010*00000101+00000000*00000001*00000001)
-I vettori con le cifre del numero li ho già e con una funzione slice selezione ogni volta le seguenti 8,e una alla volta le moltiplico per il fattore 10(2*5,calcolato con pow(),e a sua volta convertito in un vettore di numeri binari),corrispondente.
-E in fine sommo tutto.
-Il risultato è il vettore di 0 e 1 corrispondente al numero decimale iniziale.
-Ogni somma e moltiplicazione è fatta con delle funzioni che fanno le operazioni con i vettori di numeri binari come se le facessimo noi su un foglio quindi seguono le stesse regole,per ovviare alla limitazione della rappresentazione con unsigned long long.
-Oltre fattori maggiori a 5^22 c'era un errore sulla rappresentazione del numero quindi con cifre del numero decimale iniziale maggiore a 23,il fattore successivo viene fatto con le opportune somme in binario di 5^22.
Gradirei altre idee,consigli,suggerimenti,miglioramenti,per migliorare la qualità del codice,la velocità e per consentire di rappresentare in minor tempo valori maggiori,grazie.
Il codice forse è poco chiaro nel caso sarei disponibile per chiarimenti per chi fosse interessato ad aiutarmi.
#include <iostream>
#include <utility>
#include <vector>
#include <cmath>
#include <algorithm>
#include <chrono>
void decTobin_vec(std::vector<unsigned short int> &N, std::vector<unsigned short int> &n);
std::vector<unsigned short int> *decTobin(unsigned long long int cifra);
std::vector<unsigned short int> *
mult_bin_vec(std::vector<unsigned short int> &b1, std::vector<unsigned short int> &b2);
std::vector<unsigned short int> *sum_bin_vec(std::vector<unsigned short int> &b1, std::vector<unsigned short int> &b2);
std::vector<unsigned short int> *stringTovec(const std::string &numstring);
unsigned short const int VECPARTITION = 128;
int main() {
auto start = std::chrono::steady_clock::now();
//std::vector<unsigned short int> N = *stringTovec("938571980750874560846238947123908412358019875");
// <<Questo ci dovrebbe mettere circa 2 ore per convertirsi>>
std::vector<unsigned short int> N = *stringTovec("999999999999999999999999999999999");
//Ogni cifra aumenta il tempo di esecuzione di circa un fattore 5x
std::vector<unsigned short int> n = {};
for (unsigned short i : N)
std::cout << i;
std::cout << std::endl << std::endl;
std::cout << "Size:" << N.size() << std::endl;
decTobin_vec(N, n);
bool found = false;
for (int i = 0; i < n.size(); i++) {
if (n.at(static_cast<unsigned long long int>(i)) == 0 && !found) {
n.erase(n.begin() + i);
i--;
continue;
} else {
found = true;
std::cout << n.at(static_cast<unsigned long long int>(i));
}
}
std::cout << std::endl;
auto end = std::chrono::steady_clock::now();
auto diff = end - start;
std::cout << std::endl;
std::cout << "Time of Execution:";
std::cout << std::chrono::duration<double, std::milli>(diff).count() << "ms" << std::endl;
return 0;
}
template<typename T>
std::vector<T> *slice(std::vector<T> &v, int m, int n) {
auto *vec = new std::vector<T>{};
for (int i = m; i <= n; i++) {
vec->push_back(v.at(i));
}
return vec;
}
void decTobin_vec(std::vector<unsigned short int> &N, std::vector<unsigned short int> &n) {
std::cout << "Work in Progress..." << std::endl;
std::cout << std::endl;
for (unsigned short i : N) {
std::vector<unsigned short int> *v = nullptr;
v = decTobin(i);
for (auto j = 0; j < v->size(); j++)
n.push_back(v->at(static_cast<unsigned long long int>(j)));
}
auto *conv = new std::vector<unsigned short int>{};
for (unsigned long long int e = N.size() - 1, i = 0, j = i + VECPARTITION - 1;
j < n.size(); i += VECPARTITION, j += VECPARTITION, e--) {
std::vector<unsigned short int> *tmp = slice(n, static_cast<int>(i), static_cast<int>(j));
auto pow2 = new std::vector<unsigned short int>{};
auto pow5 = new std::vector<unsigned short int>{};
if (e <= 22) {
pow2 = decTobin(static_cast<unsigned long long int>(pow(2, e)));
pow5 = decTobin(static_cast<unsigned long long int>(pow(5, e)));
} else if (e > 22) {
for (int exp = 22, c = 0; c < pow(2, (e - exp)); c++) {
pow2 = sum_bin_vec(*decTobin(static_cast<unsigned long long int>(pow(2, 22))), *pow2);
}
for (int exp = 22, c = 0; c < pow(5, (e - exp)); c++) {
pow5 = sum_bin_vec(*decTobin(static_cast<unsigned long long int>(pow(5, 22))), *pow5);
}
}
std::vector<unsigned short int> *convtmp = mult_bin_vec(*pow2, *pow5);
convtmp = mult_bin_vec(*convtmp, *tmp);
conv = sum_bin_vec(*conv, *convtmp);
}
n.clear();
for (int i = 0; i < conv->size(); i++)
n.push_back(conv->at(static_cast<unsigned long long int>(i)));
}
std::vector<unsigned short int> *decTobin(unsigned long long int cifra) {
auto *v = new std::vector<unsigned short int>{};
while (cifra >= 1) {
v->insert(v->begin(), static_cast<unsigned short &&>(cifra % 2));
cifra /= 2;
}
while (v->size() != VECPARTITION)
v->insert(v->begin(), 0);
return v;
}
std::vector<unsigned short int> *sum_bin_vec(std::vector<unsigned short int> &b1, std::vector<unsigned short int> &b2) {
auto *result = new std::vector<unsigned short int>{};
unsigned short int bit = 0;
unsigned short int bit_sum = 0;
while (b1.size() != b2.size())
b1.size() > b2.size() ? b2.insert(b2.begin(), 0) : b1.insert(b1.begin(), 0);
for (auto i = static_cast<int> (b1.size() - 1), j = static_cast<int>( b2.size()) - 1; i >= 0, j >= 0; i--, j--) {
bit_sum = b1.at(static_cast<unsigned long long int>(i)) + b2.at(static_cast<unsigned long long int>(j)) + bit;
if (bit_sum == 2) {
bit = 1;
bit_sum = 0;
} else if (bit_sum == 3) {
bit = 1;
bit_sum = 1;
} else {
bit = 0;
}
result->insert(result->begin(), bit_sum);
}
if (bit == 1)
result->insert(result->begin(), bit);
return result;
}
std::vector<unsigned short int> *
mult_bin_vec(std::vector<unsigned short int> &b1, std::vector<unsigned short int> &b2) {
auto *result = new std::vector<unsigned short int>{};
auto *sum = new std::vector<unsigned short int>{};
if (b1.size() > b2.size())
if ((abs(static_cast<int>((b1.size()) - (b2.size()))) % 2))
b1.insert(b1.begin(), 0);
if (b2.size() > b1.size())
if ((abs(static_cast<int>((b1.size()) - (b2.size()))) % 2))
b2.insert(b2.begin(), 0);
while (b1.size() != b2.size()) {
if (b1.size() > b2.size()) {
b2.insert(b2.begin(), 0);
} else if (b1.size() < b2.size()) {
b1.insert(b1.begin(), 0);
}
}
for (auto i = static_cast<int>(b2.size() - 1); i >= 0; i--) {
auto j = static_cast<int>(b1.size() - 1);
for (j; j >= 0; j--) {
sum->push_back(
b2.at(static_cast<unsigned long long int>(i)) * b1.at(static_cast<unsigned long long int>(j)));
}
}
int count = 0;
for (int i = 0, j = static_cast<int>(i + b1.size() - 1);
j < sum->size() - 1; i += b1.size() * 2, j += b1.size() * 2) {
std::vector<unsigned short int> *v = slice(*sum, i, j);
std::vector<unsigned short int> *w = slice(*sum, j + 1, static_cast<int>(j + b1.size()));
std::reverse(v->begin(), v->end());
std::reverse(w->begin(), w->end());
for (int k = 0; k < count; k += 2)
v->push_back(0);
for (int k = 0; k < count + 1; k += 2)
w->push_back(0);
result = sum_bin_vec(*sum_bin_vec(*v, *w), *result);
count += 4;
}
return result;
}
std::vector<unsigned short int> *stringTovec(const std::string &numstring) {
auto *vec = new std::vector<unsigned short int>{};
for (const char i : numstring)
vec->push_back(static_cast<unsigned short &&>(std::strtol(&i, nullptr, 0)));
return vec;
}