big_integer.hpp

Go to the documentation of this file.

#ifndef BIG_INTEGER_H
#define BIG_INTEGER_H
 
#include <ranges>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdint>
#include <concepts>
#include <optional>
#include <iostream>
#include <numeric>
 
namespace hsc_snippets {
    class BigInteger {
    private:
        std::vector<std::uint8_t> digits;
        bool isNegative = false;
 
        // Helper function to remove leading zeros
        void removeLeadingZeros() {
            while (digits.size() > 1 && digits.back() == 0) {
                digits.pop_back();
            }
            if (digits.size() == 1 && digits[0] == 0) {
                isNegative = false; // Ensure 0 is always positive
            }
        }
 
        [[nodiscard]] bool _isAbsoluteGreaterOrEqual(const BigInteger &other) const {
            if (digits.size() != other.digits.size()) {
                return digits.size() > other.digits.size();
            }
 
            for (int i = static_cast<int>(digits.size()) - 1; i >= 0; --i) {
                if (digits[i] != other.digits[i]) {
                    return digits[i] > other.digits[i];
                }
            }
 
            return true; // Equal in absolute value
        }
 
#pragma region private constructors
 
        BigInteger() = default;
 
        BigInteger(bool isNegative, const std::vector<std::uint8_t> &digits)
            : digits(digits), isNegative(isNegative) {
        }
 
#pragma endregion
 
#pragma region add&subtract
 
        [[nodiscard]] BigInteger _add(const BigInteger &other) const {
            BigInteger result;
            result.digits.clear(); // Ensure the result starts with an empty digit vector
 
            size_t maxLength = std::max(digits.size(), other.digits.size());
            int carry = 0;
 
            for (size_t i = 0; i < maxLength || carry; ++i) {
                int digitSum = carry;
 
                if (i < digits.size()) {
                    digitSum += digits[i];
                }
                if (i < other.digits.size()) {
                    digitSum += other.digits[i];
                }
 
                result.digits.push_back(digitSum % 10); // Store the single digit
                carry = digitSum / 10; // Calculate carry for the next digit
            }
 
            return result;
        }
 
        [[nodiscard]] BigInteger _subtract(const BigInteger &other) const {
            BigInteger result;
            result.digits.clear();
 
            int borrow = 0;
            for (size_t i = 0; i < digits.size(); ++i) {
                int digitSub = digits[i] - borrow - (i < other.digits.size() ? other.digits[i] : 0);
                borrow = 0;
 
                if (digitSub < 0) {
                    digitSub += 10;
                    borrow = 1;
                }
 
                result.digits.push_back(digitSub);
            }
 
            result.removeLeadingZeros(); // Defined previously to remove leading zeros
 
            return result;
        }
 
#pragma endregion
 
    public:
#pragma region conversion
 
        static BigInteger parse(const std::string &number) {
            BigInteger result;
            size_t start = 0;
 
            if (!number.empty() && number[0] == '-') {
                result.isNegative = true;
                start = 1;
            }
 
            for (size_t i = number.size(); i > start; --i) {
                char c = number[i - 1];
                if (c < '0' || c > '9') {
                    throw std::invalid_argument("Invalid character in number string.");
                }
                result.digits.push_back(c - '0');
            }
            result.removeLeadingZeros();
            return result;
        }
 
        template<std::integral T>
        static BigInteger from_integer(T number) {
            if (number == std::numeric_limits<T>::min()) {
                return BigInteger(getMinValueInstance<T>());
            }
 
            BigInteger result;
            if (number < 0) {
                result.isNegative = true;
                number = -number; // Make number positive for processing
            }
 
            do {
                result.digits.push_back(number % 10);
                number /= 10;
            } while (number > 0);
 
            return result;
        }
 
