Implements a class for representing and manipulating large integers beyond the native integer range. More...

#include <big_integer.hpp>

Public Member Functions
std::string	to_string () const

template<std::integral T>
std::optional< T >	to () const

void	negate ()

BigInteger	abs () const

BigInteger	operator- () const

BigInteger	operator+ (const BigInteger &other) const

BigInteger	operator- (const BigInteger &other) const

BigInteger	operator* (const BigInteger &other) const

BigInteger	operator/ (const BigInteger &other) const

BigInteger &	operator+= (const BigInteger &other)

BigInteger &	operator-= (const BigInteger &other)

BigInteger &	operator*= (const BigInteger &other)

BigInteger &	operator/= (const BigInteger &other)

BigInteger	operator% (const BigInteger &other) const

std::pair< BigInteger, BigInteger >	divmod (const BigInteger &other) const

BigInteger &	operator++ ()

BigInteger	operator++ (int)

BigInteger &	operator-- ()

BigInteger	operator-- (int)

bool	operator== (const BigInteger &other) const

bool	operator!= (const BigInteger &other) const

bool	operator< (const BigInteger &other) const

bool	operator<= (const BigInteger &other) const

bool	operator> (const BigInteger &other) const

bool	operator>= (const BigInteger &other) const

void	multiplyByPowerOfTen (std::size_t power)

void	divideByPowerOfTen (std::size_t power)

Static Public Member Functions
static BigInteger	parse (const std::string &number)

template<std::integral T>
static BigInteger	from_integer (T number)

static const BigInteger &	zero ()

static const BigInteger &	one ()

static const BigInteger &	two ()

template<std::integral T>
static const BigInteger &	getMinValueInstance ()

template<std::integral T>
static const BigInteger &	getMaxValueInstance ()

static BigInteger	max (const BigInteger &a, const BigInteger &b)

static BigInteger	min (const BigInteger &a, const BigInteger &b)

static BigInteger	gcd (const BigInteger &a, const BigInteger &b)

static BigInteger	lcm (const BigInteger &a, const BigInteger &b)

static BigInteger	factorial (unsigned int n)

static BigInteger	pow (const BigInteger &a, unsigned int n)

static BigInteger	sqrt (const BigInteger &number)

static BigInteger	log2 (const BigInteger &number)

static BigInteger	log10 (const BigInteger &number)

Detailed Description

Implements a class for representing and manipulating large integers beyond the native integer range.

This class supports basic arithmetic operations, comparison, and conversion from/to strings and native integer types. It handles both positive and negative large integer values.

Member Function Documentation

◆ abs()

BigInteger hsc_snippets::BigInteger::abs ( ) const

inlinenodiscard

Calculates the absolute value of the BigInteger instance.

Returns: A new BigInteger representing the absolute value, with the negative flag turned off.

◆ divideByPowerOfTen()

void hsc_snippets::BigInteger::divideByPowerOfTen ( std::size_t power )

inline

Divides the BigInteger by a power of 10. This operation is optimized for base-10 representations and is performed by removing the specified number of least significant digits from the number. If the power exceeds the number of digits, the result is set to 0.

Parameters

power The exponent of 10 by which to divide the BigInteger. For example, a power of 2 means dividing the BigInteger by 100.

◆ divmod()

std::pair< BigInteger, BigInteger > hsc_snippets::BigInteger::divmod ( const BigInteger & other ) const

inlinenodiscard

Performs division and modulo operations simultaneously, returning both the quotient and the remainder.

This method divides this BigInteger by another BigInteger (divisor) and returns a pair consisting of the quotient and the remainder. It is more efficient than performing division and modulo operations separately. If the divisor is zero, the method throws a runtime error due to division by zero being undefined.

The remainder's sign is adjusted to match the divisor's sign, following the standard mathematical convention for division and modulus operations. This ensures that the remainder has the same sign as the divisor or is non-negative if the divisor is positive.

Parameters

other The divisor in the division and modulo operations.

Returns: A std::pair containing the quotient (first element) and the remainder (second element) of the division.

Exceptions

std::runtime_error If attempting division by zero in the divmod operation.

◆ factorial()

static BigInteger hsc_snippets::BigInteger::factorial ( unsigned int n )

inlinestatic

Calculates the factorial of a non-negative integer.

Parameters

n	The non-negative integer for which to compute the factorial.

Returns: The factorial of n as a BigInteger.

◆ from_integer()

template<std::integral T>

static BigInteger hsc_snippets::BigInteger::from_integer ( T number )

inlinestatic

Constructs a BigInteger from an integral type.

