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 TwilightDreamEditor is loading...
Leave a Comment