Benchmark for Adding Big Integers

Readme.md

BigInteger library

Compile the program

$ g++ -std=c++17 main.cpp -Ofast -o biginteger_benchmark

Run it with 1'000'000 digits

Download the big-number generating script NumGen from https://sourceforge.net/projects/specter-aal/

$ # generate numbers with 1'000'000 digits
$ ./NumGen
...
--- Done ---
$ ls -sh MyNum
2,0M MyNum
$ # run benchmark
$ ./biginteger_benchmark < MyNum
...9999999999999999999999999999999998
Computation of z took 0.327ms
digits(x) = 1000000
digits(y) = 1000000
digits(z) = 1000001

Run it with 100'000'000 digits

Modify the number of repeats in the script NumGen from 100 to 10000. Then repeat:

$ # generate numbers with 1'000'000 digits
$ ./NumGen
...
--- Done ---
$ ls -sh MyNum
191M MyNum
$ # run benchmark
$ ./biginteger_benchmark < MyNum
...9999999999999999999999999999999998
Computation of z took 66.7ms
digits(x) = 100000000
digits(y) = 100000000
digits(z) = 100000001

main.cpp

#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

constexpr int power(int x, int e) { return e ? x * power(x, e - 1) : 1; }

class BigInteger {
public:
  BigInteger(long long x = 0) {
    if (x > 0)
      sign = 1;
    else if (x == 0)
      sign = 0;
    else
      sign = -1;
    x *= sign;

    while (x) {
      data.push_back(x % BASE);
      x /= BASE;
    }
  }

  BigInteger &add(BigInteger const &o, int o_sign) {
    if (sign == o_sign) {
      data.resize(std::max(data.size(), o.data.size()) + 1, 0);
      int carry = 0;
      for (auto i = 0u; i < data.size(); i++) {
        if (i < o.data.size())
          carry += o.data[i];
        carry += data[i];

        data[i] = carry % BASE;
        carry /= BASE;
      }
    } else if (o_sign == 0) {
      // nothing
    } else if (sign == 0) {
      sign = o_sign;
      data = o.data;
    } else {
      int cmp = compare_abs(o);
      data.resize(std::max(data.size(), o.data.size()) + 1, 0);
      if (cmp == 0) {
        sign = 0;
        data.clear();
      } else if (cmp == 1) {
        int carry = 0;
        for (auto i = 0u; i < data.size(); i++) {
          carry += data[i];
          if (i < o.data.size())
            carry -= o.data[i];

          if (carry < 0) {
            carry += BASE;
            data[i] = carry;
            carry = 1;
          } else {
            data[i] = carry;
            carry = 0;
          }
        }
      } else {
        int carry = 0;
        for (auto i = 0u; i < data.size(); i++) {
          if (i < o.data.size())
            carry += o.data[i];
          carry -= data[i];

          if (carry < 0) {
            carry += BASE;
            data[i] = carry;
            carry = 1;
          } else {
            data[i] = carry;
            carry = 0;
          }
        }
        sign = o_sign;
      }
    }

    pop_zeros();
    return *this;
  }

  BigInteger &operator+=(BigInteger const &o) { return add(o, o.sign); }

  BigInteger operator+(BigInteger const &o) const {
    BigInteger t = *this;
    t += o;
    return t;
  }

  BigInteger &operator-=(BigInteger const &o) {
    if (o.sign)
      return add(o, -o.sign);
    return *this;
  }

  BigInteger operator-(BigInteger const &o) const {
    BigInteger t = *this;
    t -= o;
    return t;
  }

  void pop_zeros() {
    while (!data.empty() && data.back() == 0)
      data.pop_back();
  }

  unsigned int digits() const {
    if (data.empty())
      return 0;
    unsigned int d = (data.size() - 1) * DIGITS;
    int x = data.back();
    while (x > 0) {
      d++;
      x /= 10;
    }
    return d;
  }

  int compare_abs(BigInteger const &o) const {
    if (data.size() != o.data.size())
      return data.size() < o.data.size() ? -1 : 1;
    for (int i = data.size() - 1; i >= 0; i--) {
      if (data[i] != o.data[i])
        return data[i] < o.data[i] ? -1 : 1;
    }
    return 0;
  }

  friend std::ostream &operator<<(std::ostream &stream, BigInteger const &b) {
    if (b.data.empty()) {
      stream << 0;
    } else {
      if (b.sign == -1)
        stream << '-';
      stream << b.data.back();
      for (int i = b.data.size() - 2; i >= 0; i--) {
        stream.width(DIGITS);
        stream.fill('0');
        stream << b.data[i];
      }
    }
    return stream;
  }

  friend std::istream &operator>>(std::istream &is, BigInteger &b) {
    std::string s;
    is >> s;
    if (s.back() == ':')
      s.pop_back();
    int start = 0;
    if (s == "0") {
      b.sign = 0;
      b.data.clear();
    } else {
      if (s[0] == '-') {
        b.sign = -1;
        start++;
      } else {
        b.sign = 1;
      }
      b.data.resize((s.size() - start + DIGITS - 1) / DIGITS);
      for (int i = 0, idx = s.size() - 1; i < (int)b.data.size();
           i++, idx -= DIGITS) {
        int value = 0;
        for (int j = std::max(start, idx - DIGITS + 1); j <= idx; j++)
          value = value * 10 + s[j] - '0';
        b.data[i] = value;
      }
    }
    return is;
  }

private:
  static const int DIGITS = 9;
  static const int BASE = power(10, DIGITS);

  int sign;
  std::vector<int> data;
};

int main() {
  BigInteger x, y;
  cin >> x >> y;
  auto t1 = chrono::high_resolution_clock::now();
  auto z = x + y;
  auto t2 = chrono::high_resolution_clock::now();

  cout << "x = " << x << endl;
  cout << "y = " << y << endl;
  cout << "z = " << z << endl;
  cout << "Computation of z took " << setprecision(3)
       << chrono::duration_cast<chrono::microseconds>(t2 - t1).count() / 1'000.0
       << "ms" << endl;
  cout << "digits(x) = " << x.digits() << endl;
  cout << "digits(y) = " << y.digits() << endl;
  cout << "digits(z) = " << z.digits() << endl;
}