Skip to content
January 4, 2011 / gus3

Back and Forth

The Forth version of the Collatz sequence is finally working, after the debugging interpreter was called into duty. Just as I suspected yesterday, I was over-thinking the stack manipulations, leading to over- and underflows.  I didn’t need to save space in each stack frame for distance accumulation; simply putting the accumulator at the bottom, followed by repeatedly “swap-drop-increment” until all recursions return, is enough to calculate the distance to 1.

The code is actually quite light, one of the hallmarks of Forth. In the “collatz” word (function), the even case takes 13 words, the general odd case 19 words, and the special case of 1 takes 12 words, not counting the closing “then” words. Unfortunately, for my very verbal mind, keeping track of lexical levels implicitly, rather than explicitly as with Lisp, meant I needed a word-by-word debugger to understand what was actually happening on the data stack. An hour-plus of debugging showed that I failed to follow the KISS principle. Once I cut away the excess thinking, and made the code do just one thing at a time, it suddenly started working a lot better. Imagine that.

\ Program to calculate the Collatz distance of
\ the first N positive integers
\ This is the core function
: collatz ( n1 - n2 )
( The basic theory is this: build the series on the stack,
 recursively, then drop them one by one as we exit the
 recursions, counting the drops. )
    dup
    2 mod 0= if ( even )
        2 / dup
        recurse ( for n/2 )
    else ( odd )
        dup
        1 > if
            3 * 1 + dup
            recurse ( for 3n+1 )
        else
            0 ( Collatz distance for 1 )
        then
    then
    swap drop 1 + ( unroll and count recursions )
;

\ The iterator
: colliter ( n1 - ; provided from CLI )
    1 + ( incr limit by 1 ) 1
    do
        cr i dup . collatz .
    loop
    cr
;

To invoke this program with the gForth interpreter, use a command such as

gforth collatz.fs -e "10000 colliter bye"

This will print the first 10,000 integers and their Collatz distances.

It’s been fun, and I’ve learned a lot about computing theory, but I think it’s time to leave the Collatz experimenting behind. Besides the mental weariness of pounding something into a pulp, I’m also annoying people around me when I talk about it.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: