# Fast(ish) integer square root approximation for TADS3

Another answer-not-a-question. For this I was looking for a way of accurately approximating the square root in TADS3 without having to convert things to BigNumber first.

This is a fairly fast method that doesn’t rely on divisions or floating point arithmetic, and correctly computes the floor of sqrt().

``````sqrtInt(v, width?) {
local c, r;

if(v < 0) return(-1);
width = (width ? width : 32);
width += width & 1;
r = 0;
while(width > 0) {
width -= 2;
r <<= 1;
c = r + 1;
if((c * c) <= (v >> width))
r = c;
}
return(r);
}
``````

sqrtInt(v, width) returns the integer approximation of the square root of the first argument v. The second argument is optional, and is the width in bits of v. If the second argument isn’t given, the function assumes 32, which is the default size of an integer in TADS3.

In my test cases this method is more than an order of magnitude faster than taking square roots via TADS3’s builtin `BigNumber` support using something like `v = new BigNumber(v).sqrt()`.

Just throwing it out there in case it’s of use to anyone else.

3 Likes

Just for completeness, here’s a method for computing the bit width of an integer in TADS3:

``````bitWidthInt(v) {
local r;

if(v < 0)
return(-1);

r = 2;
while((v >> r) != 0)
r += 2;

return(r);
}
``````

Like `sqrtInt()` above, `bitWidthInt()` returns -1 on error (if you pass it a negative number).

Explicitly computing the “real” bit width of the number you’re trying to find the square root of eliminates several iterations through the left-shift-and-compare loop in `strInt()` but in my tests calling `bitWidthInt()` is on average still slower than just assuming the width of the input number is 32.

That’s an artifact of the TADS3 VM (the opposite is true in C, for example), which is one of the reasons I’ve taken the time to type this all out: TADS3 is a bit of an oddball implementation target, and writing performant code frequently involves using techniques that are counterintuitive from a “conventional” programming standpoint.

1 Like

well, the general idea isn’t new:

albeit I can’t figure the usefulness of transcendental mathematics in IF programming, is an interesting piece of coding.

Best regards from Italy,
dott. Piergiorgio.

Yeah. The TADS3 implementation is new (or at least I wrote it myself) but the underlying algorithm is one of the (many) standard approaches to approximating sqrt() without using floating point.

The main “original research” is in doing the testing to determine what’s optimal/gives the best performance on TADS, which is very often not at all what an optimal algorithm in C (or JavaScript or Java or Python or whatever) looks like.

In this case what lead me here is NPC decisionmaking, but I’ve also got some (fairly lightweight) procgen logic that’s a surprisingly thorny problem in TADS3 because the language really isn’t designed for (performant) general programming.

1 Like

procgen = procedural generation ?

Best regards from Italy,
dott. Piergiorgio.

OOF. I tried making an IF based on hunting in a landscape made of active cellular automata. I used all the garbage collection tricks in the book, and I almost killed the poor thing. I did not realize the limits of TADS 3 performance before that moment.

TADS3’s VM isn’t fast, agreed. But on many current hardware is faster than a PDP-11, early VAX and 8088/4,77 Mhz PCs.

This to say, why don’t do simpler things ? like the original Rogue ? less than ten location (and there’s at least 7 variation of twisty little passages in advent.inf & derivatives…) the main procedural issue should be building the connections between these less than 10 rooms with up to 8 potential exits. (plus only one up and one down if you want a multi-level dungeon…), I think that a text-only rogue game is feasible for TADS 'terp, even one in javascript or other interpreted language.

Best regards from Italy,
dott. Piergiorgio

For anything involving floating point, JavaScript is not just faster, it’s usually multiple orders of magnitude faster (on the same hardware). You can do full-on realtime physics modelling in JavaScript these days. I wrote a simple spring-and-Coulomb model to auto-layout graphs in TADS3 and with a simple 4 vertex graph it ran for several minutes before I gave up and killed the process. TADS floating point is slow.

Yeah, the performance bottlenecks I’ve been running into aren’t even using anything as “complicated” as CA.

One is a simple decision model for NPC AI…basically simple learning/behavior stuff for things that aren’t scripted for plot/whatever reasons. For example, the player can play poker with some of the NPCs. Much of the logic—like hand evaluation—can be reduced to lookup tables and so is super quick. But even rudimentary behavioral models become rapidly intractable in TADS3.

Same with the procgen stuff. Not even looking at full-on roguelike map generation and that kind of thing, but just simple layout problems (n-node graph, turn edges into map directions) are way more difficult than in almost any other environment you’re likely to find yourself programming in these days.

I’m actually considering something like writing mods/forking TADS just to make some of this “easier”.

1 Like

That’s a whole mood. Was really considering this one time. I think the main issue is that various runners use a standard implementation of TADS, so you would have to release your game as a standalone executable.

Yeah. Although one possibility is for the standalone executable to be compiled via emscripten into WebAssembly and either wrapped in its own web page or hacked into Parchment. Which restricts you to run in a browser (or I guess potentially CLI via node) but which does get you portability across platforms.

Haven’t really looked at how involved that option would be, or seen what the hidden “gotchas” are. Which is why I’m still writing things like fast integer approximations of sqrt() for TADS3: to see if I can accomplish what I want without having to resort to…extravagant…methods like forking a 'terp.

1 Like