        [[nodiscard]] std::string to_string() const {
            if (digits.empty()) {
                return "0";
            }
 
            std::string str;
            if (isNegative) {
                str += '-';
            }
 
            str.reserve(digits.size() + str.size());
            for (unsigned char digit: std::ranges::reverse_view(digits)) {
                str += static_cast<char>('0' + digit);
            }
            return str;
        }
 
        template<std::integral T>
        std::optional<T> to() const {
            T result = 0;
            T multiplier = 1;
 
            if constexpr (!std::is_signed_v<T>) {
                if (isNegative) {
                    return std::nullopt;
                }
            }
 
            for (size_t i = 0; i < digits.size(); ++i) {
                T digitValue = static_cast<T>(digits[i]);
 
                // Check for potential overflow when adding the digit value
                T tempResult = result + digitValue * multiplier;
                if (tempResult < result) {
                    return std::nullopt; // Overflow occurred during addition
                }
                result = tempResult;
 
                // Check for potential overflow in the next multiplier
                if (i < digits.size() - 1) {
                    if (std::numeric_limits<T>::max() / 10 < multiplier) {
                        return std::nullopt; // Next multiplier would overflow
                    }
                    multiplier *= 10;
                }
            }
 
            if constexpr (std::is_signed_v<T>) {
                if (isNegative) {
                    if (result == 0 || result > std::numeric_limits<T>::max()) {
                        return std::nullopt; // Can't represent this negative value in T
                    }
                    result = -result; // Negate the result
                }
            }
 
            return result;
        }
 
#pragma endregion
 
#pragma region singletons
 
        static const BigInteger &zero() {
            static BigInteger zeroInstance(false, {0}); // Zero is not negative and has a single digit '0'
            return zeroInstance;
        }
 
        static const BigInteger &one() {
            static BigInteger oneInstance(false, {1}); // One is not negative and has a single digit '1'
            return oneInstance;
        }
 
        static const BigInteger &two() {
            static BigInteger twoInstance(false, {2}); // Two is not negative and has a single digit '2'
            return twoInstance;
        }
 
        template<std::integral T>
        static const BigInteger &getMinValueInstance() {
            static BigInteger minValue = []() -> BigInteger {
                if constexpr (std::is_signed_v<T>) {
                    T number = std::numeric_limits<T>::min();
                    BigInteger result;
                    result.isNegative = true;
 
                    // Special handling for the most negative number, which cannot be directly negated in signed types
                    if (number == std::numeric_limits<T>::min()) {
                        result.digits.push_back(-(number % 10));
                        number /= 10;
                        number = -number;
                    }
 
                    while (number > 0) {
                        result.digits.push_back(number % 10);
                        number /= 10;
                    }
 
                    return result;
                } else {
                    // For unsigned types, the minimum value is always 0
                    return BigInteger::zero();
                }
            }();
 
            return minValue;
        }
 
        template<std::integral T>
        static const BigInteger &getMaxValueInstance() {
            static BigInteger maxValue = []() -> BigInteger {
                T number = std::numeric_limits<T>::max();
                BigInteger result;
                result.isNegative = false;
 
                while (number > 0) {
                    result.digits.push_back(number % 10);
                    number /= 10;
                }
 
                return result;
            }();
 
            return maxValue; // Return a const reference to the singleton instance
        }
 
#pragma endregion
 
        // Negates the BigInteger instance.
        void negate() {
            if (digits.size() == 1 && digits[0] == 0) {
                // Zero remains non-negative
                isNegative = false;
            } else {
                isNegative = !isNegative;
            }
        }
 
        [[nodiscard]] BigInteger abs() const {
            BigInteger result = *this;
            result.isNegative = false; // Remove sign
            return result;
        }
 
 
        // Unary minus operator to return the negated value of the BigInteger instance.
        BigInteger operator-() const {
            BigInteger result = *this;
            result.negate();
            return result;
        }
 
 
#pragma region arithmetic
 
