Multiplying and Adding Large Numbers

Lately, I've been working on the Euler projects. I just started coding in C++ and could really use some feedback. Basically, I wrote a program to calculate the factorial of any number between 1 and 100 (I have not tested it above 100).

I looked into the Boost library, but it seemed a little bit to easy, so I wrote some algorithms on my own.

Anyway, I would really like some comments about whether this is efficient or not, and if I can somehow optimize the algorithms? I hope this post is within the scope of the forum, since it is my first.

I first convert two integers to vectors, storing each digit separately:

// Converting number to vector
std::vector<int> LargeNumber(int number) {
std::vector<int> numbers;
while (number > 0) {
numbers.push_back(number % 10);
number /= 10;
}
return numbers;
}

Then I pass the vectors on to one of these two functions, depending on whether I want to add or multiply:

// Adds large numbers
std::vector<int> addition(std::vector<int> max, std::vector<int> min) {
if (max.size() < min.size()) {
max.swap(min);
}
std::vector<int> sum;
int rest = 0;

for (int i = 0; i < min.size(); i++) {
int c = min[i] + max[i] + rest;
sum.push_back(c % 10);
rest = c / 10;
}

for (int i = min.size(); i < max.size(); i++) {
int c = max[i] + rest;
sum.push_back(c % 10);
rest = c / 10;
}
while (rest > 0) {
sum.push_back(rest % 10);
rest /= 10;
}

return sum;
}

// Multiplying large numbers
std::vector<int> multiplication(std::vector<int> max, std::vector<int> min) {
if (max.size() < min.size()) {
max.swap(min);
}

std::vector<std::vector<int>> sums;
std::vector<int> sum;
for (int i = 0; i < min.size(); i++) {
sum.resize(0);
int n = i;
while (n > 0) {
sum.push_back(0);
n--;
}
int rest = 0;
for (int j = 0; j < max.size(); j++) {
int c = max[j] * min[i] + rest;
sum.push_back(c % 10);
rest = c / 10;
}
while (rest > 0) {
sum.push_back(rest % 10);
rest /= 10;
}
sums.push_back(sum);
}
sum.resize(0);

for (int i = 0; i < sums.size(); i++) {
sum = addition(sum, sums[i]);
}
return sum;
}

I can then calculate the factorial as:

#include <vector>
int main () {
// Calculating the factorial of the number N
int N = 100;
std::vector<int> fac;
sum.push_back(1);
for (int i = 2; i <= N; i++) {
fac = multiplication(sum, LargeNumber(i));
}
// Printing the result
std::cout << "The factorial of " << N << ": " <<  std::endl;
for (int i = sum.size()-1; i >= 0; i--) {
std::cout << fac[i];
} std::cout << std::endl;
}

Since I am very new to C++, it is hard for me to know what exactly to ask for, so any comment is very welcome.

• Your LargeNumber won't work on zero – Incomputable Mar 20 '17 at 10:31

It's really worth making your big number be a class. This will give you the ability to

• change the internal representation without altering client code
• write operators (+, -, /, *, <, ==, << and more) that work just like they do for other numbers
• specialize numeric limits and other traits classes so they can be used as arithmetic types in algorithms. For example, you might like a std::complex<BigNum>. You can have one, but a std::complex<std::vector<int>> isn't going to work.
• add literal operators so that you can write them naturally in your source code.

You don't have to do all the above at once, of course. But I recommend you read the review of Implementation of a Rational Number class in C++ to see how an arithmetic class can work.

Your main() would then be isolated from the implementation details, and look something like

#include <bignum>

int main () {
int N = 100;
auto fac = 1_big;
do {
fac *= N;
} while (--N > 0);

std::cout << "100! = " << fac << std::endl;
}

Space efficiency

Once you have your class, you'll observe that writing one digit in each int is quite wasteful. char is defined to include at least 0 to 127 so you could store two digits (0 to 100) in each element of a vector of characters.

If you've made your big number a class, it's then easier to do this in two steps - first store one digit in each character, and then widen to 2 per char. There are more space-efficient encodings; you'll have to decide where the trade-off between space and time lies for your needs.

Temporary values in multiplication

In your long multiplication, you store all the intermediate results before adding them together. You can save some of this space by using an accumulator variable to add the results as you go, like this pseudo-code:

accumulator = 0
for i in digits
tmp = arg1 * i
accumulator += tmp
return accumulator

Then you no longer need to have a vector of partial products throughout the function.

Working example

Here's what I implemented, following the notes above. It's the absolute minimum needed to calculate factorials. Several features are left as an exercise:

• Implement a user-defined literal that accepts longer numbers than unsigned long long can represent
• Support negative numbers
• Implement the other arithmetic and relational operators
• Make more of the implementation constexpr so it can be evaluated during compilation
#include <vector>
#include <iosfwd>

class Bignum
{
static constexpr char max_digit = 100;

std::vector<char> digits = {};   // smallest centits first

public:
Bignum(unsigned long long int n)
{
while (n) {
digits.push_back(n % max_digit);
n /= max_digit;
}
}
// copy constructor and assignment operator can be defaulted

Bignum& operator+=(const Bignum& other);
Bignum operator+(const Bignum& other) const;

Bignum& operator*=(const Bignum& other);

friend std::ostream& operator<<(std::ostream&, const Bignum&);

private:
// helper functions
Bignum& halve();
Bignum& trim();
};

Bignum operator""_big(unsigned long long n) { return n; }

// IMPLEMENTATION

#include <algorithm>
#include <iostream>
#include <utility>

Bignum& Bignum::operator+=(const Bignum& other)
{
int sum = 0;
auto i = digits.begin();
auto j = other.digits.begin();
bool in = true;             // until i reaches digits.end()
bool jn = true;
while ((in &= i != digits.end()) | (jn &= j != other.digits.end()) || sum) {
if (jn)
sum += *j++;
if (in) {
sum += *i;
*i++ = sum % max_digit;
} else {
digits.push_back(sum % max_digit);
}
sum /= max_digit;       // carry to next digit
}
return *this;
}

Bignum Bignum::operator+(const Bignum& other) const
{
return Bignum{*this} += other;
}

Bignum& Bignum::operator*=(const Bignum& other)
{
Bignum a = *this, b = other;
if (a.digits.size() > b.digits.size())
std::swap(a, b);

digits.clear();
while (a.digits.size() > 0) {
if (a.digits.front() % 2)
*this += b;
a.halve();
b += b;
}
return *this;
}

Bignum& Bignum::halve()
{
int carry = 0;
for (auto i = digits.rbegin();  i != digits.rend();  ++i) {
carry *= max_digit;
carry += *i;
*i = carry / 2;
carry = carry % 2;
}
return trim();
}

Bignum& Bignum::trim()
{
while (digits.size() > 0 && !digits.back())
digits.pop_back();
return *this;
}

std::ostream& operator<<(std::ostream& out, const Bignum& n)
{
if (n.digits.size() == 0)
return out << '0';

bool z = false;             // track leading zeros
for (auto i = n.digits.rbegin();  i != n.digits.rend();  ++i) {
int n = *i;
if (z |= n/10)
out << n/10;
if (z |= n)
out << n % 10;
}

return out;
}

// PROGRAM

int main () {
const int N = 100;
auto fac = 1_big;

for (int i = 1;  i < N;  ++i) {
fac *= i;
std::cout << i << "! = " << fac << std::endl;
};
}