Thankful For Mathematics

Sorry I meant to write more but had to drive to something for a bit. I also just want to state for the record that I’m just sorta dumping my thoughts right now. These are not meant to be counter-arguments or anything; you are 100% correct about the concerns of BigNumber lag.


Another thing I wanted to say was that orbital mechanics (when you’re using conic approximations) don’t require (as much) iteration, compared to a full n-body physics simulation. You just need a moment in time, measured in seconds, and it gives you the true anomaly (angle/theta) and radius.

Even then, the algorithm (yes, algorithm, because Kepler hates you) to find true anomaly can get really expensive.

So to explain more about this:

I was thinking of having a basic orbit object, and then a “baked” orbit object, where after all the adjustments are made, the baked version divides the period into 36 segments of time (uniting true anomaly, radius, and time, ideally as approximated integers). That way, if I want to find an orbital position at a certain time from a baked orbit, I’m dealing with only integers, up until the single interpolation bit.

Of course, orbital mechanics normally requires way more precision than this. In fact, this subject is quite notorious for testing the extreme limits of data precision, for this reason.

However, the benefit of writing an IF title that will convey things through text is that the player is not able to see the rough outline of the orbit, and it still functions about the same.

Worst case scenario, a fellow enthusiast will check my math, and I’ll be off by less than 10% maybe, but I’m certain they’ll understand lol.

The only reason why I’m going through this much work is:

  1. I’m an orbital mechanics enthusiast.
  2. I would like some way for a nav computer to help the player schedule things like intercepts, fly-bys, captures, etc. Even if the actual fine-tuning will be handled by the computer, the computer still needs a way to plot things over time and position.

The main concern I have with BigNumber lag is that while I have experienced it in a previous project, I am also currently running on a Linux, which was originally designed to be an overnight hobbyist-level “supercomputer”. I had to move to this as my main rig after I lost my laptop for a while, but now I can’t go back lol. (Turns out I don’t do enough stuff that absolutely requires a GPU to run.)

So, there’s always going to be a nagging concern in the back of my mind that the lag will be way more noticeable for someone else, when I’m not seeing it at all. Once I get this to a testing state, I would love to have someone on a really low-end rig try it, and let me know if it’s unplayable. I don’t want to inadvertently create the IF sphere’s version of “but can it run Crysis?”.

3 Likes

well, being a Naval historian, Naval fire control equations are my run-of-mill general programming problem, whose are best tackled with general programming language (I tend to use Fortran)

and, the best site for an orbital mechanics enthutiast:

Virtual Apollo Guidance Computer

Best regards from Italy,
dott. Piergiorgio.

4 Likes

Oh yeah, I understand. I meant generic “you”: anyone who sat down to implement a new IF authoring system today would probably be better off using one of the many languages/environments that already exist on virtually every platform instead of rolling their own virtual machine.

It’s difficult to isolate the exact trouble spots (because afaik there aren’t debugging tools like valgrind or gdb or anything like that for TADS3 code), but in my testing there wasn’t really any way to squeeze better performance out of it by doing a lot of hand-holding for memory management. Like you can assign two variables to random BigNumber values and then iterate through a big loop where you’re discarding any results involving them (e.g. by just putting a comparison in a conditional) and it’s still several orders of magnitude slower than doing the same thing with integers. I assume this tells us that the compiler isn’t taking advantage of anything available on the local architecture and is just using its own floating point implementation in the vm. I haven’t tried digging through the source code to be sure though.

I don’t know what your basic gameplay loop is going to look like, but if the player always has some physical constraints on how they can approach problems (that is, only so much fuel/specific thrust/delta v/whatever) and you know the orbits they’re going to be doing/attempting, you can probably just precompute a whole bunch of orbital elements for “valid” (as in orbit successfully achieved) solutions and then handle them at runtime via lookup table instead of computation. And then handle failure states (spin endlessly through space, smoking crater, whatever) via canned failure messages. Because although TADS doesn’t let you take advantage of modern computer architectures computationally, the huge amounts of memory/disk we have today are something that it’s fairly easy to take advantage of.

So basically the thing you’re talking about above (computing the orbital elements for a given game state, storing the results, and then interpolating to get a value at a specific point in the orbit) is absolutely a valid approach, but you can think much bigger.

For example, I wrote a poker-playing AI in TADS3/adv3 that’s about 90% table lookups, which means that it takes less time than evaluating the parse tree for the typed command.

You will get the compiler complaining if you store very large arrays; t3make by default worries about whether or not your game will run on a 16 bit machine, but you can suppress the warnings by compiling with the -w-15001 flag.

2 Likes

Oh, fascinating…! I was considering doing this at first, but I had some concerns about hitting some kind of memory limit. I wasn’t sure what TADS3 considers “too much”.

