HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Multiplying and Adding Large Numbers

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewcppstackoverflowc++number-systems
multiplyingnumbersaddinglargeand

Problem

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 LargeNumber(int number) {
    std::vector 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 addition(std::vector max, std::vector min) {
    if (max.size()  sum;
    int rest = 0;    

    for (int i = 0; i  0) {
        sum.push_back(rest % 10);
        rest /= 10;
    }

    return sum;
}


// Multiplying large numbers
std::vector multiplication(std::vector max, std::vector min) {
    if (max.size() > sums;
    std::vector sum;
    for (int i = 0; i  0) {
            sum.push_back(0);
            n--;
        }
        int rest = 0;
        for (int j = 0; j  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 
int main () {
    // Calculating the factorial of the number N
    int N = 100;
    std::vector fac;
    sum.push_back(1);
    for (int i = 2; i = 0; i--) {
        std::cout << fac[i];
    } std::cout << std::endl; 
}


Since I am ve

Solution

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 (+, -, /, *,



  • 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. You can have one, but a std::complex 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 

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 
#include 

class Bignum
{
    static constexpr char max_digit = 100;

    std::vector 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
#include 
#include 

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;
    };
}

Code Snippets

#include <bignum>

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

    std::cout << "100! = " << fac << std::endl;
}
#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;
    };
}

Context

StackExchange Code Review Q#158256, answer score: 5

Revisions (0)

No revisions yet.