puzzlecracker said:
Gianni Mariani wrote: .... ....
how to correct this problem?
Change the order of operations to minimize the round-off error
accumulation and/or use higher precision (double) numbers.
You can use exact numbers as well - like a quotient type.
This is one example I whipped up to come up with that bit pattern...
template <typename w_T>
w_T gcd( w_T i_v1, w_T i_v2 )
{
w_T l_vl;
w_T l_vs;
if ( i_v1 > i_v2 )
{
l_vl = i_v1;
l_vs = i_v2;
}
else
{
l_vl = i_v2;
l_vs = i_v1;
}
w_T l_t;
w_T l_t2;
do {
l_t2 = l_vl % l_vs;
l_t = l_vl;
l_vl = l_vs;
l_vs = l_t2;
} while( l_t2 );
return l_vl;
}
struct quotient
{
typedef unsigned long long t_type;
bool m_sign;
t_type m_numerator;
t_type m_denominator;
quotient(
bool i_sign,
t_type i_numerator,
t_type i_denominator
)
: m_sign( i_sign ),
m_numerator( i_numerator ),
m_denominator( i_denominator )
{
Simplify();
}
void Simplify()
{
t_type l_gcd = gcd( m_numerator, m_denominator );
if ( l_gcd != 1 )
{
m_numerator /= l_gcd;
m_denominator /= l_gcd;
}
}
quotient operator-() const
{
return quotient( !m_sign, m_numerator, m_denominator );
}
};
quotient operator+( const quotient & i_lhs, const quotient & i_rhs )
{
quotient::t_type l_demgcd = gcd( i_lhs.m_denominator,
i_rhs.m_denominator );
quotient::t_type l_mul_rhs = i_lhs.m_denominator / l_demgcd;
quotient::t_type l_mul_lhs = i_rhs.m_denominator / l_demgcd;
quotient::t_type l_den = l_mul_lhs * i_lhs.m_denominator;
if ( i_lhs.m_sign == i_rhs.m_sign )
{
return quotient(
i_lhs.m_sign,
i_lhs.m_numerator * l_mul_lhs + i_rhs.m_numerator * l_mul_rhs,
l_den
);
}
else
{
quotient::t_type l_num_lhs = i_lhs.m_numerator * l_mul_lhs;
quotient::t_type l_num_rhs = i_rhs.m_numerator * l_mul_rhs;
if ( l_num_lhs > l_num_rhs )
{
return quotient(
i_lhs.m_sign,
l_num_lhs - l_num_rhs,
l_den
);
}
else
{
return quotient(
i_rhs.m_sign,
l_num_rhs - l_num_lhs,
l_den
);
}
}
}
quotient operator-( const quotient & i_lhs, const quotient & i_rhs )
{
return i_lhs + - i_rhs;
}
quotient operator*( const quotient & i_lhs, const quotient & i_rhs )
{
return quotient(
i_rhs.m_sign != i_rhs.m_sign,
i_lhs.m_numerator * i_rhs.m_numerator,
i_lhs.m_denominator * i_rhs.m_denominator
);
}
quotient operator/( const quotient & i_lhs, const quotient & i_rhs )
{
return quotient(
i_rhs.m_sign != i_rhs.m_sign,
i_lhs.m_numerator * i_rhs.m_denominator,
i_lhs.m_denominator * i_rhs.m_numerator
);
}
template<
typename i_char_type,
class i_traitsbasic_ostream<i_char_type, i_traits>& operator << (
basic_ostream<i_char_type, i_traits> & i_ostream,
const quotient & i_value
) {
if ( i_value.m_sign )
{
i_ostream << '-';
}
i_ostream << i_value.m_numerator;
if ( i_value.m_denominator != 1 )
{
i_ostream << '/' << i_value.m_denominator;
}
return i_ostream;
}
//////////////////// example of you to use quotient this //////////////
int main()
{
quotient m_value( false, 1, 10 ); // 1/10th or 0.1
quotient m_bit( false, 1, 2 ); // 1/2 or 0,5 - the first bit.
for ( int i = 23; i --; )
{
quotient m_diff = m_value - m_bit;
if ( m_diff.m_sign )
{
std::cout << '0';
}
else
{
std::cout << '1';
m_value = m_diff;
}
m_bit.m_denominator <<= 1;
}
std::cout << " " << m_value << " " << quotient( false, 1000, 1 ) *
m_value;
}