But yeah, the player will be stringing together transfers, slingshots, captures, etc, but it’ll be using only pre-determined altitudes. One concern was initial pre-computation time, and also (again) memory ceilings.

This was something I did in a C# version of this kinda game idea, but the loading time was rather long, and this was in C#.

2 Likes

It’s unfortunate that the T3VM doesn’t have any floating point opcodes. I’m not trying to convert anyone, but if anyone’s project truly does need a lot of floating point maths and it’s running far too slowly, Glulx now has both 32 and 64 bit floating point opcodes. They’re usable from both Inform 6 and 7.

4 Likes

You can precompute the values using a PreinitObject, which executes after compilation but before runtime (for release builds, at least, but t3make can be configured to do it for debug as well). If the precomputed values are stored in a global table, it will be saved in the image file.

3 Likes

How widely-supported are the double opcodes at this point? I didn’t realize any interpreters supported them yet.

1 Like

Parchment, Lectrote, Windows Glk, Spatterlight all already support them, and Gargoyle will in the next release. The main gap is the mobile interpreters.

2 Likes

Wait, what???

You can code in stuff to be pre-computed, and it saves the results during author compile, so it doesn’t happen during the player starting the game???

Jim, you are going to absolutely blow my mind, if I’m understanding you correctly. This changes everything.

2 Likes

