Software floats instead of fixed point?

[lwho]

I'm starting to get crazy while fixing all those over/underflows in galaxy generation. All of those are fixable, but the code doesn't get more readable by that. Galaxy generation code isn't exactly simple anyway and burying the algorithms below a layer of numeric tricks to avoid over- or underflows does not really help it.

So, I started thinking (I know, I should have done that earlier ;)). The fact, that we have quite large ranges of values in galaxy generation and already need some dirty tricks for that (e.g. different mass units for planets/stars) calls for using floating points.

We are not using (hardware) floating points in generation code, because they are not portable across platforms (or even on the same platform) and thus would yield different galaxies. However, a software floating point implementation would not suffer from this disadvantage. The implementation is not much more complex than our "fixed" implementation and I don't think it would be much slower than our (software) fixed point implementation. If we save overflow checking here and there by using floating instead of fixed point it might be not slower at all or even faster. I'm not thinking about implementing IEEE 754 (different rounding modes etc.), just what we need and mostly already have in "fixed".

Before I start such a work and implement software floats based on our "fixed" implementation I would like to ask into the round

• If anyone has a better idea than replacing fixed point by software floating point?
• If anyone knows a little, portable (and license compatible) library/module that we could re-use instead of re-inventing the wheel?

[impaktor]

If anyone knows a little, portable (and license compatible) library/module that we could re-use instead of re-inventing the wheel?

DrDobbs might have something on this, or does the boost library?

[FluffyFreak]

Something like those listed on this StackOverflow answer

[jpab]

This is a wheel that we (JohnJ, actually) already reinvented ages ago, the last time this idea was brought up. There should be a branch with the code in it somewhere. There are other software floating point libs we could use, but I haven't investigated them.

John B

[lwho]

Thanks for the heads up. I'll have a look for the branch. Of the existing libs, SoftFloat seems to be the most appropriate, though the full IEEE conformance probably comes at a price. I tend slightly to something self-made,but we'll see.

[DraQ]

What if instead of fixed point values we used plain ints for most of the stuff?
It won't necessarily cover all our needs (high ranges with high powers will still be a pain), but with cleverly selected units we should be able to cover a lot of stuff.
For example I remember calculating that 64bit int should be enough to map any given coordinate in a reasonably sized* planetary system with sub-cm precision.
Astronomical body mass expressed in masses of Deimos** shouldn't overflow even for the most massive stars and so on.

*) One where it's at all practical to get around without jumping. We could split unreasonably sized multiples into separate - in gameplay terms - systems.
**) Pretty much the smallest body in Sol with gravity worth accounting for, and also small enough to make any discreteness in masses of larger bodies not noticeable.

P.S.
Sorry about the long absence.
I'll try to find time to contribute from the beginning of the next year.

[jpab]

What if instead of fixed point values we used plain ints for most of the stuff?

"Fixed point" and "plain ints with carefully selected units" are the same thing. For example, a 32-bit 24.8 fixed-point value in light years is the same as a 32-bit integer value stored in units of (1/256) light years.

The tricky part, of course, is working out what units are sensible for each value. You also need to remember that in the galaxy code we have several non-trivial calculations that relate different values, and for fixed point you don't just have to choose the units for the input and output values, you also have to choose the units for every intermediate value in the calculation. The advantage of floating point is that it dynamically selects the "best" units (ie, the exponent) to represent each value. The disadvantage is that by making that choice dynamically it will have, in some sense, different behaviour for different values, which can be problematic. It also trades off some bits which could be used to represent values more precisely in order to instead represent the exponent, so for a given number of total bits you get a much greater range of representable values, but less precision.

In our case, I think the range of magnitudes that we're dealing with and the complexity of the expressions being evaluated (having many intermediate values with ranges that may be significantly different to the ranges of the input and output values) mean that floating point is a better choice than fixed point for galaxy generation. However, I am open to arguments on either side.

Fixed point may be better for some other contexts in our code, but that's a different discussion.

John B

[DraQ]

What if instead of fixed point values we used plain ints for most of the stuff?

"Fixed point" and "plain ints with carefully selected units" are the same thing.

I can't help but notice that our fixedf<int> template is quite a bit more involved than just a plain int64_t.

The tricky part, of course, is working out what units are sensible for each value. You also need to remember that in the galaxy code we have several non-trivial calculations that relate different values, and for fixed point you don't just have to choose the units for the input and output values, you also have to choose the units for every intermediate value in the calculation.

That is true, though intermediate values are only a problem if we're doing something that's bad for the range, like exponentiation.
We do have some such nasty formulas like Stefan-Boltzman, but since we're usually caring only about what comes out the other end, we can always just normalize to whatever makes sense in the context (like I did with planetary temperature calculations using Earth's respective values), and denormalize the output.