        BigInteger operator+(const BigInteger &other) const {
            BigInteger result;
 
            if (isNegative == other.isNegative) {
                result = _add(other);
                result.isNegative = isNegative; // Result will have the same sign
            } else {
                // Determine which number is greater in absolute value
                if (_isAbsoluteGreaterOrEqual(other)) {
                    result = _subtract(other);
                    result.isNegative = isNegative;
                } else {
                    result = other._subtract(*this);
                    result.isNegative = other.isNegative;
                }
            }
 
            result.removeLeadingZeros(); // Ensure there are no leading zeros
            if (result.digits.size() == 1 && result.digits[0] == 0) {
                result.isNegative = false; // Explicitly set the sign to non-negative for zero
            }
 
            return result;
        }
 
        BigInteger operator-(const BigInteger &other) const {
            BigInteger negatedOther = other;
            negatedOther.isNegative = !other.isNegative; // Negate the second operand
            return *this + negatedOther; // Use the + operator
        }
 
        BigInteger operator*(const BigInteger &other) const {
            // Check if either operand is zero
            if (*this == BigInteger::zero() || other == BigInteger::zero()) {
                return BigInteger::zero();
            }
 
            size_t totalLength = digits.size() + other.digits.size();
            BigInteger result;
            result.digits.resize(totalLength, 0); // Prepare the result vector with the appropriate size
 
            // Perform the multiplication algorithm
            for (size_t i = 0; i < digits.size(); ++i) {
                int carry = 0;
                for (size_t j = 0; j < other.digits.size() || carry; ++j) {
                    int product = carry + result.digits[i + j];
                    if (j < other.digits.size()) {
                        product += digits[i] * other.digits[j];
                    }
                    result.digits[i + j] = product % 10;
                    carry = product / 10;
                }
            }
 
            result.removeLeadingZeros(); // Ensure the result is correctly processed for leading zeros
            result.isNegative = isNegative != other.isNegative; // Determine the sign of the result
 
            return result;
        }
 
        BigInteger operator/(const BigInteger &other) const {
            if (other == BigInteger::zero()) {
                throw std::runtime_error("Division by zero");
            }
 
            BigInteger dividend = this->abs();
            BigInteger divisor = other.abs();
            BigInteger quotient;
            BigInteger current;
            quotient.digits.resize(dividend.digits.size(), 0);
 
            for (int i = static_cast<int>(dividend.digits.size()) - 1; i >= 0; --i) {
                current = current * BigInteger::from_integer(10) + BigInteger::from_integer(dividend.digits[i]);
                int count = 0;
                while (current >= divisor) {
                    current = current - divisor;
                    ++count;
                }
                quotient.digits[i] = count;
            }
 
            quotient.removeLeadingZeros(); // Remove any leading zeros
 
            // After calculating the quotient, if it is zero, its sign should be positive
            if (quotient == BigInteger::zero()) {
                quotient.isNegative = false;
            } else {
                // Otherwise, the sign of the quotient is determined by the signs of the operands
                quotient.isNegative = isNegative != other.isNegative;
            }
 
            return quotient;
        }
 
 
        BigInteger &operator+=(const BigInteger &other) {
            // Use the existing addition logic (_add method, or however addition is implemented in your class)
            *this = *this + other; // This line might change depending on how you've implemented addition internally
            return *this; // Return the current instance after modification
        }
 
        BigInteger &operator-=(const BigInteger &other) {
            // Use the existing subtraction logic (_subtract method, or however subtraction is implemented in your class)
            *this = *this - other; // This line might change depending on how you've implemented subtraction internally
            return *this; // Return the current instance after modification
        }
 
 
        BigInteger &operator*=(const BigInteger &other) {
            *this = *this * other;
            return *this;
        }
 
        BigInteger &operator/=(const BigInteger &other) {
            *this = *this / other;
            return *this;
        }
 
 
        BigInteger operator%(const BigInteger &other) const {
            if (other == BigInteger::zero()) {
                throw std::runtime_error("Modulo by zero");
            }
 
            BigInteger quotient = *this / other;
            BigInteger product = quotient * other;
            BigInteger remainder = *this - product;
 
            return remainder;
        }
 
#pragma endregion
 
