uint128_t UnitClassFile
unknown
c_cpp
a year ago
28 kB
4
Indexable
#include "UnsignedInteger128Bit.hpp" namespace TwilightDream::WideIntegers { const uint128_t uint128_0( 0 ); const uint128_t uint128_1( 1 ); uint128_t::uint128_t( const std::string& characters, uint8_t base ) { from_string( characters.c_str(), characters.size(), base ); } uint128_t::uint128_t( const char* characters, const std::size_t size, uint8_t base ) { from_string( characters, size, base ); } uint128_t::uint128_t( const bool& b ) : uint128_t( ( uint8_t )b ) {} uint128_t::~uint128_t() { this->high_bits = ZERO_BITS; this->low_bits = ZERO_BITS; } void uint128_t::from_string( const char* characters, std::size_t size, uint8_t base ) { if ( ( characters == nullptr ) || !size || ( characters[ 0 ] == '\x00' ) ) { low_bits = high_bits = 0; return; } while ( *characters && size && std::isspace( *characters ) ) { ++characters; size--; } // no prefixes switch ( base ) { case 16: _initialize_with_hexadecimal( characters, size ); break; case 10: _initialize_with_decimal( characters, size ); break; case 8: _initialize_with_octal( characters, size ); break; case 2: _initialize_with_binary( characters, size ); break; default: throw std::invalid_argument(""); break; } } void uint128_t::_initialize_with_hexadecimal( const char* characters, std::size_t len ) { // 2**128 = 0x100000000000000000000000000000000. static const std::size_t MAX_SIZE = 32; low_bits = high_bits = 0; if ( !characters || !len ) { return; } const std::size_t max_size = std::min( len, MAX_SIZE ); const std::size_t starting_index = ( MAX_SIZE < len ) ? ( len - MAX_SIZE ) : 0; const std::size_t double_lower = sizeof( low_bits ) * 2; const std::size_t lower_size = ( max_size >= double_lower ) ? double_lower : max_size; const std::size_t upper_size = ( max_size >= double_lower ) ? ( max_size - double_lower ) : 0; std::stringstream lower_s, upper_s; upper_s << std::hex << std::string( characters + starting_index, upper_size ); lower_s << std::hex << std::string( characters + starting_index + upper_size, lower_size ); // should check for errors upper_s >> high_bits; lower_s >> low_bits; } void uint128_t::_initialize_with_decimal( const char* characters, std::size_t size ) { // 2**128 = 340282366920938463463374607431768211456. static const std::size_t MAX_SIZE = 39; low_bits = high_bits = 0; if ( !characters || !size ) { return; } const std::size_t max_size = std::min( size, MAX_SIZE ); const std::size_t starting_index = ( MAX_SIZE < size ) ? ( size - MAX_SIZE ) : 0; characters += starting_index; for ( std::size_t i = 0; *characters && ( '0' <= *characters ) && ( *characters <= '9' ) && ( i < max_size ); ++characters, ++i ) { *this *= 10; *this += *characters - '0'; } } void uint128_t::_initialize_with_octal( const char* characters, std::size_t size ) { // 2**128 = 0o4000000000000000000000000000000000000000000. static const std::size_t MAX_SIZE = 43; low_bits = high_bits = 0; if ( !characters || !size ) { return; } const std::size_t max_size = std::min( size, MAX_SIZE ); const std::size_t starting_index = ( MAX_SIZE < size ) ? ( size - MAX_SIZE ) : 0; characters += starting_index; for ( std::size_t i = 0; *characters && ( '0' <= *characters ) && ( *characters <= '7' ) && ( i < max_size ); ++characters, ++i ) { *this *= 8; *this += *characters - '0'; } } void uint128_t::_initialize_with_binary( const char* characters, std::size_t size ) { // 2**128 = 0b100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000. static const std::size_t MAX_SIZE = 128; low_bits = high_bits = 0; if ( !characters || !size ) { return; } const std::size_t max_size = std::min( size, MAX_SIZE ); const std::size_t starting_index = ( MAX_SIZE < size ) ? ( size - MAX_SIZE ) : 0; const std::size_t eight_lower = sizeof( low_bits ) * 8; const std::size_t lower_size = ( max_size >= eight_lower ) ? eight_lower : max_size; const std::size_t upper_size = ( max_size >= eight_lower ) ? ( max_size - eight_lower ) : 0; characters += starting_index; for ( std::size_t i = 0; *characters && ( '0' <= *characters ) && ( *characters <= '1' ) && ( i < upper_size ); ++characters, ++i ) { high_bits <<= 1; high_bits |= *characters - '0'; } for ( std::size_t i = 0; *characters && ( '0' <= *characters ) && ( *characters <= '1' ) && ( i < lower_size ); ++characters, ++i ) { low_bits <<= 1; low_bits |= *characters - '0'; } } uint128_t& uint128_t::operator=( const bool& other ) { high_bits = 0; low_bits = other; return *this; } void uint128_t::import_bytes( const std::vector<uint8_t>& bytes ) { size_t byte_counter = 0; std::size_t byte_amount = std::min( bytes.size(), (size_t)16 ); auto ConvertFromVector = [&byte_counter, byte_amount](const std::vector<uint8_t>& bytes, uint64_t& value) -> void { value = 0; while( byte_counter < byte_amount ) { value <<= 8; value |= bytes[byte_counter]; byte_counter++; } }; ConvertFromVector(bytes, high_bits); ConvertFromVector(bytes, low_bits); } void uint128_t::export_bytes( std::vector<uint8_t>& bytes ) const { auto ConvertToVector = [](std::vector<uint8_t> & result, const uint64_t& value) -> void { result.push_back(static_cast<uint8_t>(value >> 56)); result.push_back(static_cast<uint8_t>(value >> 48)); result.push_back(static_cast<uint8_t>(value >> 40)); result.push_back(static_cast<uint8_t>(value >> 32)); result.push_back(static_cast<uint8_t>(value >> 24)); result.push_back(static_cast<uint8_t>(value >> 16)); result.push_back(static_cast<uint8_t>(value >> 8)); result.push_back(static_cast<uint8_t>(value)); }; ConvertToVector(bytes, high_bits); ConvertToVector(bytes, low_bits); } uint128_t::operator bool() const { return ( bool )( high_bits | low_bits ); } uint128_t::operator uint8_t() const { return ( uint8_t )low_bits; } uint128_t::operator uint16_t() const { return ( uint16_t )low_bits; } uint128_t::operator uint32_t() const { return ( uint32_t )low_bits; } uint128_t::operator uint64_t() const { return ( uint64_t )low_bits; } /* Basic bit manipulation function (BMF) */ // Check if all bits are set bool uint128_t::check_all_bits() const { if ( this->high_bits == ONE_BITS && this->low_bits == ONE_BITS ) { return true; } return false; } // Check if any bits are set bool uint128_t::check_any_bit() const { if ( this->high_bits != ZERO_BITS || this->low_bits != ZERO_BITS ) { return true; } return false; } // Check if no bits are set bool uint128_t::check_none_bits() const { if ( this->high_bits == ZERO_BITS && this->low_bits == ZERO_BITS ) { return true; } return false; } void uint128_t::swap( uint128_t& other ) { std::swap( this->high_bits, other.high_bits ); std::swap( this->low_bits, other.low_bits ); } void uint128_t::change_all_bits( bool value ) { this->high_bits = value ? ONE_BITS : ZERO_BITS; this->low_bits = value ? ONE_BITS : ZERO_BITS; } void uint128_t::change_high_bits( uint64_t value ) { this->high_bits = value; } void uint128_t::change_low_bits( uint64_t value ) { this->low_bits = value; } void uint128_t::set_bit( size_t position, bool value ) { if ( position >= BITS_SIZE ) { return; } if ( position >= BITS_SIZE_HALF ) { if ( value ) { this->high_bits |= ( BIT_ONE << ( position - BITS_SIZE_HALF ) ); } else { this->high_bits &= ~( BIT_ONE << ( position - BITS_SIZE_HALF ) ); } } else { if ( value ) { this->low_bits |= ( BIT_ONE << position ); } else { this->low_bits &= ~( BIT_ONE << position ); } } } bool uint128_t::get_bit( size_t position ) { if ( position >= BITS_SIZE ) { return false; } if ( position >= BITS_SIZE_HALF ) { return ( this->high_bits & ( BIT_ONE << ( position - BITS_SIZE_HALF ) ) ) != ZERO_BITS; } else { return ( this->low_bits & ( BIT_ONE << position ) ) != ZERO_BITS; } } void uint128_t::bit_not_xor( const uint128_t& other ) { this->high_bits ^= ~other.high_bits; this->low_bits ^= ~other.low_bits; } void uint128_t::bit_not_and( const uint128_t& other ) { this->high_bits &= ~other.high_bits; this->low_bits &= ~other.low_bits; } void uint128_t::bit_not_xor( uint64_t other ) { this->low_bits ^= ~other; } void uint128_t::bit_not_and( uint64_t other ) { this->low_bits &= ~other; } /* Logical Operators */ bool uint128_t::operator!() const { return !( bool )( high_bits | low_bits ); } bool uint128_t::operator&&( const uint128_t& other ) const { return ( ( bool )*this && other ); } bool uint128_t::operator||( const uint128_t& other ) const { return ( ( bool )*this || other ); } /* Comparison Operators */ bool uint128_t::operator==( const uint128_t& other ) const { return ( ( high_bits == other.high_bits ) && ( low_bits == other.low_bits ) ); } bool uint128_t::operator!=( const uint128_t& other ) const { return ( ( high_bits != other.high_bits ) || ( low_bits != other.low_bits ) ); } bool uint128_t::operator>( const uint128_t& other ) const { if ( high_bits == other.high_bits ) { return ( low_bits > other.low_bits ); } return ( high_bits > other.high_bits ); } bool uint128_t::operator<( const uint128_t& other ) const { if ( high_bits == other.high_bits ) { return ( low_bits < other.low_bits ); } return ( high_bits < other.high_bits ); } bool uint128_t::operator>=( const uint128_t& other ) const { return !( *this < other ); } bool uint128_t::operator<=( const uint128_t& other ) const { return !( *this > other ); } /* Internal helper functions */ uint64_t uint128_t::population_count() const { uint64_t low_population_count = low_bits; uint64_t high_population_count = high_bits; auto population_count_64bit = [ &low_population_count, &high_population_count ]() -> uint64_t { low_population_count -= ( low_population_count >> 1 ) & 0x5555555555555555; low_population_count = ( low_population_count & 0x3333333333333333 ) + ( ( low_population_count >> 2 ) & 0x3333333333333333 ); low_population_count = ( low_population_count + ( low_population_count >> 4 ) ) & 0x0f0f0f0f0f0f0f0f; low_population_count = ( low_population_count * 0x0101010101010101 ) >> 56; high_population_count -= ( high_population_count >> 1 ) & 0x5555555555555555; high_population_count = ( high_population_count & 0x3333333333333333 ) + ( ( high_population_count >> 2 ) & 0x3333333333333333 ); high_population_count = ( high_population_count + ( high_population_count >> 4 ) ) & 0x0f0f0f0f0f0f0f0f; high_population_count = ( high_population_count * 0x0101010101010101 ) >> 56; return low_population_count + high_population_count; }; return population_count_64bit(); } uint32_t uint128_t::counter_one_bits_from_left() const { uint32_t result = 0; if ( this->high_bits ) { result = 64; uint64_t high = this->high_bits; //For each bit with high bits while ( high ) { high >>= 1; result++; } } else { uint64_t low = this->low_bits; while ( low ) { low >>= 1; result++; } } return result; } /* Binary bitwise operator */ uint128_t uint128_t::operator&( const uint128_t& other ) const { return uint128_t( high_bits & other.high_bits, low_bits & other.low_bits ); } uint128_t& uint128_t::operator&=( const uint128_t& other ) { high_bits &= other.high_bits; low_bits &= other.low_bits; return *this; } uint128_t uint128_t::operator|( const uint128_t& other ) const { return uint128_t( high_bits | other.high_bits, low_bits | other.low_bits ); } uint128_t& uint128_t::operator|=( const uint128_t& other ) { high_bits |= other.high_bits; low_bits |= other.low_bits; return *this; } uint128_t uint128_t::operator^( const uint128_t& other ) const { return uint128_t( high_bits ^ other.high_bits, low_bits ^ other.low_bits ); } uint128_t& uint128_t::operator^=( const uint128_t& other ) { high_bits ^= other.high_bits; low_bits ^= other.low_bits; return *this; } uint128_t uint128_t::operator~() const { return uint128_t( ~high_bits, ~low_bits ); } uint128_t uint128_t::operator<<( const uint128_t& shift_amount ) const { const uint64_t shift = shift_amount.low_bits; if ( ( ( bool )shift_amount.high_bits ) || ( shift >= BITS_SIZE ) ) { return uint128_0; } else if ( shift == BITS_SIZE_HALF ) { return uint128_t( low_bits, BIT_ZERO ); } else if ( shift == 0 ) { return *this; } else if ( shift < BITS_SIZE_HALF ) { return uint128_t( ( high_bits << shift ) + ( low_bits >> ( BITS_SIZE_HALF - shift ) ), low_bits << shift ); } else if ( ( BITS_SIZE > shift ) && ( shift > BITS_SIZE_HALF ) ) { return uint128_t( low_bits << ( shift - BITS_SIZE_HALF ), BIT_ZERO ); } else { return uint128_0; } } uint128_t& uint128_t::operator<<=( const uint128_t& shift_amount ) { *this = *this << shift_amount; return *this; } uint128_t uint128_t::operator>>( const uint128_t& shift_amount ) const { const uint64_t shift = shift_amount.low_bits; if ( ( ( bool )shift_amount.high_bits ) || ( shift >= BITS_SIZE ) ) { return uint128_0; } else if ( shift == BITS_SIZE_HALF ) { return uint128_t( BIT_ZERO, high_bits ); } else if ( shift == 0 ) { return *this; } else if ( shift < BITS_SIZE_HALF ) { return uint128_t( high_bits >> shift, ( high_bits << ( BITS_SIZE_HALF - shift ) ) + ( low_bits >> shift ) ); } else if ( ( BITS_SIZE > shift ) && ( shift > BITS_SIZE_HALF ) ) { return uint128_t( BIT_ZERO, ( high_bits >> ( shift - BITS_SIZE_HALF ) ) ); } else { return uint128_0; } } uint128_t& uint128_t::operator>>=( const uint128_t& shift_amount ) { *this = *this >> shift_amount; return *this; } uint128_t operator<<( const bool& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator<<( const uint8_t& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator<<( const uint16_t& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator<<( const uint32_t& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator<<( const uint64_t& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator<<( const int8_t& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator<<( const int16_t& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator<<( const int32_t& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator<<( const int64_t& self, const uint128_t& other ) { return uint128_t( self ) << other; } uint128_t operator>>( const bool& self, const uint128_t& other ) { return uint128_t( self ) >> other; } uint128_t operator>>( const uint8_t& self, const uint128_t& other ) { return uint128_t( self ) >> other; } uint128_t operator>>( const uint16_t& self, const uint128_t& other ) { return uint128_t( self ) >> other; } uint128_t operator>>( const uint32_t& self, const uint128_t& other ) { return uint128_t( self ) >> other; } uint128_t operator>>( const uint64_t& self, const uint128_t& other ) { return uint128_t( self ) >> other; } uint128_t operator>>( const int8_t& self, const uint128_t& other ) { return uint128_t( self ) >> other; } uint128_t operator>>( const int16_t& self, const uint128_t& other ) { return uint128_t( self ) >> other; } uint128_t operator>>( const int32_t& self, const uint128_t& other ) { return uint128_t( self ) >> other; } uint128_t operator>>( const int64_t& self, const uint128_t& other ) { return uint128_t( self ) >> other; } /* Arithmetic Operators */ uint128_t uint128_t::operator+( const uint128_t& other ) const { return uint128_t( high_bits + other.high_bits + ( ( low_bits + other.low_bits ) < low_bits ), low_bits + other.low_bits ); } uint128_t& uint128_t::operator+=( const uint128_t& other ) { high_bits += other.high_bits + ( ( low_bits + other.low_bits ) < low_bits ); low_bits += other.low_bits; return *this; } uint128_t uint128_t::operator-( const uint128_t& other ) const { return uint128_t( high_bits - other.high_bits - ( ( low_bits - other.low_bits ) > low_bits ), low_bits - other.low_bits ); } uint128_t& uint128_t::operator-=( const uint128_t& other ) { *this = *this - other; return *this; } uint128_t& uint128_t::operator++() { return *this += uint128_1; } uint128_t uint128_t::operator++( int ) { uint128_t temp( *this ); ++*this; return temp; } uint128_t& uint128_t::operator--() { return *this -= uint128_1; } uint128_t uint128_t::operator--( int ) { uint128_t temp( *this ); --*this; return temp; } uint128_t uint128_t::operator+() const{ return *this; } uint128_t uint128_t::operator-() const{ return ~*this + uint128_1; } uint128_t uint128_t::operator*( const uint128_t& other ) const { return multiplication( *this, other ); } uint128_t& uint128_t::operator*=( const uint128_t& other ) { *this = *this * other; return *this; } uint128_t uint128_t::operator/( const uint128_t& other ) const { return division( *this, other ).first; } uint128_t& uint128_t::operator/=( const uint128_t& other ) { *this = *this / other; return *this; } uint128_t uint128_t::operator%( const uint128_t& other ) const { return division( *this, other ).second; } uint128_t& uint128_t::operator%=( const uint128_t& other ) { *this = *this % other; return *this; } /* Internal implementation of arithmetic operations */ uint128_t uint128_t::multiplication( const uint128_t& multiplied, const uint128_t& multiplier ) const { // Karatsuba algorithm constexpr uint64_t bit_mask = ( ONE_BITS >> BITS_SIZE_QUARTER ); // split values into 4 32-bit parts uint64_t top[ 4 ] = { multiplied.high_bits >> BITS_SIZE_QUARTER, multiplied.high_bits & bit_mask, multiplied.low_bits >> BITS_SIZE_QUARTER, multiplied.low_bits & bit_mask }; uint64_t bottom[ 4 ] = { multiplier.high_bits >> BITS_SIZE_QUARTER, multiplier.high_bits & bit_mask, multiplier.low_bits >> BITS_SIZE_QUARTER, multiplier.low_bits & bit_mask }; uint64_t products[ 4 ][ 4 ]; // multiply each component of the values for ( int y = 3; y > -1; y-- ) { for ( int x = 3; x > -1; x-- ) { products[ 3 - x ][ y ] = top[ x ] * bottom[ y ]; } } // first row uint64_t fourth32 = ( products[ 0 ][ 3 ] & bit_mask ); uint64_t third32 = ( products[ 0 ][ 2 ] & bit_mask ) + ( products[ 0 ][ 3 ] >> BITS_SIZE_QUARTER ); uint64_t second32 = ( products[ 0 ][ 1 ] & bit_mask ) + ( products[ 0 ][ 2 ] >> BITS_SIZE_QUARTER ); uint64_t first32 = ( products[ 0 ][ 0 ] & bit_mask ) + ( products[ 0 ][ 1 ] >> BITS_SIZE_QUARTER ); // second row third32 += ( products[ 1 ][ 3 ] & bit_mask ); second32 += ( products[ 1 ][ 2 ] & bit_mask ) + ( products[ 1 ][ 3 ] >> BITS_SIZE_QUARTER ); first32 += ( products[ 1 ][ 1 ] & bit_mask ) + ( products[ 1 ][ 2 ] >> BITS_SIZE_QUARTER ); // third row second32 += ( products[ 2 ][ 3 ] & bit_mask ); first32 += ( products[ 2 ][ 2 ] & bit_mask ) + ( products[ 2 ][ 3 ] >> BITS_SIZE_QUARTER ); // fourth row first32 += ( products[ 3 ][ 3 ] & bit_mask ); // move carry to next digit third32 += fourth32 >> BITS_SIZE_QUARTER; second32 += third32 >> BITS_SIZE_QUARTER; first32 += second32 >> BITS_SIZE_QUARTER; // remove carry from current digit fourth32 &= bit_mask; third32 &= bit_mask; second32 &= bit_mask; first32 &= bit_mask; // combine components return uint128_t( ( first32 << BITS_SIZE_QUARTER ) | second32, ( third32 << BITS_SIZE_QUARTER ) | fourth32 ); } std::pair<uint128_t, uint128_t> uint128_t::division( const uint128_t& dividend, const uint128_t& divisor ) const { // Check for division by zero if ( divisor == uint128_0 ) { throw std::runtime_error( "Division by zero" ); } // If the divisor is 1, the quotient is the dividend and the remainder is 0 if ( divisor == uint128_1 ) { return std::pair<uint128_t, uint128_t>( dividend, uint128_0 ); } // If the dividend is 1, the quotient is 0 and the remainder is the 1 if ( dividend == uint128_1 ) { return std::pair<uint128_t, uint128_t>( uint128_0, uint128_1 ); } //If the dividend equal to divisor if ( dividend == divisor ) { return std::pair<uint128_t, uint128_t>( uint128_1, uint128_0 ); } // If the dividend is 0, the quotient and remainder are both 0 if ( ( dividend == uint128_0 ) || ( dividend < divisor ) ) { return std::pair<uint128_t, uint128_t>( uint128_0, dividend ); } std::pair<uint128_t, uint128_t> quotient_and_remainder( uint128_0, uint128_0 ); for ( uint32_t bit_size = dividend.counter_one_bits_from_left(); bit_size > 0; bit_size-- ) { quotient_and_remainder.first <<= uint128_1; quotient_and_remainder.second <<= uint128_1; if ( ( dividend >> ( bit_size - BIT_ONE ) ) & 1 ) { ++quotient_and_remainder.second; } if ( quotient_and_remainder.second >= divisor ) { quotient_and_remainder.second -= divisor; ++quotient_and_remainder.first; } } return quotient_and_remainder; } //The bit position of the highest valid bit. uint32_t uint128_t::get_most_significant_bit_index() const { if ( this->high_bits ) { //For each bit with high bits for ( int index = BITS_SIZE - 1; index >= BITS_SIZE_HALF; index-- ) { if ( this->high_bits & ( BIT_ONE << index ) ) { return index + BITS_SIZE_HALF; } } } else { //For each bit with low bits for ( int index = BITS_SIZE_HALF - 1; index >= 0; index-- ) { if ( this->low_bits & ( BIT_ONE << index ) ) { return index; } } } } uint64_t& uint128_t::operator[]( size_t index ) { index %= 2; if(index) return this->low_bits; else return this->high_bits; } // Donald Knuth's multi-precision unsigned integer division // Implement the algorithm in Knuth[The Art of Computer Programming] Book // https://raw.githubusercontent.com/hcs0/Hackers-Delight/master/divmnu.c.txt // https://raw.githubusercontent.com/hcs0/Hackers-Delight/master/divmnu64.c.txt std::pair<uint128_t, uint128_t> uint128_t::long_division( const uint128_t& dividend, const uint128_t& divisor ) const { // Check for division by zero if ( divisor == uint128_0 ) { throw std::runtime_error( "Division by zero" ); } // If the divisor is 1, the quotient is the dividend and the remainder is 0 if ( divisor == uint128_1 ) { return std::pair<uint128_t, uint128_t>( dividend, uint128_0 ); } // If the dividend is 1, the quotient is 0 and the remainder is the 1 if ( dividend == uint128_1 ) { return std::pair<uint128_t, uint128_t>( uint128_0, uint128_1 ); } //If the dividend equal to divisor if ( dividend == divisor ) { return std::pair<uint128_t, uint128_t>( uint128_1, uint128_0 ); } // If the dividend is 0, the quotient and remainder are both 0 if ( ( dividend == uint128_0 ) || ( dividend < divisor ) ) { return std::pair<uint128_t, uint128_t>( uint128_0, dividend ); } std::pair<uint128_t, uint128_t> quotient_and_remainder( uint128_0, uint128_0 ); //Special case detection in order to simplify arithmetic. if ( this->high_bits == ZERO_BITS && divisor.high_bits == ZERO_BITS ) { if ( this->low_bits < divisor.low_bits ) { quotient_and_remainder.first.low_bits = BIT_ZERO; quotient_and_remainder.second.low_bits = this->low_bits; } else { quotient_and_remainder.first.low_bits = this->low_bits / divisor.low_bits; quotient_and_remainder.second.low_bits = this->low_bits % divisor.low_bits; } return quotient_and_remainder; } // 1. Initialization and normalization if ( dividend.high_bits < divisor.high_bits || ( dividend.high_bits == divisor.high_bits && dividend.low_bits < divisor.low_bits ) ) { quotient_and_remainder.first = uint128_0; quotient_and_remainder.second = dividend.high_bits; return quotient_and_remainder; } // Bit shift left to normalize int64_t shift = get_most_significant_bit_index(); // count leading zeros of the most significant word of the divisor uint128_t u = *this << shift; // normalized dividend uint128_t v = divisor << shift; // normalized divisor uint64_t qhat; // estimated quotient digit uint64_t rhat; // remainder uint64_t borrow; // borrow flag uint64_t carry; // carry flag int64_t n = 2; // number of words in the divisor int64_t m = 2; // number of words in the dividend minus n // 2. Main loop for ( int j = m; j >= 0; j-- ) { // Estimate quotient qhat = ( u.high_bits == v.high_bits ) ? ONE_BITS : ( u.high_bits * ONE_BITS + u.low_bits ) / v.high_bits; rhat = ( u.high_bits * ONE_BITS + u.low_bits ) - qhat * v.high_bits; while ( qhat >= ONE_BITS || qhat * v.low_bits > rhat * ONE_BITS + u[ j ] ) { qhat--; rhat += v.high_bits; if ( rhat >= ONE_BITS ) break; } // Multiply and subtract borrow = BIT_ZERO; for ( int i = 0; i < n; i++ ) { carry = qhat * v[ i ]; carry += borrow; borrow = ( carry < borrow ) ? BIT_ONE : BIT_ZERO; carry += u[ i + j ]; borrow += ( carry < u[ i + j ] ) ? BIT_ONE : BIT_ZERO; u[ i + j ] = carry; } carry = u[ j + n ]; carry += borrow; u[ j + n ] = carry; // If we subtracted too much if ( carry < borrow ) { // Add divisor back to dividend carry = BIT_ZERO; for ( int64_t i = BIT_ZERO; i < n; i++ ) { carry = u[ i + j ] + v[ i ] + carry; u[ i + j ] = carry; carry = ( carry >= ONE_BITS ) ? BIT_ONE : BIT_ZERO; } u[ j + n ] += carry; qhat--; } // Store quotient digit quotient_and_remainder.first[ j ] = qhat; } // 3. Get quotient and real remainder // Bit shift right to unnormalize quotient_and_remainder.second = ( u >> shift ).low_bits; return quotient_and_remainder; } const uint64_t& uint128_t::high_value() const { return high_bits; } const uint64_t& uint128_t::low_value() const { return low_bits; } std::string uint128_t::to_string( uint8_t base, const unsigned int& size ) const { if ( ( base < 2 ) || ( base > 16 ) ) { throw std::invalid_argument( "Base must be in the range [2, 16]" ); } std::string result = ""; if ( !( *this ) ) { result = "0"; } else { std::pair<uint128_t, uint128_t> quotient_and_remainder( *this, uint128_0 ); do { quotient_and_remainder = division( quotient_and_remainder.first, base ); result = "0123456789abcdef"[ ( uint8_t )quotient_and_remainder.second ] + result; } while ( quotient_and_remainder.first ); } if ( result.size() < size ) { result = std::string( size - result.size(), '0' ) + result; } return result; } std::ostream& operator<<(std::ostream & stream, const uint128_t & other) { if (stream.flags() & stream.oct){ stream << other.to_string(8); } else if (stream.flags() & stream.dec){ stream << other.to_string(10); } else if (stream.flags() & stream.hex){ stream << other.to_string(16); } return stream; } } // namespace TwilightDream
Editor is loading...
Leave a Comment