U

#### Udit Sharma

I am a newbie as far as C++ is concerned. I am just reading books like

Effective C++ and More Effective C++. So kindly bear with me if I have

made some very stupid mistake.

I have read in books that it is always better to use vectors rather

than arrays and that there is no performance hit and also that your

code would be more safe to use when using vectors.

I had to write a small program to compute the sum of digits in a

factorial of a number (<= 10000). I have written two versions: one

using vectors, and one using plain arrays.

But I notice a stark difference in execution times. The program using

arrays runs in about 0.309 seconds (to compute sum of digits in

10000!) while the one using vectors takes about 2.9 seconds to finish

the same. I compiled both on an Ubuntu 9.1 Linux machine running using

gcc 4.4.1 and at optimization level 3.

I have listed both the programs here. Kindly tell me if the problem is

with the way I have written the code or something else.

//Program using arrays

#include <iostream>

int main() {

unsigned int factorial = 0;

std::cout << "Enter number : ";

std::cin >> factorial;

const unsigned MAXDIGITS = 10000, BASE = 10000;

unsigned indDigits[MAXDIGITS]; //This is the array that am

talking about

indDigits[0] = 1;

unsigned int counter = 0, oanda = 0, size = 0;

for(unsigned facts = 1; facts <= factorial; facts++) {

for (unsigned index = counter; index <= size; index++){

oanda += facts * indDigits[index];

indDigits[index] = oanda%BASE;

if(index == counter && !((oanda > 0) && (oanda != BASE)))

counter++;

oanda /= BASE;

}

if(oanda)

indDigits[++size]=oanda;

}

unsigned sumDigits = 0;

for (unsigned i = 0; i <= size; i++){

for(unsigned j = 1; j <= BASE/10; j*=10)

sumDigits += (indDigits

*/j)%10;*

}

std::cout << "Sum of Digits: " << sumDigits << std::endl;

}

//Same Program using vectors

#include <iostream>

#include <vector>

typedef std::vector<unsigned> Vec;

typedef std::vector<unsigned>::iterator Iter;

int main() {

unsigned int factorial = 0;

std::cout << "Enter number : ";

std::cin >> factorial;

const unsigned BASE = 10000;

Vec indDigits; //This is the vector that am talking about

indDigits.push_back(1);

unsigned int counter = 0, oanda = 0, size = 0;

for(unsigned facts = 1; facts <= factorial; facts++) {

oanda = 0;

for(Iter iter = indDigits.begin() + counter; iter !=

indDigits.end(); iter++){

oanda += facts * (*iter);

*iter = oanda%BASE;

if((iter == indDigits.begin() + counter) && !((oanda > 0)

&& (oanda != BASE)))

counter++;

oanda /= BASE;

}

if(oanda)

indDigits.push_back(oanda);

}

unsigned sumDigits = 0;

for (Iter iter = indDigits.begin(); iter != indDigits.end(); iter+

+){

for(unsigned j = 1; j <= BASE/10; j*=10)

sumDigits += ((*iter)/j)%10;

}

std::cout << "Sum of Digits: " << sumDigits << std::endl;

}

Thanks in advance.

Cheers

Udit

}

std::cout << "Sum of Digits: " << sumDigits << std::endl;

}

//Same Program using vectors

#include <iostream>

#include <vector>

typedef std::vector<unsigned> Vec;

typedef std::vector<unsigned>::iterator Iter;

int main() {

unsigned int factorial = 0;

std::cout << "Enter number : ";

std::cin >> factorial;

const unsigned BASE = 10000;

Vec indDigits; //This is the vector that am talking about

indDigits.push_back(1);

unsigned int counter = 0, oanda = 0, size = 0;

for(unsigned facts = 1; facts <= factorial; facts++) {

oanda = 0;

for(Iter iter = indDigits.begin() + counter; iter !=

indDigits.end(); iter++){

oanda += facts * (*iter);

*iter = oanda%BASE;

if((iter == indDigits.begin() + counter) && !((oanda > 0)

&& (oanda != BASE)))

counter++;

oanda /= BASE;

}

if(oanda)

indDigits.push_back(oanda);

}

unsigned sumDigits = 0;

for (Iter iter = indDigits.begin(); iter != indDigits.end(); iter+

+){

for(unsigned j = 1; j <= BASE/10; j*=10)

sumDigits += ((*iter)/j)%10;

}

std::cout << "Sum of Digits: " << sumDigits << std::endl;

}

Thanks in advance.

Cheers

Udit