Template Parameters

T	The integral type of the input number.

Parameters

number The number to be converted to a BigInteger.

Returns: A BigInteger instance representing the input number.

◆ gcd()

static BigInteger hsc_snippets::BigInteger::gcd	(	const BigInteger &	a,
		const BigInteger &	b )

inlinestatic

Calculates the Greatest Common Divisor (GCD) of two BigInteger values using the Euclidean algorithm.

The Euclidean algorithm is based on the principle that the gcd of two numbers also divides their difference. This method repeatedly replaces the larger number by its difference with the smaller number until one of the numbers becomes zero. The non-zero number at this point is the gcd of the original two numbers.

Parameters

a	The first BigInteger for which to find the gcd.
b	The second BigInteger for which to find the gcd.

Returns: The gcd of BigInteger a and BigInteger b.

◆ getMaxValueInstance()

template<std::integral T>

static const BigInteger & hsc_snippets::BigInteger::getMaxValueInstance ( )

inlinestatic

Provides a singleton instance representing the maximum value of an integral type.

Template Parameters

T	The integral type for which the maximum value is requested.

Returns: A const reference to the BigInteger instance representing the maximum value of the integral type T.

◆ getMinValueInstance()

template<std::integral T>

static const BigInteger & hsc_snippets::BigInteger::getMinValueInstance ( )

inlinestatic

Provides a singleton instance representing the minimum value of an integral type.

Template Parameters

T	The integral type for which the minimum value is requested.

Returns: A const reference to the BigInteger instance representing the minimum value of the integral type T.

◆ lcm()

static BigInteger hsc_snippets::BigInteger::lcm	(	const BigInteger &	a,
		const BigInteger &	b )

inlinestatic

Calculates the Least Common Multiple (LCM) of two BigInteger values using the formula lcm(a, b) = |a * b| / gcd(a, b).

The lcm of two numbers is calculated using their gcd with the above formula. This works because the gcd of two numbers also divides their lcm. The method ensures the result is non-negative, as the lcm is defined as a non-negative value. In case both a and b are zero, the lcm is defined to be zero.

Parameters

a	The first BigInteger for which to find the lcm.
b	The second BigInteger for which to find the lcm.

Returns: The lcm of BigInteger a and BigInteger b.

◆ log10()

static BigInteger hsc_snippets::BigInteger::log10 ( const BigInteger & number )

inlinestatic

Calculates the base-10 logarithm of a BigInteger.

Parameters

number The BigInteger for which to calculate the base-10 logarithm.

Returns: An approximation of the base-10 logarithm of the given BigInteger, based on the number of digits.

Exceptions

std::out_of_range If the input is zero (log10(0) is undefined) or negative (log10 of a negative number is not allowed).

◆ log2()

static BigInteger hsc_snippets::BigInteger::log2 ( const BigInteger & number )

inlinestatic

Calculates the base-2 logarithm of a BigInteger.

Parameters

number The BigInteger for which to calculate the base-2 logarithm.

Returns: The base-2 logarithm of the given BigInteger.

Exceptions

std::out_of_range If the input is zero (log2(0) is undefined) or negative (log2 of a negative number is not allowed).

◆ max()

static BigInteger hsc_snippets::BigInteger::max	(	const BigInteger &	a,
		const BigInteger &	b )

inlinestatic

Determines the maximum of two BigInteger values.

Parameters

a	The first BigInteger to compare.
b	The second BigInteger to compare.

Returns: The larger of the two BigInteger values.

◆ min()

static BigInteger hsc_snippets::BigInteger::min	(	const BigInteger &	a,
		const BigInteger &	b )

inlinestatic

Determines the minimum of two BigInteger values.

Parameters

a	The first BigInteger to compare.
b	The second BigInteger to compare.

Returns: The smaller of the two BigInteger values.

◆ multiplyByPowerOfTen()

void hsc_snippets::BigInteger::multiplyByPowerOfTen ( std::size_t power )

inline

Multiplies the BigInteger by a power of 10. This operation is optimized for base-10 representations and is performed by simply adding the specified number of zeros to the least significant digits of the number.

Parameters

power The exponent of 10 by which to multiply the BigInteger. For example, a power of 3 means multiplying the BigInteger by 1000.

◆ negate()

void hsc_snippets::BigInteger::negate ( )

inline

◆ one()

static const BigInteger & hsc_snippets::BigInteger::one ( )

inlinestatic

Provides a singleton instance representing one.

Returns: A const reference to the BigInteger instance representing one.

◆ operator!=()

