Simple alternatives to floating-point when performing arithmetic on short string-encoded rationals

Question

I am creating unit tests for a function that rounds "rational" numbers stored as strings. The current rounding implementation casts the strings to a floating point type:

#include <boost/lexical_cast.hpp>

#include <iomanip>
#include <limits>
#include <sstream>

template<typename T = double, 
         size_t PRECISION = std::numeric_limits<T>::digits10>
std::string Round(const std::string& number)
{
    std::stringstream ss{};
    ss << std::fixed << std::setprecision(PRECISION);
    ss << boost::lexical_cast<T>(number);
    return ss.str();
}

In one of my tests, I input the number 3.55, which is represented as 3.5499999... on my machine. It all goes well when rounding from 2 decimals to 10. However, when I round to the first decimal, I unsurprisingly get 3.5 instead of 3.6.

What would be a simple method to avoid this error?

Currently, the best solution I was able to find was to use a multiple precision type:

#include <boost/multiprecision/cpp_dec_float.hpp>

#include <iomanip>
#include <sstream>

template<size_t PRECISION = 10>
std::string Round(const std::string& number)
{
    using FixedPrecision = 
        boost::multiprecision::number<
            boost::multiprecision::cpp_dec_float<PRECISION>>;

    std::stringstream ss{};
    ss << std::fixed << std::setprecision(PRECISION);
    ss << FixedPrecision{number};
    return ss.str();
}

While this solution addresses the problem in a straightforward way (vs manually parsing strings or creating a Rational number class), I find it overkill for such a simple problem.

To find ways to address this problem, I peeked at some calculators' implementations. I looked at gnome-calculator's source code and found that it uses GNU MPFR. I then looked at SpeedCrunch's implementation and found it re-uses the same code as bc, which employs a rational type (numerator, denominator).

Am I overlooking something?

Answer 1

If you are trying to round strings for a given number of decimal places (n decimal), you can do this directly on the string "the human way" : First check that the string has a decimal point. if it has one, check if it it has an n+1 digit after the decimal point. If it does, but it is less than five, you can substring the head of the string up to the n decimal. If it is greater than five, you have to transform your string, basically backtrack until you find a non '9' digit 'd', replace it with 'd+1' and set all the nines you found to 0. If ALL the digits before the n+1 decimal are nines (say -999.99879) append a 1 at the top(after the sign if there is one), and set all the nines you found to zero (-1000.00879). A bit tedious and somewhat inefficient, but straightforward and follows grammar school intuition.

Answer 2

You're not missing anything. The problem in your first implementation is that it's rounding twice: first in the conversion from string to float, and then a second time in the conversion from float back to string.

Using a multi-precision numeric type like boost's allows you to do the first conversion exactly (without rounding), and that's probably the most elegant way to solve the problem.

If you want to avoid using a multi-precision type, then you have to find some other way to represent a rational number, as was said already in the comments. You can do this with integers, but the result is much longer than the boost solution:

#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <sstream>

std::string Round(const std::string &number, size_t new_places)
{
    /* split the string at the decimal point */
    auto dot = number.find('.');
    if (dot == std::string::npos)
        return number;

    auto whole_s = number.substr(0, dot);
    auto dec_s = number.substr(dot + 1);

    /* count the number of decimal places */
    auto old_places = dec_s.size();
    if(old_places <= new_places)
        return number;

    /* convert to integer form */
    auto whole = atoll(whole_s.c_str());
    auto dec = atoll(dec_s.c_str());
    auto sign = (whole < 0) ? -1 : 1;
    whole = abs(whole);

    /* combine into a single integer (123.4567 -> 1234567) */
    auto old_denom = (long long)pow(10.0, old_places);
    auto numerator = whole * old_denom + dec;

    /* remove low digits by division (1234567 -> 12346) */
    auto new_denom = (long long)pow(10.0, new_places);
    auto scale = old_denom / new_denom;
    numerator = (numerator + scale / 2) / scale;

    /* split at the decimal point again (12346 -> 123.46) */
    whole = sign * (numerator / new_denom);
    dec = numerator % new_denom;

    /* convert back to string form */
    std::ostringstream oss;
    oss << whole << '.' << std::setw(new_places) << std::setfill('0') << dec;
    return oss.str();
}