Okay, I have an update. A little disclaimer: I haven’t run any formal computation speed tests yet (mostly because I’m not sure how to, in a TADS Linux environment. I’m used to speed tests with Java and C#).

For some context, I have invented my own response to the BigNumber, which I call the MegaRegister. A MegaRegister is capable of storing 16 digits of integer, positive and negative. So what makes it different from a BigNumber? See below:

  1. A MegaRegister does not touch garbage collection. Once you have made all of your MegaRegisters, they are reused, recycled, and kept in memory.
  2. Instead of exchanging object references, MegaRegisters simply load their contents into other MegaRegisters. All references to a MegaRegister are final.
  3. A MegaRegister is made of exactly four integers and a boolean. No more, no less. No computation time will be spent on resizing the contents of a MegaRegister, or accounting for various sizes.
  4. A MegaRegister can only do add, subtract, multiply, divide, and various comparison operations.
  5. All computations using a MegaRegister are strictly performed in a central “Register Core”, which has a fixed number of dedicated MegaRegisters for computation and answer storage.
  6. Operations have a lot of simplifications and efficiencies put in.
  7. MegaRegisters are not meant to be generalized or scaled; they are optimized for a very predictable execution environment.

The overall plan here is:

  1. During the preinit stage, do all the major computations with BigNumbers; nevermind the computation lag here.
  2. Cache all pre-computed orbits as approximations, made of MegaRegisters.
  3. Cached orbits can now be quickly evaluated using only a constant number of MegaRegisters, and simple computations.
  4. I can now quickly store and use distances from the sun to several magnitudes beyond the dwarf planet of Eris, down to the meter.

Tada!

It’s a lot, and people often tell me that my methods are overkill, but I’m gonna get crank the heck outta this. Sometimes the overkill method is necessary, in my experience. I’ve gotten stuff to run 10x faster than it’s supposed to, with a bit of neuroticism.

I’m not sure what the heck BigNumber is doing under the hood, but I feel like its general flexibility and near-constant harassment of garbage collection is probably a big part of the problem.

I’ll let y’all know how it goes.

3 Likes

Sounds cool! I wish I could find an excuse to use big math in a game…

2 Likes

If I had any interest in math whatsoever, then I’d probably lose my mind at this point. Thankfully, I absolutely hate math. :smiley:

6 Likes

Update: I have working addition, subtraction, and multiplication, with all the usual quick-reroute efficiencies for speed. None of it touches garbage collection. Honestly, it reminds me of my time programming ARM chipsets in Assembly.

Which brings me to this little nugget: Division operations.

Division is insanely expensive. The best I could figure out would be 52 multiplication operations, worst-case scenario (mostly guess-and-checks in a balanced binary tree).

This is when I discovered that a lot of early (and modern) ARM chips don’t support division at all, and would use all kinds of silly bit-trickery to replicate specific, controlled, and pre-calculated approximations of division.

So, after researching some of these fascinating tricks and work-arounds, I’ve been planning how I could implement them into my MegaRegister system, because true division would be really slow, and unnecessary for a lot of the math I plan on performing.

2 Likes

That really says that division has the cost of (single) multiplication plus an extra comparison for each bit. At least, that’s how I do it. Not the fastest way, but a whole lot simpler.

2 Likes

This is for multi-word integers? Also forgive me if I don’t completely follow what you mean.

1 Like

One word integer, but the word can be as many bits as you want.

  1. Shift the divisor up (*2) until it’s geater than the number. That’s zero as starting answer. (1)
  2. While the bit position is greater than 1, shift down. Add the divisor to number.
  3. If the new sum is greater than number, keep old sum. Keep the bits.(2)
  4. Repeat until the divisor is back to original (bit 1)
  5. Whatever left is the remainder. The kept bits is the answer. (3)

I hope that’s clear. Of course, that depends on how you do multiplication. (4)

Notes:
(1) Or just start by going to max bit in the beginning to simplify implementation.
(2) sum += (sum+div>num) ? 0 : div;
(3) so you use 2 separate “registers” or variables here.
(4) Multiplication is adding the second number to the first, everytime the control bit ( of original num) is 1, skipping at 0s.

Edit:
How do you multiply?
A=0 (answer)
B=first num
C=second num (control)
While (C) {
A+=(LSB(C))?B:0; //(C%2)
C>>=1;B<<=1; //(C/=2; B*=2)
}

Edit: check out "Russian Peasant Algorithm " :slight_smile:

With division, you want MSB, so you need to shift B (B*2^w) then reduce.

4 Likes

Ah, yeah, this is something like what I’m planning on implementing as well. I’m just working with multi-word integers.

1 Like

Uhhhh I’ve made a mistake.

Each integer in the 4-integer series represents a digit in base-10,000.

Why 10,000?

Because I’m a moron, apparently.

I had asked the question of “what’s the most-distant orbital distance (in meters) that I would need to keep track of?” and came up with a really big number, so I ignorantly just counted the base-10 digits of the result, and split them into equal groups of 4, rounding up, which means each group is 4 digits long, allowing it to store anything from 0 to 9,999. Hence: base-10,000.

So, uh… I sorta did this because it was natural and intuitive for me, and helped me figure out how the algorithms worked, but I failed to remember that I’m trying to make a version of BigNumber that’s easier on the interpreter.

It has now occurred to me, just now, that my chosen base forces me to use an integer division operation, every time I want to iterate through digits. I just learned a few days ago that division was really slow, and I’ve now connected the dots as to why most multi-word integers are implemented with bases built around powers of 2, because it would let me replace all division with bit-shifting, which is so much faster.

My code for the MegaRegister is really…uh…awkward, because it’s based entirely on constants and macros, to create a tightly-defined execution environment, both for speed and memory recycling. I didn’t want the CPU or interpreter to worry about execution stacks, or allocating memory for temporary variables. Of course, this isn’t the best corporate code, but corporate code probably won’t solve the BigNumber problem.

I am now beholding all this code, and realizing I gotta rewrite a lot of macros and general code to accommodate a new base value, which would allow me to ditch division, in favor of bit-shifting.

Ugh.

Like, I was literally reading what @ramstrong had explained, and was like “Oh that’s interesting, he’s using bit-shifting instead of division. In a thread where I’m lamenting about how slow division is. I wonder why that is.”

MAYBE IT’S BECAUSE HE KNOWS WHAT HE’S DOING, AND MY IMPLEMENTATION COULD BE AS FAST AND EFFICIENT AS WHAT HE OUTLINES, IF I COULD REALIZE THAT DIVISION IS SLOW, AT EVERY LEVEL OF EXECUTION.

So, uh…I got a lot more spoons to gather, and a lot of rewriting to do…

I have this weird habit of constantly chasing the hard problems.

The really big shambling mess in the room, though, is that I’m doing a lot of coding and implementation, but I need to figure out a way to do timed tests, and compare what I got so far with BigNumber. There’s a lot of work to reach a testing state, though, and there is still a possibility that this will be slower than BigNumber.

4 Likes

I’m not sure that I have fully understand your “base-10.000 math”, aside that looks like a sort of 10-bit BCD; If so, I can agree that handling the overflow between 1001 and 1023 is indeed awkward; if you want decimal math, perhaps is better use the good ol’ 4-bit BCD, or I have misunderstand something ?

Best regards from Italy,
dott. Piergiorgio.

2 Likes

If by “BCD”, you mean “binary-coded decimal”, then yes.

Basically I have 4 BCDs, and each handles 4 digits (0 to 9,999) of a massive base-10 number (0 to 9,999,999,999,999,999). All 4 BCDs work together to store a 16-digit integer in base-10.

I’m now realizing that I should have started this as 4 “digits” of 16 bits (0 to 511), thus giving me a 4-digit number in base-512 (0 to 18,446,744,073,709,551,615). That way, I can do bit-shifting between digits, and ensure they don’t get corrupted, or do unnecessary math to make it work out.

I’m essentially trying to recreate what would be an intrinsic 64-bit unsigned integer in any other language, without tossing all 64 bits to garbage collection constantly, like what BigNumber does.

Also, full disclosure: No hate to Michael J Roberts at all. BigNumber does its job well, and nobody would expect some wacko to come along and attempt an orbital mechanics game in their IF language. I fully own up to the fact that I am doing weird stuff again.

3 Likes