bool hsc_snippets::BigInteger::operator!= ( const BigInteger & other ) const

inline

◆ operator%()

BigInteger hsc_snippets::BigInteger::operator% ( const BigInteger & other ) const

inline

Calculates the remainder of division of this BigInteger by another BigInteger.

The modular operation follows the standard definition where the remainder of the division of this BigInteger (dividend) by the 'other' BigInteger (divisor) is returned. If the divisor is zero, the operation throws a runtime error due to division by zero being undefined.

Parameters

other The divisor in the modular operation.

Returns: The remainder after dividing this BigInteger by the 'other' BigInteger.

Exceptions

std::runtime_error If attempting to perform modulo by zero.

◆ operator*()

BigInteger hsc_snippets::BigInteger::operator* ( const BigInteger & other ) const

inline

Multiplies this BigInteger with another BigInteger.

The method uses a classic grade-school multiplication algorithm, where each digit of the first number is multiplied by each digit of the second number, and the intermediate results are added together, taking care of the carry at each step. The result is stored in a temporary vector which is large enough to hold the maximum possible number of digits (sum of the number of digits in both numbers).

Time Complexity: O(n*m), where n and m are the number of digits in the two numbers. This is because each digit of the first number is multiplied with each digit of the second number. Space Complexity: O(n + m), which is the size of the temporary vector used to store the intermediate results.

Parameters

other The BigInteger to multiply with this BigInteger.

Returns: The product of this BigInteger and the other BigInteger.

◆ operator*=()

BigInteger & hsc_snippets::BigInteger::operator*= ( const BigInteger & other )

inline

Multiplies the current BigInteger by another BigInteger and assigns the result to the current object.

Parameters

other The BigInteger to multiply with the current BigInteger.

Returns: A reference to the current BigInteger after multiplication.

◆ operator+()

BigInteger hsc_snippets::BigInteger::operator+ ( const BigInteger & other ) const

inline

Adds two BigInteger instances.

Parameters

other The BigInteger instance to add to the current instance.

Returns: The result of adding the current instance to the other instance.

◆ operator++() [1/2]

BigInteger & hsc_snippets::BigInteger::operator++ ( )

inline

◆ operator++() [2/2]

BigInteger hsc_snippets::BigInteger::operator++ ( int )

inline

◆ operator+=()

BigInteger & hsc_snippets::BigInteger::operator+= ( const BigInteger & other )

inline

Adds the value of another BigInteger to this instance and updates this instance with the result.

This operator modifies the current instance by adding the value of the specified BigInteger ('other') to it. The addition is performed using the existing addition logic defined in the class, which handles the arithmetic and any necessary carry operation. After the addition, the current instance is updated with the new value, making this operation in-place.

Parameters

other The BigInteger to add to this instance.

Returns: A reference to this instance after the addition.

◆ operator-() [1/2]

BigInteger hsc_snippets::BigInteger::operator- ( ) const

inline

◆ operator-() [2/2]

BigInteger hsc_snippets::BigInteger::operator- ( const BigInteger & other ) const

inline

Subtracts a BigInteger instance from the current instance.

Parameters

other The BigInteger instance to subtract from the current instance.

Returns: The result of subtracting the other instance from the current instance.

◆ operator--() [1/2]

BigInteger & hsc_snippets::BigInteger::operator-- ( )

inline

◆ operator--() [2/2]

BigInteger hsc_snippets::BigInteger::operator-- ( int )

inline

◆ operator-=()

BigInteger & hsc_snippets::BigInteger::operator-= ( const BigInteger & other )

inline

Subtracts the value of another BigInteger from this instance and updates this instance with the result.

This operator modifies the current instance by subtracting the value of the specified BigInteger ('other') from it. The subtraction is performed using the existing subtraction logic defined in the class, which handles the arithmetic and any necessary borrow operation. After the subtraction, the current instance is updated with the new value, making this operation in-place.

Parameters

other The BigInteger to subtract from this instance.

Returns: A reference to this instance after the subtraction.

◆ operator/()

BigInteger hsc_snippets::BigInteger::operator/ ( const BigInteger & other ) const

inline

Divides this BigInteger by another BigInteger and returns the quotient.

The method uses a long division approach where the dividend is divided by the divisor starting from the highest order of magnitude down to the lowest. At each step, the method finds how many times the divisor fits into the current portion of the dividend and subtracts the corresponding multiple of the divisor from the dividend. The quotient is built digit by digit from these multiples.

