La mia riscrittura usando i template:
- Codice:
#include <iostream>
#include <cstdint>
#include <chrono>
#include <string>
#include <vector>
using namespace std;
using namespace std::chrono;
template < typename NumberRepType >
NumberRepType
addition( const NumberRepType& n1, const NumberRepType& n2 )
{
const uint32_t S1 = size( n1 );
const uint32_t S2 = size( n2 );
const uint32_t SM = max( S1, S2 );
NumberRepType n3;
n3.reserve( SM + 1 ); // reserve representation size
uint32_t n = 0;
for ( uint32_t i = 0; i < SM; ++i )
{
if ( i < S1 )
{
n += ( n1[ i ] - '0' );
}
if ( i < S2 )
{
n += ( n2[ i ] - '0' );
}
n3.push_back( static_cast< uint8_t >( ( n % 10 ) + '0' ) );
n /= 10;
}
if ( n > 0 )
{
n3.push_back( '1' );
}
return n3;
}
template < typename NumberRepType >
NumberRepType
multiplication( const NumberRepType& n1, const NumberRepType& n2 )
{
const uint32_t S1 = size( n1 );
const uint32_t S2 = size( n2 );
NumberRepType n3;
n3.reserve( ( S1 * S2 ) + 1 );
NumberRepType temp;
for ( uint32_t i = 0; i < S1; ++i )
{
temp.clear( );
uint32_t n = 0;
for ( uint32_t j = 0; j < i; ++j )
{
temp.push_back( '0' );
}
for ( uint32_t j = 0; j < S2; ++j )
{
n += ( n1[ i ] - '0' ) * ( n2[ j ] - '0' );
temp.push_back( n % 10 + '0' );
}
n /= 10;
if ( n > 0 )
{
temp.push_back( n + '0' );
}
n3 = addition< NumberRepType >( n3, temp );
}
return n3;
}
int
main( )
{
cout << "calcolo di 12345^1000 (versione string): ";
string a = "54321";
string b = "1";
auto start1 = high_resolution_clock::now( );
for ( unsigned int i = 0; i < 1000; ++i )
{
b = multiplication( a, b );
}
auto stop1 = high_resolution_clock::now( );
auto duration1 = duration_cast< milliseconds >( stop1 - start1 );
cout << duration1.count( ) << " ms" << endl;
//-----------------------------------------------------------
cout << "calcolo di 12345^1000 (versione vector): ";
vector< uint8_t > c = {5, 4, 3, 2, 1};
vector< uint8_t > d = {1};
auto start2 = high_resolution_clock::now( );
for ( unsigned int i = 0; i < 1000; ++i )
{
d = multiplication( c, d );
}
auto stop2 = high_resolution_clock::now( );
auto duration2 = duration_cast< milliseconds >( stop2 - start2 );
cout << duration2.count( ) << " ms" << endl;
}