Understand your algorithm

Understand your algorithm

It's easy to get tied up in Forth. The point is, only the first two items on the stack can be accessed easily - and what most people forget is that once you've applied your DUP or OVER you now got three items on the stack!

But you can free up some stack space by carefully planning your calculations and taking into account their scope. We've discussed the latter in great length in a former page. If you're working with plain cells note there is also the Return Stack. It's a great place to store (nearly) read-only values.

We're going to discuss an example of Rosetta code, a very fast integer square root routine. In order to understand this algorithm, we've made a uBasic/4tH implementation:

_iSqrt Param (1)
  Let q = 1
  Do Until q > a@
    Let q = q * 4
  Loop

  Let z = a@
  Let r = 0

  Do While q > 1
    Let q = q / 4
    Let t = z - r - q
    Let r = r / 2
    If t > -1 Then
      Let z = t
      Let r = r + q
    Endif
  Loop

Return (r)

So let's analyze this baby. It takes one parameter, the integer whose square root we're looking for. Halfway the algorithm its value is copied to variable z, but that's all. As a matter of fact: this copy is completely superfluous. We could have carried on with a@ and nothing would break. That's one variable down.

The q variable is assigned to "1" straight away. Halfway variable r is assigned to "0" - but if we did that straight away it would be fine as well, since it's not referenced. The t variable has a quite limited scope within the second loop. So we better leave it just where it is.

So what have we learned?
1. We don't need variable z since it is identical to a@;
2. Whether z or a@ - there is not too much going on here;
3. Variable r is only of importance in the second loop - but after variable q is used;
4. Variable t has a very limited scope within the second loop.

And with that information we'll decide which variable goes where:
1. Variable a@ goes on the Return Stack;
2. Variable z is dropped;
3. We initialize variables r and q straight away;
4. We initialize variable t when it's needed - and drop it as soon as possible.

That brings us to the first part of our implementation:

>r 0 1 begin dup r@ > except 4 * repeat

We put the input value on the Return Stack, initialize variables r and q and go straight into the first loop. Unless q is greater than a@ we multiply q by "4". We can forget about initializing r or z, because we're already there.

Let's start with the basic frame of the second loop. Variable q is still the "Top of Stack", so that's pretty easy:

begin dup 1 > while ( more stuff) repeat

First, variable q is divided by "4" - which is a piece of cake:

begin dup 1 > while 2/ 2/ ( more stuff) repeat

Now variable t has to be calculated - and it gets quite crowded on the stack. If we do it as advertised, we bury r and q under z (or a@ if you prefer) and subtract them both. For q that's quite doable (a simple OVER will do) but for r it gets quite complicated and ugly. But we can make our lives a whole lot easier by slightly transforming our expression:

t = z - r - q => t = z - (r + q) => t = -(r+q) + z

Which translates to:

over over + negate r@ +

So now we got three variables on the stack; from bottom to top : r, q and t. If variable t is negative, nothing happens - we just have to discard it. However, if variable t is not negative a lot is happening involving just about every variable. To make matters worse, we have to half the value of variable r, which is now buried under two other variables.

But there is a solution. Note that for this expression the position of variable r doesn't matter, so we can SWAP it:

swap over over + negate r@ +

Now the order of the variables on the stack is q, r and t. Since we always have to half the value of variable r, we could write the first part of the IF statement as:

dup 0< if drop 2/ else  ( more stuff) then

That's not inefficient since you have to branch and halve the value of r anyway. Performance-wise, you're doing nothing twice. I challenge you to rewrite it more efficient without drowning in stack acrobatics.

Our t variable becomes the new z variable, so we begin our ELSE clause with:

dup 0< if drop 2/ else rdrop >r ( more stuff) then

So much for variable t. At this moment the value of r is already halved in our algorithm, so we continue with:

dup 0< if drop 2/ else rdrop >r 2/ ( more stuff) then

And finally we have to add the value of q to r which is dead easy now:

dup 0< if drop 2/ else rdrop >r 2/ over + then

So, what's left? Let's clean up the stack so it represents the original stack diagram:

dup 0< if drop 2/ else rdrop >r 2/ over + then swap

And that ladies, is how it's done:

  begin
    dup 1 >
  while
    2/ 2/ swap over over + negate r@ +
    dup 0< if drop 2/ else rdrop >r 2/ over + then swap
  repeat

At the end of the second loop we still got variables r and q on the Data Stack and z on the Return Stack. There is added value to z, however. It holds the remainder of the original parameter and the square of the result so that:

a@ = r^2 + z

Ordinary programming languages do have a problem returning several results, but 4tH hasn't. So why not use it? Variable q goes out of scope now, so we can complete our stack diagram:

drop r>

And we're done. We've implemented our algorithm efficiently without too much trouble:

: sqrt-rem
  >r 0 1 begin dup r@ > except 4 * repeat
  begin
    dup 1 >
  while
    2/ 2/ swap over over + negate r@ +
    dup 0< if drop 2/ else rdrop >r 2/ over + then swap
  repeat
  drop r>
;

Epilogue

So what have we learned?
1. Don't resort to local variables without a fight. Local variables are for Forth losers and C programmers (these are different categories);
2. Study your algorithm closely;
3. Don't be afraid to rewrite your expressions;
4. Plan ahead. Don't just look for what you need right now - take into consideration what you need later;
5. Don't be afraid to retrace your steps and re-evaluate your choices;
6. Don't forget to clean up after yourself - no matter whether it's an IF, BEGIN..REPEAT or an entire routine;
7. Small routines are beautiful since they're easy to manage. And be DRY behind the ears before you even attempt to write Forth.