Time Complexity: For simplicity, let's denote this as O(d*(n-m)), where n is the number of digits in the dividend, m is the number of digits in the divisor, and d is the number of digits in the quotient. This accounts for the repeated subtraction of the divisor from portions of the dividend. Space Complexity: O(n), mainly for storing the quotient, where n is the number of digits in the dividend.

Parameters

other The BigInteger divisor.

Returns: The quotient of dividing this BigInteger by the other BigInteger.

Exceptions

std::runtime_error if attempted to divide by zero.

◆ operator/=()

BigInteger & hsc_snippets::BigInteger::operator/= ( const BigInteger & other )

inline

Divides the current BigInteger by another BigInteger and assigns the result to the current object.

Parameters

other The BigInteger to divide the current BigInteger by.

Returns: A reference to the current BigInteger after division.

◆ operator<()

bool hsc_snippets::BigInteger::operator< ( const BigInteger & other ) const

inline

◆ operator<=()

bool hsc_snippets::BigInteger::operator<= ( const BigInteger & other ) const

inline

◆ operator==()

bool hsc_snippets::BigInteger::operator== ( const BigInteger & other ) const

inline

◆ operator>()

bool hsc_snippets::BigInteger::operator> ( const BigInteger & other ) const

inline

◆ operator>=()

bool hsc_snippets::BigInteger::operator>= ( const BigInteger & other ) const

inline

◆ parse()

static BigInteger hsc_snippets::BigInteger::parse ( const std::string & number )

inlinestatic

Constructs a BigInteger from a string representation.

Parameters

number A string representing a potentially large integer.

Returns: A BigInteger instance corresponding to the input string.

Exceptions

std::invalid_argument If the string contains non-numeric characters (excluding an initial minus sign).

◆ pow()

static BigInteger hsc_snippets::BigInteger::pow	(	const BigInteger &	a,
		unsigned int	n )

inlinestatic

Computes a raised to the power of n using the fast powering algorithm.

Parameters

a	The base as a BigInteger.
n	The exponent as an unsigned integer.

Returns: The result of a^n as a BigInteger.

◆ sqrt()

static BigInteger hsc_snippets::BigInteger::sqrt ( const BigInteger & number )

inlinestatic

Calculates the square root of a BigInteger.

Parameters

number The BigInteger to find the square root of.

Returns: The square root of the given BigInteger.

Exceptions

std::runtime_error if the given BigInteger is negative.

◆ to()

template<std::integral T>

std::optional< T > hsc_snippets::BigInteger::to ( ) const

inline

Attempts to convert the BigInteger to a specified integral type T.

This method checks if the BigInteger's value fits within the range of the target type T. If the conversion is possible, the method returns an std::optional containing the converted value. If the conversion would lead to overflow, underflow, or if the BigInteger's value cannot be accurately represented by type T, the method returns std::nullopt.

Template Parameters

T	The target integral type for the conversion. Must satisfy std::integral.

Returns: An std::optional<T> containing the converted value if successful; otherwise, std::nullopt.

◆ to_string()

std::string hsc_snippets::BigInteger::to_string ( ) const

inlinenodiscard

Converts the BigInteger to its string representation.

Returns: A string representation of the BigInteger.

◆ two()

static const BigInteger & hsc_snippets::BigInteger::two ( )

inlinestatic

Provides a singleton instance representing two.

Returns: A const reference to the BigInteger instance representing two.

◆ zero()

static const BigInteger & hsc_snippets::BigInteger::zero ( )

inlinestatic

Provides a singleton instance representing zero.

Returns: A const reference to the BigInteger instance representing zero.

The documentation for this class was generated from the following file:

src/big_integer.hpp

Public Member Functions

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ abs()

◆ divideByPowerOfTen()

◆ divmod()

◆ factorial()

◆ from_integer()

◆ gcd()

◆ getMaxValueInstance()

◆ getMinValueInstance()

◆ lcm()

◆ log10()

◆ log2()

◆ max()

◆ min()

◆ multiplyByPowerOfTen()

◆ negate()

◆ one()

◆ operator!=()

◆ operator%()

◆ operator*()

◆ operator*=()

◆ operator+()

◆ operator++() [1/2]

◆ operator++() [2/2]

◆ operator+=()

◆ operator-() [1/2]

◆ operator-() [2/2]

◆ operator--() [1/2]

◆ operator--() [2/2]

◆ operator-=()

◆ operator/()

◆ operator/=()

◆ operator<()

◆ operator<=()

◆ operator==()

◆ operator>()

◆ operator>=()

◆ parse()

◆ pow()

◆ sqrt()

◆ to()

◆ to_string()

◆ two()

◆ zero()