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?

By definition, rationals can be represented as a ratio of two integers. So use a data structure that represents a rational using two integral values - the representing or encoding of those integers can be anything you like. The means of adding, subtracting, multiplying, and dividing rationals are relatively simple. As is simplifying them (dividing numerator and denominator by the greatest common divisor). — Peter, Dec 02 '18 at 00:33
@Peter That really only moves the goalposts because now you have to implement decimal-to-rational conversion and _still_ must choose a precision limit. However, that _would_ be the appropriate thing to do here. I stole [this implementation](https://stackoverflow.com/questions/26643695/converting-decimal-to-fraction-c#comment41895571_26643695) for work just last week and it's great. — Lightness Races in Orbit, Dec 02 '18 at 00:35
@LightnessRacesinOrbit - a decimal to rational conversion is pretty simple - I remember learning the math for that in primary school. The key is choosing a representation of the numerator an denominator that is sufficient for needs. Yes, there is always a precision limit (e.g. the range of values a "big int" type can represent is limited by available memory, as is the ability to use a pair of them to represent a rational). Unless you're trying to represent an irrational value (e.g. represent pi to a huge number of decimal places as a rational) the practical limits will exceed what is needed. — Peter, Dec 02 '18 at 01:06

score 0 · Answer 1 · answered Feb 21 '19 at 20:13

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.

score 0 · Answer 2 · answered Feb 21 '19 at 21:47

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();
}

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

2 Answers2