Fuel Usage and Distances in Tim's HOST

This article describes some interesting artifacts about fuel usage in Tim's host. It was published first in May 2004.

What we all know

For several maneuvers in VGA Planets, it matters whether your ship has fuel or not. Combat is the most important of these: we all know that it is important that your Super Star Destroyer or your uncloaked robber reaches the planet without fuel.

Therefore, it is crucial that your client program offers you precise predictions about the fuel usage. Some people even use their hand-held calculator to validate the predictions. Still, it happens from time to time that host.exe surprises you.

The well-known formula for fuel consumption looks like this:

       EngineFuelUsage * (Mass DIV 10) * Trunc(Distance)
Trunc( ------------------------------------------------- )
                          (Way*10000)

where EngineFuelUsage is the engine-specific fuel usage (e.g. 8100 for Transwarp Drives at Warp 9), Mass is the gross mass of the ship, Distance is the distance travelled this turn, and Way is the maximum distance according to your speed (e.g. 81 for normal Warp 9, 162 for gravitonic Warp 9).

This formula appears in all major VGAP formula documents, all the major client programs use it. Decompiling HOST yields this formula, too. And I finally took a peep into HOST source code, and found it there, too. Still, client programs err in their predictions.

The problem

The distance travelled is computed using the good old pythagorean theorem:

Trunc(Sqrt(dx^2 + dy^2))

Single-stepping through host.exe (version 3.22.046 if you care) with a debugger finally yields a big surprise: when given the values dx=3, dy=0, this formula as compiled by Microsoft PDS BASIC, yields 2, not 3 as everyone expects. Of course, this means that the final result of the fuel consumption formula will be off from what you get with a hand-held calculator.

Investigation

Trying a bit more, we find many more such places where BASIC errs. The question now is: why does BASIC do that?

First, let's look on how the computation is implemented:

• The "square" operation, dx^2, is implemented using BASIC's ^ operator. Unfortunately, the compiler misses the obvious optimisation opportunity of transforming the program into dx*dx, and uses a very general routine to compute dx-to-the-second. Ultimately, it ends up computing

    exp(2*log(dx))

  instead, which is, as you might know, mathematically equivalent - in theory. Unlike for normal powers, there are well-known machine code sequences for computing exp(x) and log(dx). However, both logarithm and exponential are operations which yield irrational numbers which would need an infinite amount of memory to store, hence the processor has to round. That is, we're needing at least two rounding steps for an operation which can be computed in exact integers.
• The "square root" operation Sqrt(...) is, again, hard for the CPU. It always yields an irrational number except if the input is the square of a natural number. However, this step cannot be avoided easily.
• Finally, we truncate the result. Unlike a human, a computer doesn't have common sense. If the result is 2.99999999999999999999999999, the computer will happily truncate that to 2, although it is "obvious" that we actually mean 3.

To sum it up, host.exe involves three rounding stages where it would need at most one. It seems we lost enough precision by the first step that the second one occasionally produces numbers juuuuust below the actual result, so the third one yields a number which is one too low.

There are probably many more places, other than just (3,0), where the result differs from the exact one. Here is a plot of all the places where BASIC PDS yields a value that differs from the mathematically correct one, for a 1000x1000 matrix.

Quite impressive, eh? These are 1590 points, making the total error rate about 0.15 percent.

Comparison

So now let's check: how do other compilers operate on the same CPU? If there is a fundamental problem, they should be troubled by the same problem. For this comparison, I implemented an exact computation of the Trunc(Sqrt(dx^2+dy^2)) operation, and compared the performance of other compilers against it. I have computed only a 200x200 area, because relevant values for VGAP are 162 and below.

For cases where there are errors, I have provided a plot (don't hesitate to download them, they're no larger than 6k each).

You can download the test program source code here.

Note 1: Pascal does not have a built-in pow function, so I wrote my own, using the above formula. Pascal does have a sqr function, but that one generates code which is equivalent to explicit multiplying and does not change the result.

Note 2: many languages rely on the C runtime library, so I did not explicitly list the performance of, for example, Perl or C++. It would yield the same results as in C.

