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


Comments (0)

Skip to main content