Big.h

#ifndef BigFoot_Big_h
#define BigFoot_Big_h

#include <string>
#include <algorithm>

#include "TypeTraits.h"
#include "BigPrivate.h"

/** @brief BigFoot, aribitrary length integer library */
namespace BigFoot {

/**
@brief Class for storing integers with arbitrary length
@tparam T       Type for internal storage
*/
template<class T = int> class Big {
    public:
        typedef T Type; /**< @brief Type for internal storage */

        /**
         * @brief Construct the value from character sequence
         * @tparam base         Input base (see @c convert parameter)
         * @param value         String value
         * @param conver        Converter to use (as there is no way to
         *      explicitly call templated constructor, you can workaround it
         *      here by passing class instance, e.g. Convert<16>() for
         *      hexadecimal numbers)
         */
        template<size_t base = 10> Big(const std::string& value, Convert<base> convert = Convert<base>()): d(new BigPrivate<Type>(1)) {
            ++d->references;

            if(value.empty()) return;

            bool negate = false;
            size_t end = 1;
            if(value[0] == '-') negate = true;
            else if(value[0] != '+') end = 0;

            Big<Type> result;
            Big<Type> multiplier(1);
            for(size_t i = value.size(); i != end; --i) {
                char tmp = Convert<base>::from(value[i-1]);
                if(tmp == -1) return;
                result += tmp*multiplier;
                multiplier *= base;
            }

            delete d;
            d = result.d;
            result.d = 0;
            clean();
            if(negate) *this = -*this;
        }

        /** @brief Construct default (zero) value */
        inline Big(): d(new BigPrivate<Type>(1)) { ++d->references; }

        /** @brief Construct the value from storage type */
        Big(Type value) {
            typename TypeTraits<Type>::StorageType data(value);
            d = new BigPrivate<Type>(&data, 1);
            ++d->references;
        }

        /** @brief Construct the value from user type (wider than Type) */
        template<class U> Big(U value, typename std::enable_if<!std::is_pointer<U>::value && (sizeof(U) > sizeof(typename TypeTraits<Type>::StorageType))>::type* = 0) {
            size_t size = sizeof(U)/sizeof(typename TypeTraits<Type>::StorageType);
            typename TypeTraits<Type>::StorageType data[sizeof(U)/sizeof(typename TypeTraits<Type>::StorageType)];

            for(size_t i = 0; i != size; ++i) {
                data[i] = value & TypeTraits<Type>::mask;
                value >>= TypeTraits<Type>::bits;
            }

            d = new BigPrivate<Type>(data, size);
            ++d->references;
            clean();
        }

        /** @brief Copy constructor */
        Big(const Big<Type>& other) {
            d = other.d;
            ++d->references;
        }

        /** @brief Destructor */
        inline ~Big() { if(d && !--d->references) delete d; }

        /** @brief Assignment operator */
        Big<Type>& operator=(const Big<Type>& other) {
            if(d != other.d) {
                if(!--d->references) delete d;
                d = other.d;
                ++d->references;
            }
            return *this;
        }

        /**
         * @brief Value as character sequence
         * @tparam base     Output base
         */
        template<size_t base = 10> std::string value() const {
            std::string result;

            bool negate = *this < 0;
            Big<Type> tmp(*this < 0 ? -*this : *this);
            do {
                Type remainder;
                tmp = tmp.divideWithRemainder(base, &remainder);
                result.push_back(Convert<base>::to(remainder));
            } while(tmp != 0);

            if(negate) result.push_back('-');

            std::reverse(result.begin(), result.end());
            return result;
        }

        /** @{ @name Mathematical operators */

        /** @brief Positive value */
        inline Big<Type> operator+() const { return *this; }

        /** @brief Negative value */
        Big<Type> operator-() const {
            Big<Type> result;
            result.d->data.resize(d->data.size());

            /* Negate */
            for(size_t i = 0; i != d->data.size(); ++i)
                result.d->data[i] = ~d->data[i];

            /* Add 1 */
            return ++result;
        }

        /** @brief Addition */
        Big<Type> operator+(const Big<Type>& other_) const {
            /* Detach and extend smaller number to size of larger */
            Big<Type> result(other_.d->data.size() >= d->data.size() ? *this : other_);
            const Big<Type>& other(other_.d->data.size() >= d->data.size() ? other_ : *this);
            result.detach();
            result.signExtend(other.d->data.size());

            typename TypeTraits<Type>::ComputationType tmp(0);
            for(size_t i = 0; i != result.d->data.size()-1; ++i) {
                /* Add the numbers */
                tmp += static_cast<typename TypeTraits<Type>::ComputationType>(result.d->data[i]) +
                       static_cast<typename TypeTraits<Type>::ComputationType>(other.d->data[i]);

                /* Save (truncated) and take out the carry for next iteration */
                result.d->data[i] = tmp;
                tmp >>= TypeTraits<Type>::bits;
            }

            /* Last number with signed extension */
            tmp += static_cast<typename TypeTraits<Type>::ComputationType>(
                   static_cast<Type>(result.d->data.back())) +
                   static_cast<typename TypeTraits<Type>::ComputationType>(
                   static_cast<Type>(other.d->data.back()));

            result.d->data.back() = tmp;
            tmp >>= TypeTraits<Type>::bits;

            /* Add carry, if any, preserve signedness */
            if((*this < 0) == (other_ < 0) && ((tmp != TypeTraits<Type>::mask && tmp != 0) || (*this < 0) != (result < 0)))
                result.d->data.push_back(tmp);

            result.clean();
            return result;
        }

        /** @brief Addition assignment */
        inline Big<Type>& operator+=(const Big<Type>& other) {
            *this = operator+(other);
            return *this;
        }

        /** @brief Prefix increment */
        inline Big<Type>& operator++() { return operator+=(1); }

        /** @brief Postfix increment */
        inline Big<Type> operator++(int) {
            Big<Type> result(*this);
            operator+=(1);
            return result;
        }

        /** @brief Substraction */
        inline Big<Type> operator-(const Big<Type>& other) const {
            return operator+(-other);
        }

        /** @brief Substraction assignment */
        inline Big<Type>& operator-=(const Big<Type>& other) {
            return operator+=(-other);
        }

        /** @brief Prefix decrement */
        inline Big<Type>& operator--() { return operator-=(1); }

        /** @brief Postfix increment */
        inline Big<Type> operator--(int) {
            Big<Type> result(*this);
            operator-=(1);
            return result;
        }

        /** @brief Bitwise left shift */
        Big<Type> operator<<(size_t bits) const {
            Big<Type> result(*this);
            result.detach();

            /* Add elements to beginning of the vector */
            size_t count = bits/TypeTraits<Type>::bits;
            result.d->data.insert(result.d->data.begin(), count, 0);

            /* Move the bits */
            bits %= TypeTraits<Type>::bits;
            if(bits) {
                typename TypeTraits<Type>::StorageType tmp;
                typename TypeTraits<Type>::StorageType carry(0);
                for(size_t i = 0; i != result.d->data.size(); ++i) {
                    tmp = (result.d->data[i] << bits) | carry;
                    carry = result.d->data[i] >> (TypeTraits<Type>::bits-bits);
                    result.d->data[i] = tmp;
                }
                if(carry) result.d->data.push_back(carry);
            }

            return result;
        }

        /** @brief Bitwise left shift assignment */
        inline Big<Type>& operator<<=(size_t bits) {
            *this = operator<<(bits);
            return *this;
        }

        /** @brief Multiplication */
        Big<Type> operator*(const Big<Type>& other) const {
            bool negative = ((other >= 0) != (*this >= 0));
            Big<Type> a = *this < 0 ? -*this : *this;
            Big<Type> b = other < 0 ? -other : other;

            Big<Type> result;
            for(size_t oi = 0; oi != b.d->data.size(); ++oi) {
                Big<Type> part(new BigPrivate<Type>(a.d->data.size()));
                typename TypeTraits<Type>::ComputationType tmp(0);
                for(size_t i = 0; i != a.d->data.size(); ++i) {
                    /* Multiply the numbers */
                    tmp += static_cast<typename TypeTraits<Type>::ComputationType>(a.d->data[i]) *
                           static_cast<typename TypeTraits<Type>::ComputationType>(b.d->data[oi]);

                    /* Save and take out the carry for next iteration */
                    part.d->data[i] = tmp;
                    tmp >>= TypeTraits<Type>::bits;
                }

                /* Add carry, if any, preserve signedness */
                if((tmp != 0 && (tmp & TypeTraits<Type>::mask) != TypeTraits<Type>::mask) || part < 0)
                    part.d->data.push_back(tmp);

                result += (part << oi*TypeTraits<Type>::bits);
            }

            result.clean();
            return negative ? -result : result;
        }

        /** @brief Multiplication assignment */
        inline Big<Type> operator*=(const Big<Type>& other) {
            *this = operator*(other);
            return *this;
        }

        /** @brief Division (only with storage type) */
        Big<Type> operator/(Type divisor) const {
            Type remainder;
            return divideWithRemainder(divisor, &remainder);
        }

        /** @brief Division assignment (only with storage type) */
        Big<Type>& operator/=(Type divisor) {
            *this = operator/(divisor);
            return *this;
        }

        /** @brief Modulo (only with storage type) */
        Type operator%(Type divisor) {
            Type remainder;
            divideWithRemainder(divisor, &remainder);
            return remainder;
        }

        /*@}*/

        /** @{ @name Relational operators */

        /** @brief Equality */
        inline bool operator==(const Big<Type>& other) const {
            if(other.d->data.size() != d->data.size()) return false;

            for(size_t i = d->data.size(); i != 0; --i)
                if(d->data[i-1] != other.d->data[i-1])
                    return false;

            return true;
        }

        /** @brief Equal to */
        inline bool operator!=(const Big<Type>& other) const {
            return !operator==(other);
        }

        /** @brief Greater than or equal */
        inline bool operator>=(const Big<Type>& other) const {
            if((d->data.back() >> (TypeTraits<Type>::bits-1)) <
                (other.d->data.back() >> (TypeTraits<Type>::bits-1)))
                return true;
            if((d->data.back() >> (TypeTraits<Type>::bits-1)) >
                (other.d->data.back() >> (TypeTraits<Type>::bits-1)))
                return false;

            if(d->data.size() > other.d->data.size()) return true;
            if(d->data.size() < other.d->data.size()) return false;

            for(size_t i = d->data.size(); i != 0; --i)
                if(d->data[i-1] < other.d->data[i-1]) return false;

            return true;
        }

        /** @brief Greater than */
        inline bool operator>(const Big<Type>& other) const {
            return !operator<=(other);
        }

        /** @brief Less than or equal */
        inline bool operator<=(const Big<Type>& other) const {
            if((d->data.back() >> (TypeTraits<Type>::bits-1)) >
                (other.d->data.back() >> (TypeTraits<Type>::bits-1)))
                return true;
            if((d->data.back() >> (TypeTraits<Type>::bits-1)) <
                (other.d->data.back() >> (TypeTraits<Type>::bits-1)))
                return false;

            if(d->data.size() < other.d->data.size()) return true;
            if(d->data.size() > other.d->data.size()) return false;

            for(size_t i = d->data.size(); i != 0; --i)
                if(d->data[i-1] > other.d->data[i-1]) return false;

            return true;
        }

        /** @brief Less than */
        inline bool operator<(const Big<Type>& other) const {
            return !operator>=(other);
        }
        /*@}*/

    private:
        BigPrivate<Type>* d;    /**< @brief Private object */

        /** @brief Construct this object from given private object */
        inline explicit Big(BigPrivate<Type>* d): d(d) {
            ++d->references;
        }

        /** @brief Detach this object from all shared references */
        inline void detach() {
            if(d->references > 1) {
                --d->references;
                d = new BigPrivate<Type>(*d);
                d->references = 1;
            }
        }

        /**
         * @brief Value for extending the data
         *
         * Zeros for positive (unsigned data), ones for negative signed data.
         */
        inline typename TypeTraits<Type>::StorageType extensionValue() const {
            return (d->data.back() >> (TypeTraits<Type>::bits-1)) ? TypeTraits<Type>::mask : 0;
        }

        /** @brief Sign extend the data to given size */
        void signExtend(size_t size) {
            if(size == d->data.size()) return;
            detach();

            typename TypeTraits<Type>::StorageType value = extensionValue();

            for(size_t i = d->data.size(); i < size; ++i)
                d->data.push_back(value);
        }

        /** @brief Clean the number
         *
         * Removes unneeded items at the end (all zeros or all ones in
         * signed types).
         */
        void clean() {
            typename TypeTraits<Type>::StorageType value = extensionValue();

            /* nesmím když je kladné / neznaménkové a další odebrání by to zničilo */

            while(d->data.size() > 1 && d->data.back() == value) {
                /* Exit when another removal would change the sign */
                if((d->data[d->data.size() - 2] >> (TypeTraits<Type>::bits-1)) != (value & 1))
                    return;

                d->data.pop_back();
            }
        }

        /** @brief Division with remainder saving (only with storage type) */
        Big<Type> divideWithRemainder(Type divisor, Type* remainder) const {
            bool negative = (divisor >= 0) != (*this >= 0);
            Big<Type> a = *this < 0 ? -*this : *this;
            divisor = abs(divisor);

            Big<Type> result(new BigPrivate<Type>(a.d->data.size()));
            typename TypeTraits<Type>::ComputationType tmp(0);
            for(size_t i = a.d->data.size(); i != 0; --i) {
                tmp+=static_cast<typename TypeTraits<Type>::ComputationType>(a.d->data[i-1]);

                result.d->data[i-1] = tmp/static_cast<typename TypeTraits<Type>::ComputationType>(divisor);
                tmp = (tmp%divisor << TypeTraits<Type>::bits);
            }

            *remainder = tmp >> TypeTraits<Type>::bits;
            result.clean();
            return negative ? -result : result;
        }
};

#define outside_operator(op) \
    template<class T, class U> inline auto operator op(T a, const Big<U>& b) -> decltype(Big<U>(a).operator op(b)) { \
        return Big<U>(a) op b; \
    }
outside_operator(+)
outside_operator(-)
outside_operator(*)
outside_operator(==)
outside_operator(!=)
outside_operator(>=)
outside_operator(>)
outside_operator(<=)
outside_operator(<)
#undef outside_operator

template<class T> std::ostream& operator<<(std::ostream& out, const Big<T>& number) {
    return out << number.value();
}

template<class T> std::istream& operator>>(std::istream& in, Big<T>& number) {
    while(isspace(in.peek()))
        in.ignore();

    std::string value;
    while(in.peek() >= '0' && in.peek() <= '9')
        value.push_back(in.get());

    number = Big<T>(value);

    return in;
}

}