Note 3: all differences appear at places where the result would, mathematically speaking, yield an integer. For example, for a displacement of (16,63), the result of SQR(16^2 + 63^2) is 65. BASIC ultimately ends up at a value such as 64.999999999999 which is then truncated to 64.

Solution

Unfortunately, it is very hard to clone HOST's behaviour. One could "steal" the relevant parts of the MS BASIC runtime library, but that would limit us to programs running on a native x86 CPU with floating point unit. It is not possible to give a simple formula, either, because there's no simple error pattern.

However, since only result values below 162 are relevant, it is possible to compute a complete table with all results. I have prepared such a table for a 168x168 square. Actually, I have compressed the table to use only one bit per entry, so that it ultimately comes out at 3.5k only.

I have implemented this table in PCC and VPA, so the next versions of these programs (PCC 1.1.9, VPA 3.62b) will support exact fuel usage for THost. The most recent versions of Kero's RVV also support this table.

Table File Format (disttabl.dat)

VPA takes the table from a file disttabl.dat. PCC will also use that file if it finds it, but it also comes with a built-in default (like it has the standard ship-list built in). RVV has the table built-in.

The file consists of 168 "rows" of 21 bytes (=168 bits) each. The first row corresponds to dy=1, the second one is dy=2, up to dy=168. The first byte in each row corresponds to dx=0 to dx=7 (starting with the least-significant bit), the second byte describes dx=8 to dx=15, and so on. Each bit is set if the value at that particular place is larger than the value left to it.

To compute the value of INT(SQR(dx^2+dy^2)), you take row dy and count the bits up to and including the bit corresponding to dx, and add dy-1.

The table does not contain row 0; if you want to know a value for which dy is zero, you can swap dx and dy (the problem is symmetric). The value for dx = dy = 0 is zero, of course. If one or both of dx and dy are negative, remove the sign. The problem is also symmetric in that direction. If the coordinates are too big to be covered by the table, it is a multi-turn move, so the exact value is not relevant.

I encourage all other programmers of client programs to make use of that file, too. Some useful files, an implementation of the 'correct' fuel usage computation, and the disttabl.dat file can be downloaded here.

Of course, there are other possibilities to achieve the same result, you might even come up with a more efficient one. However, using this particular one makes it simpler to update your client in case Tim decides to change Host (maybe there are even host versions which do not exhibit this problem): all that needs to be done is to replace the file.

Side step: Running out of Fuel

If you want to rob someone, for example, you usually take a cloaked MBR, bring it to the ship you want to steal, and tow it away. You do that towing in a manner so that your MBR ends the turn with no fuel. Generally, this is hard, because you don't know how much the ship will weigh. Dacian Hantig discovered that there are some distances where the MBR can tolerate very large mass change and still reach its target.

That maneuver is not directly related to the pythagoras anomaly, but we finally found the reason: let's assume fuel is the amount of fuel used to cover a particular distance, and ship_fuel is the amount on the ship. In this case, the distance you are allowed to move

ERnd(Way * Ship_Fuel / Fuel_Usage)

Note that way is the maximum distance allowed by your speed (e.g. 81 or 162) whereas fuel is just the amount of fuel you need to travel, say, 5 ly to your waypoint.

That is, if you have only 80% of the fuel needed to go your distance, you are allowed to go 80% of your maximum movement, not of your waypoint. However, if your waypoint is longer or your ship is heavier, so that your fuel suffices for 50% only, you can only go 50% of your maximum distance.

A bit mathematics:

• EngineFuelUsage = fuel usage for your warp factor, e.g. 8100 for Transwarp Drives at Warp 9.
• Mass = ship mass
• Distance = distance to waypoint
• Way = maximum allowed distance (81 for Warp 9)
• Ship_Fuel = fuel on ship

Start with the fuel usage formula:

                    EngineFuelUsage * (Mass DIV 10) * Trunc(Distance)
Fuel_Usage = Trunc( ------------------------------------------------- )
                                       (Way*10000)

Let's take a particular ship and see how far it gets with its fuel. Set Fuel_usage = Ship_Fuel and, for simplicity, ignore all rounding:

               Ship_Fuel * Way * 10000