        [[nodiscard]] std::pair<BigInteger, BigInteger> divmod(const BigInteger &other) const {
            if (other == BigInteger::zero()) {
                throw std::runtime_error("Modulo by zero");
            }
 
            BigInteger quotient = *this / other;
            BigInteger product = quotient * other;
            BigInteger remainder = *this - product;
 
            return std::make_pair(quotient, remainder);
        }
 
        static BigInteger max(const BigInteger &a, const BigInteger &b) {
            if (a.isNegative && !b.isNegative) return b; // a is negative, b is positive
            if (!a.isNegative && b.isNegative) return a; // a is positive, b is negative
 
            // Both are positive or negative
            if (a._isAbsoluteGreaterOrEqual(b))
                return a.isNegative ? b : a; // If both have same sign, return based on absolute value
            return a.isNegative ? a : b;
        }
 
        static BigInteger min(const BigInteger &a, const BigInteger &b) {
            if (a.isNegative && !b.isNegative) return a; // a is negative, b is positive
            if (!a.isNegative && b.isNegative) return b; // a is positive, b is negative
 
            // Both are positive or negative
            if (a._isAbsoluteGreaterOrEqual(b))
                return a.isNegative ? a : b; // If both have same sign, return based on absolute value
            return a.isNegative ? b : a;
        }
 
#pragma region increment & decrement
 
        // Prefix increment
        BigInteger &operator++() {
            *this = *this + BigInteger::one();
            return *this;
        }
 
        // Postfix increment
        BigInteger operator++(int) {
            BigInteger temp = *this;
            ++(*this); // Use prefix increment
            return temp;
        }
 
        // Prefix decrement
        BigInteger &operator--() {
            *this = *this - BigInteger::one();
            return *this;
        }
 
        // Postfix decrement
        BigInteger operator--(int) {
            BigInteger temp = *this;
            --(*this); // Use prefix decrement
            return temp;
        }
 
#pragma endregion
 
 
#pragma region comparators
 
        // Equality comparator
        bool operator==(const BigInteger &other) const {
            return isNegative == other.isNegative && digits == other.digits;
        }
 
        // Inequality comparator
        bool operator!=(const BigInteger &other) const {
            return !(*this == other);
        }
 
        // Less than comparator
        bool operator<(const BigInteger &other) const {
            if (isNegative != other.isNegative) {
                return isNegative; // If *this is negative and other is positive, *this is smaller
            }
 
            if (digits.size() != other.digits.size()) {
                return isNegative ? digits.size() > other.digits.size() : digits.size() < other.digits.size();
            }
 
            for (int i = static_cast<int>(digits.size()) - 1; i >= 0; --i) {
                if (digits[i] != other.digits[i]) {
                    return isNegative ? digits[i] > other.digits[i] : digits[i] < other.digits[i];
                }
            }
 
            return false; // Numbers are equal, so *this is not less than other
        }
 
        // Less than or equal comparator
        bool operator<=(const BigInteger &other) const {
            return *this == other || *this < other;
        }
 
        // Greater than comparator
        bool operator>(const BigInteger &other) const {
            return !(*this <= other);
        }
 
        // Greater than or equal comparator
        bool operator>=(const BigInteger &other) const {
            return !(*this < other);
        }
 
#pragma endregion
 