OTOH from what I've seen (and IIRC) the code is peppered with conversions between different units for the same type of values - for example jumping between Earth's, Jupiter's and Sol's masses.
That's nasty, bug-prone, convoluted, mess to maintain (as we have seen) and ultimately unnecessary. I think that as long as we can help it we should be using single unit for given value type and as long as we can help it it should be plain int or at least keep the other types contained.
Conversion to human readable units should be the job of the player's interface, and handling weird units in formulas, as long as we don't overflow due to exponentiation, should mostly amount to recalculating the constants - because that's what physical constants ARE, after all.

It would be good to see what different types of units we need, let's start with:

• Astronomical body mass (generates gravity, isn't subjected to dynamic physics).
• Dynamic object mass (doesn't generate relevant amounts of gravity, is used in physical and gameplay calculations)
• Temperature (we probably don't need or want to separate temperature for emitting bodies)
• In-system distances and coords (could probably be trimmed to plain non-float manageable range if we split highly separate multiples into their constituents and split off very distant planets into rogues - we have quite a few in-system distances that are impractical to cross using conventional drive, bodies separated in such way are effectively unreachable from each other anyway).
• Interstellar distances - game can be oblivious to their relationship with in-system ones

The advantage of floating point is that it dynamically selects the "best" units (ie, the exponent) to represent each value. The disadvantage is that by making that choice dynamically it will have, in some sense, different behaviour for different values, which can be problematic. It also trades off some bits which could be used to represent values more precisely in order to instead represent the exponent, so for a given number of total bits you get a much greater range of representable values, but less precision.

Yes. We also trade precision we could use for ability to represent values we won't need. For example if we're far enough from a point of reference, floats will give us considerable lack of precision with objects jumping around and choppiness, which is bad, OTOH we will be able to represent distances the size of an atom which is... come to think of it, not really useful.

I think fixed precision is really much better if we can afford it and given galaxy partitioned into individual systems we should be able to, so we even should try to use ints in actual gameplay in place of floats in many cases, if it's possible - for example if we represented actual in-game coordinates for in-system objects as ordinary int64_t-s we should be able to cover a 1000x1000x1000AU cube (which is a sensible size for a playable system) with around 1cm precision which should be enough when dealing with spaceships.

Lack of cross-platform consistency should be the least of our worries as it only helps with bug replication and multiplayer, and I don't think Pioneer is ever going to have the latter (if only due to time compression).

[jpab]

What if instead of fixed point values we used plain ints for most of the stuff?

"Fixed point" and "plain ints with carefully selected units" are the same thing.

I can't help but notice that our fixedf<int> template is quite a bit more involved than just a plain int64_t.

Yes, I'm sorry. I had forgotten dimensionless values (as I usually do when thinking about fixed point) which break the fixed-point=integer-with-different-units equivalence somewhat. However, for values which have units, there is no difference between treating them as fixed point or treating them as integers with appropriately adjusted units, just as there's no difference between units of metres and units of (1/1000) kilometres (silly example, I know, but hopefully it illustrates my point).

OTOH from what I've seen (and IIRC) the code is peppered with conversions between different units for the same type of values - for example jumping between Earth's, Jupiter's and Sol's masses. That's nasty, bug-prone, convoluted, mess to maintain (as we have seen) and ultimately unnecessary.

It certainly is nasty and bug-prone, and it's that complexity and extra development cost which is my primary reason (perhaps my only reason, but it's a pretty strong one) for believing that a switch to floating point would be an improvement overall. Also, given the bugs that we've already seen, I don't share your confidence that we could just pick one canonical set of units, and use fixed point, and not have problems of overflow.

Also, we really do need consistency of results in the galaxy generation code, and if you search the web for information about achieving consistency of results with hardware floating point, you'll find that it is possible but very tricky (for example: https://randomascii.wordpress.com/2013/ ... terminism/), which is why a software floating point implementation may be a better choice for the galaxy and system generation code.

In your message you also talk about the problem of objects jumping around because of the limited precision of floating point when representing values with large magnitude. This is entirely separate from galaxy generation. We only use fixed point values in the galaxy generation code (to ensure consistent results). For the dynamic state of objects, which includes the positions of everything you see in space, we have always used (hardware) floating point. It would certainly be possible to switch to using an integer representation of the dynamic position of objects while switching the galaxy generation code to use software floating point. Using integers for positions of objects has definite advantages and is more limited in development scope than maintaining fixed-point calculations for the whole of the galaxy generation code. This is for a couple of reasons: First, the positions only need to be stored as integers, (I think) the calculations can still be done using floating point, as long as an appropriate reference frame is used, second, as it's only positions that need the extra precision, we only have to choose distance units, not a whole collection of units. I'm undecided on whether the extra precision we would get from this is worth the extra code complexity, but I'm not against it if someone wants to take the job on.