#endif

test.cpp

#include <cassert>

#include "Big.h"

using BigFoot::TypeTraits;

void testPow() {
    assert(BigFoot::pow(10, 0) == 1);
    assert(BigFoot::pow(2, 10) == 1024);
}

void testFac() {
    assert(BigFoot::fac(0) == 1);
    assert(BigFoot::fac(5) == 120);
}

void testFib() {
    assert(BigFoot::fib(0) == 0);
    assert(BigFoot::fib(1) == 1);
    assert(BigFoot::fib(11) == 89);
}

template<class T> void testBig() {
    typedef BigFoot::Big<T> BigInt;

    /* Create and compare */
    assert(BigInt(1234) == 1234);
    assert(BigInt(123456) != 123457);

    /* Comparing two positive */
    assert(!(BigInt(123456) >= 123457) && BigInt(123456) >= 123456 && BigInt(123456) >= 123455);
    assert(!(BigInt(123456) <= 123455) && BigInt(123456) <= 123456 && BigInt(123456) <= 123457);
    assert(BigInt(123456) > 123455 && !(BigInt(123456) > 123456) && !(BigInt(123456) > 123457));
    assert(!(BigInt(123456) < 123455) && !(BigInt(123456) < 123456) && BigInt(123456) < 123457);

    /* Comparing two negative */
    assert(BigInt(-123456) >= -123457 && BigInt(-123456) >= -123456 && !(BigInt(-123456) >= -123455));
    assert(BigInt(-123456) <= -123455 && BigInt(-123456) <= -123456 && !(BigInt(-123456) <= -123457));
    assert(!(BigInt(-123456) > -123455) && !(BigInt(-123456) > -123456) && BigInt(-123456) > -123457);
    assert(BigInt(-123456) < -123455 && !(BigInt(-123456) < -123456) && !(BigInt(-123456) < -123457));

    /* Comparing positive and negative */
    assert(BigInt(123456) >= BigInt(-123456) && !(BigInt(-123456) >= BigInt(123456)));
    assert(BigInt(-123456) <= BigInt(123456) && !(BigInt(123456) <= BigInt(-123456)));
    assert(BigInt(123456) > BigInt(-123456) && !(BigInt(-123456) > BigInt(123456)));
    assert(BigInt(-123456) < BigInt(123456) && !(BigInt(123456) < BigInt(-123456)));

    /* Comparing negative to zero */
    assert(BigInt(T(0)) >= -123456 && !(BigInt(-123456) >= 0));
    assert(BigInt(-123456) <= 0 && !(BigInt(T(0)) <= -123456));
    assert(BigInt(T(0)) > -123456 && !(BigInt(-123456) > 0));
    assert(BigInt(-123456) < 0 && !(BigInt(T(0)) < -123456));

    /* Autoclean */
    assert(BigInt(TypeTraits<typename BigInt::Type>::mask) > 0);
    assert(BigInt(-1 & ~TypeTraits<typename BigInt::Type>::mask) < 0);

    /* Copy and assign */
    BigInt source(123456);
    BigInt destination(source);
    destination = 0;
    assert(source == 123456);
    destination = source;
    source = 123455;
    assert(destination == 123456);

    /* Add */
    BigInt a(123456);
    BigInt b(1);
    assert(a + b == 123457);
    assert(a == 123456 && b == 1);

    /* Preserve signedness */
    assert(BigInt(1ul << (TypeTraits<typename BigInt::Type>::bits-2)) +
           BigInt(1ul << (TypeTraits<typename BigInt::Type>::bits-2)) > 0);
    assert(BigInt(static_cast<typename BigInt::Type>(1ul << (TypeTraits<typename BigInt::Type>::bits-1))) +
           BigInt(static_cast<typename BigInt::Type>(1ul << (TypeTraits<typename BigInt::Type>::bits-1))) < 0);

    /* Overflow */
    assert(BigInt(TypeTraits<typename BigInt::Type>::mask) + TypeTraits<typename BigInt::Type>::mask == TypeTraits<typename BigInt::Type>::mask*2);

    /* Substract */
    assert(a - b == 123455);
    assert(123456 - b == 123455 && a - 1 == 123455);
    assert(a == 123456 && b == 1);
    assert((BigInt(0xFFF) + 123456) - 2*123456 ==
            BigInt(0xFFF) - 123456);

    /* Increment/decrement */
    BigInt prefix(123455);
    BigInt postfix(prefix);
    assert(++prefix == 123456);
    assert(postfix++ == 123455 && postfix == 123456);
    assert(--prefix == 123455);
    assert(postfix-- == 123456 && postfix == 123455);

    /* Negative values */
    assert(-BigInt(123456) == -123456);
    assert(-(-BigInt(123456)) == 123456);
    assert(123456 - BigInt(0xFFF) == -(BigInt(0xFFF-123456)));

    /* Multiplication */
    assert(BigInt(123456)*123456 == 123456ll*123456ll);
    assert(BigInt(123456)*-123456 == -123456ll*123456ll);
    assert(BigInt(-123456)*123456 == -123456ll*123456ll);
    assert(BigInt(-123456)*-123456 == 123456ll*123456ll);

    /* Left shift (multiplication depends on it, but it cannot be tested
       without multiplication, so it is after it */
    assert(BigInt(1) << TypeTraits<typename BigInt::Type>::bits == pow(BigInt(2), TypeTraits<typename BigInt::Type>::bits));
    assert(BigInt(TypeTraits<typename BigInt::Type>::mask) << 1 == BigInt(TypeTraits<typename BigInt::Type>::mask)*2);

    /* Create from string */
    assert(BigInt("123456") == 123456);
    assert(BigInt("-123456") == -123456);
    assert(BigInt("666", BigFoot::Convert<8>()) == 0666);
    assert(BigInt("Cafe8abe", BigFoot::Convert<16>()) == 0xcafe8abel);

    /* Division */
    assert(BigInt(2)/2 == 1);
    assert(BigInt(123456)/96 == 1286);

    /* Save to string */
    assert(BigInt().value() == "0");
    assert(BigInt(123456).value() == "123456");
    assert(BigInt(-123456).value() == "-123456");
    assert(BigInt(0666).template value<8>() == "666");
    assert(BigInt(0xcafe8abel).template value<16>() == "cafe8abe");
}

int main(int argc, char** argv) {
    testPow();
    testFac();
    testFib();

    testBig<char>();
    testBig<short>();
    testBig<int>();
    #ifdef GCC_128BIT_INTEGER
    testBig<long long>();
    #endif

    return 0;
}