Share via


Happy PI Day

Yesterday, I wanted to celebrate PI Day in my own way, so I wrote this little program during breakfast. Today, I investigated a bit and reduce the number of allocations: this version only does 9 buffer allocations to compute PI with 100 digits.

#include <iostream>
#include <memory>

using namespace std;

template<int count>
class BunchOfDigits {
    static const int MaxVal = 10000;
std::unique_ptr<int[]> _blocks;
int _first;

public:
BunchOfDigits(int val = 0)
      : _first(0), _blocks(new int[count + 1])
{
        _blocks[0] = val;
    for (int i = 1; i <= count; ++i) _blocks[i] = 0;
}

    BunchOfDigits(const BunchOfDigits& other)
: _first(other._first), _blocks(new int[count + 1])
{
        for (int i = 0; i <= count; i++) {
        _blocks[i] = other._blocks[i];
}
    }

    BunchOfDigits(BunchOfDigits&& other)
      : _first(other._first), _blocks(std::move(other._blocks))
    {
        other._blocks = nullptr;
}

    BunchOfDigits &BunchOfDigits::operator =(const BunchOfDigits& other)
{
        _first = other._first;
    _blocks.reset(new int[count + 1]);
    for (int i = 0; i <= count; i++) {
    _blocks[i] = other._blocks[i];
     }
        return *this;
}

    void Copy(const BunchOfDigits& other)
    {
        _first = other._first;
    for (int i = 0; i <= count; i++) {
    _blocks[i] = other._blocks[i];
}
    }

    BunchOfDigits& operator/=(const int val)
{
        int remainder = 0;
    for (int i = _first; i <= count; i++) {
    int dividend = remainder * MaxVal + _blocks[i];
        _blocks[i] = dividend / val;
        remainder = dividend % val;
}
        while ((_first <= count) && !_blocks[_first]) _first++;
    return *this;
}

    BunchOfDigits& operator*=(const int val)
{
        int carry = 0;
    for (int i = count; i >= _first; --i) {
    int n = _blocks[i] * val + carry;
            _blocks[i] = n % MaxVal;
carry = n / MaxVal;
}
        if ((carry > 0) && (_first > 0)) {
_blocks[--_first] = carry;
}
        return *this;
}
    BunchOfDigits& operator+=(const BunchOfDigits& val)
{
        int carry = 0;
int first = (_first < val._first) ? _first : val._first;
for (int i = count; i >= first; --i) {
int sum = _blocks[i] + val._blocks[i] + carry;
_blocks[i] = sum % BunchOfDigits::MaxVal;
carry = sum / BunchOfDigits::MaxVal;
}
        if ((carry > 0) && (_first > 0)) {
_blocks[--first] = carry;
}
        return *this;
    }

BunchOfDigits& operator-=(const BunchOfDigits& val)
{
        int carry = 0;
for (int i = count; i >= _first; --i) {
int n = _blocks[i];
int m = carry + val._blocks[i];
if (n < m) {
                n += MaxVal;
carry = 1;
            } else {
carry = 0;
}
_blocks[i] = n - m;
}
        while ((_first <= count) && !_blocks[_first]) {
++_first;
}
        return *this;
}

    bool IsZero() { return _first > count; }

    template<int count>
    friend std::ostream& operator<<(std::ostream& os, const BunchOfDigits<count>& obj);

};

template<int count>
BunchOfDigits<count> operator/(const BunchOfDigits<count>& left, int val)
{
    BunchOfDigits<count> ret = left;
    ret /= val;
    return ret;
}

template<int count>
BunchOfDigits<count> operator*(int val, const BunchOfDigits<count>& right)
{
    BunchOfDigits<count> ret = right;
    ret *= val;
    return ret;
}

template<int count>
BunchOfDigits<count> operator-(const BunchOfDigits<count>& left, const BunchOfDigits<count>& right)
{
    BunchOfDigits<count> ret = left;
    ret -= right;
    return ret;
}

template<int count>
std::ostream& operator<<(std::ostream& os, const BunchOfDigits<count>& val)
{
    os << val._blocks[0] << ".";
    for (int i = 1; i < count; i++) {
        int tmp = val._blocks[i] * 10;
        int max = 3;
        while (tmp < BunchOfDigits<count>::MaxVal && (max-- > 0)) {
            os << "0";
tmp *= 10;
}
        os << val._blocks[i];
}
    return os;
}

template<int count>
BunchOfDigits<count> Atan_1_over(int val)
{
    bool plus = true;
    int n = 1;
    BunchOfDigits<count> tmp(1);
    tmp /= val;
    BunchOfDigits<count> ret(tmp);
    BunchOfDigits<count> tmp2;
    while (!tmp.IsZero()) {
n +=2;
plus = !plus;
        tmp /= val;
        tmp /= val;
tmp2.Copy(tmp);
tmp2 /= n;
        if (plus) {
ret += tmp2;
} else {
ret -= tmp2;
}
}
    return ret;
}

int main(int argc, char* argv[])
{
    const int n = 26;
    BunchOfDigits<n> pi = 4 * (4 * Atan_1_over<n>(5) - Atan_1_over<n>(239));
    cout << "pi = " << pi << endl;
    return 0;
}