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.