Distance = -------------------------------
           EngineFuelUsage * (Mass DIV 10)

Imagine a 370 kt ship with 3 kt fuel, Transwarps and Warp 9. Such a ship would get (3*81*10000)/(8100*37) = 8 light years until it runs out of fuel.

Now consider the case where Fuel_usage > Ship_Fuel. In this case, the allowed distance is

Allowed_dist = ERnd(Way * Ship_Fuel / Fuel_Usage)

We want to know the configuration where Allowed_dist gets maximal, that is, where Allowed_dist = Distance (because you'll never go farther than your waypoint is).

                                                Way * Ship_Fuel
Allowed_dist = ERnd ( ---------------------------------------------------------------------- )
                      Trunc(EngineFuelUsage * (Mass DIV 10) * Trunc(Distance) / (Way*10000))

Again, remove most rounding functions:

                      Way * Ship_Fuel * Way * 10000
Allowed_dist = ------------------------------------------
               EngineFuelUsage * (Mass DIV 10) * Distance

Now set Allowed_dist = Distance and solve it:

                        Way^2 * Ship_Fuel * 10000
Allowed_dist = Sqrt ( ------------------------------- )
                      EngineFuelUsage * (Mass DIV 10)

That is, the above 370 kt ship can go about Sqrt((81*81*3*10000)/(8100*37)) = Sqrt(656) = 25 light years, although the previous formula said we only manage 8 ly. Due to rounding, the actual value might even be larger.

I have tested this on host.exe: here's a diagram how far that 370 kt ship gets, and how much fuel it uses. The X axis contains the waypoint entered in the client program, the red dots are the distance actually travelled, the green ones are remaining fuel. As you see, the actual point where the ship runs out of fuel is at 9 ly:

Note that, starting at a particular distance, the farther the waypoint, the shorter the way you actually travelled.

Now ask the other question: how heavy can the ship get and still reach its 9 ly waypoint? Again, set Allowed_dist = Distance, but solve the system towards the ship mass.

               Way^2 * Ship_Fuel * 10000
Mass DIV 10 = ----------------------------
              EngineFuelUsage * Distance^2

Our 370 kt ship could therefore change its mass up to (81*81*3*10000)/(8100*9*9) * 10 = 3000 kilotons, that is, it can tow a 2630 kt ship(!) and still reach its waypoint.

Warning: These formulas involve heavy rounding. If you just type them into your handheld calculator, you get an approximate at best. The actual value might be somehow larger or smaller. Counter-check your results by using the "forward" formulas.

In reality, for example, the cited ship will need 9 ly to run out of fuel (see diagram), although the formula says just 8. It would manage to travel up to 27 ly (see diagram again). The 3000 kt ship would need (8100*300*8)/(81*10000) = 24 kt for normal travel, making its allowed movement 81*3/24 = 10 ly.

Tidbits

There are a handful of people who will now shout "Tim is a crappy programmer". This is wrong. Tim is innocent (okay, the run-out-of-fuel thing might be his fault, but that is a mathematical error, not a programming mistake :-) Tim probably doesn't even know what garbage his compiler produces (and it does produce garbage, as I know from endless debugger sessions). Actually, he should not have to know what comes out his compiler - that's what a compiler is for: you concentrate on the high-level language code, not on the machine code. It's MS who produced a really broken compiler and, as we've seen, they could have done better.

The crucial operation Trunc(Sqrt(x)) can actually even be implemented completely without rounding or floating-point. But, since the programming language already offers the required operators, only few people sit down and rewrite them again.

Special Thanks

Many thanks to Yendor (in the RCworld forum) for being insistent enough to make me look into this problem, and for clarifying the interaction with Dacian Towing. Without him, we'd still wonder why correct formulas yield wrong results.

Many thanks to Dacian Hantig for finding out about power towing.

Downloads

• Test program source code: fuel_programs.zip (2484 bytes)
• Test program results: fuel_results.zip (17k)
• Scripts and code for correct computation: fuel_code.zip (8555 bytes)