        static BigInteger gcd(const BigInteger &a, const BigInteger &b) {
            BigInteger zero = BigInteger::from_integer(0);
            BigInteger x = a.abs(); // Work with absolute values to ensure non-negativity
            BigInteger y = b.abs();
 
            while (y != zero) {
                BigInteger temp = y;
                y = x % y; // Replace y with the remainder of x divided by y
                x = temp; // Replace x with the old value of y
            }
 
            return x; // x contains the gcd when y becomes zero
        }
 
 
        static BigInteger lcm(const BigInteger &a, const BigInteger &b) {
            if (a == BigInteger::zero() && b == BigInteger::zero()) {
                return BigInteger::zero(); // LCM of zero and zero is defined as zero
            }
 
            BigInteger product = a * b; // Calculate the product of a and b
            BigInteger gcdValue = gcd(a, b); // Calculate the gcd of a and b
            BigInteger lcmValue = product / gcdValue; // Calculate the lcm using the product and gcd
 
            return lcmValue.abs(); // Ensure the lcm is non-negative
        }
 
        static BigInteger factorial(unsigned int n) {
            BigInteger result = BigInteger::from_integer(1); // Start with 1 as 0! = 1 and 1! = 1
 
            for (unsigned int i = 2; i <= n; ++i) {
                result = result * BigInteger::from_integer(i); // Multiply result by i for each step from 2 to n
            }
 
            return result;
        }
 
        static BigInteger pow(const BigInteger &a, unsigned int n) {
            if (n == 0) {
                return BigInteger::from_integer(1); // a^0 = 1 for any a
            }
 
            BigInteger result = BigInteger::from_integer(1);
            BigInteger base = a;
            while (n > 0) {
                if (n % 2 == 1) {
                    // If n is odd
                    result = result * base; // Multiply result by current base
                }
                base = base * base; // Square the base
                n /= 2; // Halve the exponent
            }
 
            return result;
        }
 
        static BigInteger sqrt(const BigInteger &number) {
            if (number.isNegative) {
                throw std::runtime_error("Square root of a negative number is not defined.");
            }
 
            if (number == zero() || number == one()) {
                return number;
            }
 
            BigInteger low = one();
            BigInteger high = number;
            BigInteger prev;
 
            while (low <= high) {
                BigInteger mid = (low + high) / two();
                BigInteger square = mid * mid;
 
                if (square == number) {
                    return mid;
                } else if (square < number) {
                    low = mid + one();
                    prev = mid;
                } else {
                    high = mid - one();
                }
            }
 
            return prev;
        }
 
 
        static BigInteger log2(const BigInteger &number) {
            if (number == BigInteger::zero()) {
                throw std::out_of_range("log2(0) is undefined");
            }
            if (number.isNegative) {
                throw std::out_of_range("log2(negative) is not allowed");
            }
 
            BigInteger logVal = BigInteger::from_integer(-1);
            BigInteger s = number;
            while (s != BigInteger::zero()) {
                logVal = logVal + BigInteger::one();
                s = s / BigInteger::two();
            }
            return logVal;
        }
 
        static BigInteger log10(const BigInteger &number) {
            if (number == BigInteger::zero()) {
                throw std::out_of_range("log10(0) is undefined");
            }
            if (number.isNegative) {
                throw std::out_of_range("log10(negative) is not allowed");
            }
 
            // log10 of a number is roughly the number of its digits minus 1
            return BigInteger::from_integer(number.digits.size() - 1);
        }
 
        void multiplyByPowerOfTen(std::size_t power) {
            if (*this == zero()) return; // 0 * 10^n = 0, no need to change anything
            digits.insert(digits.begin(), power, 0); // Insert 'power' number of zeros at the beginning
            removeLeadingZeros(); // Just in case there were leading zeros before
        }
 
        void divideByPowerOfTen(std::size_t power) {
            if (power >= digits.size()) {
                // If power is greater than or equal to the number of digits, the result is 0
                digits.clear();
                digits.push_back(0);
                isNegative = false; // Zero is not negative
            } else {
                // Erase 'power' number of digits from the beginning
                digits.erase(digits.begin(), digits.begin() + static_cast<int>(power));
            }
            removeLeadingZeros(); // Just in case leading zeros are created
        }
    };
}
 
#endif // BIG_INTEGER_H