3

I'm trying to write a C++ function that takes as input an arbitrary double value and converts it into a string that meets three requirements:

  • When the string is converted back into a double, it will be exactly the same value as the original double
  • The string is of the shortest length possible
  • The string does not use scientific notation, e.g. 0.00123 not 1.23e-3

I have an implementation of this function that works, but using the first naïve method that came to mind:

#include <string>
#include <sstream>

using namespace std;

string doubleToString(double d, int precision)
{
    ostringstream ss;
    ss.setf(ios_base::fixed);
    ss.precision(precision);
    ss << d;
    return ss.str();
}

string convertDoubleToStringConciselyAndAccurately(double d)
{
    // a precision of 325 seems to be accurate enough to represent any double,
    // as the minimum positive double value has an exponent of -324 (at least
    // on the platforms I care about)
    const int maxPrecision = 325;

    for(int precision = 1; precision < maxPrecision; ++precision) {
        string possibleResult = doubleToString(d, precision);
        double d2 = atof(possibleResult.c_str());

        if (d == d2) {
            cout << precision << "\n";
            return possibleResult;
        }
    }

    return doubleToString(d, maxPrecision);
}

When this function is called with a double that requires lots of precision, such as a representation of an irrational number, it will usually have to make 16 attempts at converting it. If the number has a very small exponent, such as 1e-300, it can take hundreds of attempts. This isn't particularly fast or efficient!

So what would be a faster, more efficient, or perhaps more elegant way to implement this?

In fact, I'm wondering what's the fastest way of implementing this that we can figure out? Or the most efficient? Or both?

Note: I understand that for the vast majority of use cases the implementation I wrote is plenty fast and efficient enough — I'm not trying to micro-optimize. I'm asking this question purely for the intellectual curiosity of it, and so that I might learn something.

edit: My original implementation of the function had an error, where it assumed the maximum precision necessary for any double was 17. This is not true, as it doesn't cover doubles like 1e-100.

edit 2: I found an easy optimization, which is to figure out the exponent of the double value and use that as a starting point when searching for the right precision. Should mean that the function won't take more than 17 attempts to find the correct precision:

string convertDoubleToStringConciselyAndAccurately(double d)
{
    const int maxPrecision = 325;
    int minPrecision = 1;

    if (d < 0.1) {
        minPrecision = (int)floor(-log10(d));
    }

    for(int precision = minPrecision; precision < maxPrecision; ++precision) {
        string possibleResult = doubleToString(d, precision);
        double d2 = atof(possibleResult.c_str());

        if (d == d2) {
            return possibleResult;
        }
    }

    return doubleToString(d, maxPrecision);
}
Bri Bri
  • 2,169
  • 3
  • 19
  • 44
  • 2
    Have you tried [`std::to_string`](http://en.cppreference.com/w/cpp/string/basic_string/to_string)? – NathanOliver Mar 26 '18 at 21:34
  • @NathanOliver std::to_string creates strings much longer than they have to be from my experience. Ex 12 -> “12.000000” – Aiden Grossman Mar 26 '18 at 21:37
  • @NathanOliver That doesn't appear to do what I'm looking for. For example `std::to_string(1.2)` will return `1.200000` instead of `1.2`. – Bri Bri Mar 26 '18 at 21:38
  • Are there any requirements about precision? For example `0.30000000000000004` is "a bit long" you might say and want "0.3" instead as it is less than 1ulp from the correct value – WorldSEnder Mar 26 '18 at 21:40
  • @WorldSEnder that’s another thing. You will have to deal with the caveats of using floating point representations. – Aiden Grossman Mar 26 '18 at 21:41
  • Ah, yep. I normally don't use it for floating point types. Didn't see that it only uses 6 places for the decimal part. – NathanOliver Mar 26 '18 at 21:41
  • @WorldSEnder The double you get from converting the string back to a double needs to be *exactly* the same value as the original double. Meaning if you were to look at their raw bits, they will be identical. So to use your example, it'd need to be `0.30000000000000004` because that's not the same value as `0.3`. However, you don't want it to be `0.300000000000000040000`. Furthermore, `4.7999999999999998` is not necessary as `4.78` will actually convert to the exact same value. – Bri Bri Mar 26 '18 at 21:58
  • 1
    This is not a simple problem. It's pretty well understood among experts. [Here](https://github.com/jwiegley/gdtoa) is some good information and code. – Pete Becker Mar 26 '18 at 22:10
  • Is there a minimum value you'll encounter or do you have to tackle all the denormals too? How about INF and NAN? – Mark Ransom Mar 26 '18 at 22:46
  • @MarkRansom INF and NaN don't need to be accounted for. But there's no specific minimum value. Part of the idea behind this is that it should be guaranteed that any double representation of a number can be converted to a string and back again and yield bit-for-bit exactly what you started with. – Bri Bri Mar 26 '18 at 23:08
  • If you need a fast implementation, you'll need to use an own routine for this, as no standard function can do this. If you need an algorithm to do this, check out [this](https://github.com/kring/grisu.net). Btw, why do you prohibit the use of sci notation? It seems to be contradictory to the "shortest length" for numbers like 1e-200 (i.e., this is 6 characters instead of ~200). – geza Mar 27 '18 at 02:30
  • Possible duplicate of [C++: what is the optimal way to convert a double to a string?](https://stackoverflow.com/q/1313988/995714) – phuclv Mar 27 '18 at 07:38

1 Answers1

1

In C++17 I believe you can just use std::to_chars with std::chars_format::fixed specified.

Veedrac
  • 58,273
  • 15
  • 112
  • 169