Hacker News Reader

Your problem is practically important as it can be considered as the "canonical" string representation of given floating point number (after adding the closestness requirement). There are many efficient algorithms as a result, selected algorithms include Dragon4, Grisu3, Ryu and Dragonbox. See also Google's double-conversion library which implements first two of them.

Thank you for pointing me to all the prior work on this!

I am surprised how complex the issue seems to be. I assumed there might be an elegant solution, but the problem seems to be a lot harder than I thought.

See also the code in LLVM Flang for binary/decimal conversions. Minimal-digit decimals don’t come up in Fortran as often as other languages, but I use them when allowed by the output format. Interestingly, the last digit of a minimal decimal conversion is often irrelevant, so long as it exists.

Since such algorithms were developed in the 1990's, nowadays you can expect your language's standard library to use them for float-to-decimal and decimal-to-float conversions. So all you need to do in code is to print the float without any special formatting instructions, and you'll get the shortest unique decimal representation.

Except that C specifies that floating point numbers should be printed in a fixed precision (6 decimal digits) when no precision is given. Internally they do use some sort of float-to-decimal algorithms [1], but you can't get the shortest representation out of them.

[1] Some (e.g. Windows CRT) do use the shortest representation as a basis, in which case you can actually extract it with large enough precision (where all subsequent digits will be zeros). But many libcs print the exact representation instead (e.g. 3.140000000000000124344978758017532527446746826171875 for `printf("%.51f", 3.14)`), so they are useless for our purpose.

Ok, you got me there. Looks like they fixed that in C++17 with std::to_chars. https://en.cppreference.com/w/cpp/utility/to_chars.html

That's what the %g format specifier is for.

  printf("%f\n", 3.14); // 3.140000
  printf("%g\n", 3.14); // 3.14

This is a common misconception. Quoting the ISO C (actually the final draft of C23, but should be enough for this purpose):

> g, G: A double argument representing a floating-point number is converted in style f or e (or in style F or E in the case of a G conversion specifier), depending on the value converted and the precision. Let P equal the precision if nonzero, 6 if the precision is omitted, or 1 if the precision is zero. Then, if a conversion with style E would have an exponent of X: if P > X ≥ −4, the conversion is with style f (or F) and precision P − (X + 1). otherwise, the conversion is with style e (or E) and precision P − 1.

Note that it doesn't say anything about, say, the inherent precision of number. It is a simple remapping to %f or %e depending on the precision value.

Hmm, is that then just an extension that's de facto standard? Every compiler I tried at godbolt.org prints 3.140000 and 3.14 respectively.

3.14 is the correct answer for both %g and the shortest possible representation. Try 1.0 / 3.0 instead; it won't show all digits required for round-tripping.

Don't worry about negative comments, yes, this is not the best way, but (if there's no error, I didn't analyze it thoroughly) it's often good enough; if it works, then it works.

I once wanted to find a vector for which Euler rotation (5°, 5°, 0) will result with the same vector, so I just ran a loop of million iterations or so which would take a starting vector, translate it randomly slightly (add a small random vector) and see if after rotation it's closer to original than the previous vector would be after rotation, if not, discard the change otherwise keep it. The script ran for a couple seconds on Python and with decreasing translation vector based on iteration number, I got perfect result (based on limited float precision of the vector). 2s would be terribly slow in a library but completely satisfying for my needs :D

Thank you for your encouragement :)

I read a bit more about the topic, and it seems that the issue with my approach is that the decimal representation might end up exactly halfway between two floats, and then the result of parsing it depends on the rounding mode that the parser uses. (By default scanf should use round-to-even, but I'm not sure all implementations do so)

In the PostgreSQL docs I found a curious fact: They use an algorithm that makes sure the printed decimal is never exactly half way between two representable floats, so the result of scanning the decimal representation doesn't depend on the rounding mode.

FYI, you can solve your problem in closed form by converting your Euler angles into the 'rotation vector'[1] or 'axis-angle'[2] representations and then normalizing the resulting vector.

[1]: https://en.wikipedia.org/wiki/Axis%E2%80%93angle_representat...

[2]: https://en.wikipedia.org/wiki/Axis%E2%80%93angle_representat...

Cool! Thanks for that; it makes perfect sense: if you convert the rotation to axis-angle, and then take that axis, obviously a vector rotated around the axis defined by itself won't change.

I just tested it:

    from bpy import context as C
    from mathutils import Vector, Euler
    from math import radians as rad

    r = Euler((rad(5), rad(5), 0))
    ob = C.object
    ob.rotation_euler = r
    ob.rotation_mode = 'AXIS_ANGLE'
    a, x, y, z = ob.rotation_axis_angle
    v = Vector((x, y, z))
    print(v)
    v.rotate(r)
    print(v)
    print("--")

Can be done without using an object:

    from mathutils import Vector, Euler
    from math import radians as rad

    r = Euler((rad(5), rad(5), 0))
    v = Vector(r.to_quaternion().axis)
    print(v)
    v.rotate(r)
    print(v)
    print("--")

I guess that's faster than working out the eigenvectors by hand.

> I wonder if there is a more efficient way to determine that shortest representation rather than running printf/scanf in a loop?

Yes, just `printf("%f", ...);` will get you that.

The actual algorithms to do the float->string conversion are quite complicated. Here is a recent pretty good one: https://github.com/ulfjack/ryu

I think there's been an even more recent one that is even more efficient than Ryu but I don't remember the name.

std::numeric_limits<float>::max_digits10

https://en.cppreference.com/w/cpp/types/numeric_limits/max_d...

No, just no. And, never use sscanf().

This is totally pointless when serialization to and from an unsigned integer that's binary equivalent would be perfectly reversible and therefore wouldn't lose any information.

    double f = 0.0/0.0; // might need some compiler flags to make this a soft error.
    double g;
    char s[9];

    assert(sizeof double == sizeof uint64_t);

    snprintf(s, 9, "%0" PRIu64, *(uint64_t *)(&f));

    snscanf(s, 9, "%0" SCNu64, (uint64_t *)(&g));

If you want something shorter, apply some sort of heuristic that doesn't sacrifice faithful reproduction of the original representation, e.g., idempotency.

Off-topic, For this kind of pointer casting, shouldn't you be using a union? I believe this is undefined behaviour, as written.

As written, it is UB, yes, but certainly in C++, and, I think, also in C, using a union is undefined behavior, too. I think (assuming isn’t and float to be of the same size) the main risk is that, if you do

   union {
     float f;
     int i;
   } foo;
   foo.f = 3.14;
   printf(“%x”, foo.i);

that the compiler can think the assignment to foo.f isn’t used anywhere, and thus can chose not to do it.

In C++, you have to use memmove (compilers can and often do recognize that idiom)

Yes, it violates the standard, although in practice it should work because the alignment is the same.

If the goal is just to reliably serialize and deserialize floating point numbers, use `%a` instead. It will print and read hexadecimal floating point literals.