Stacking Actions - Part 3

In the previous article of this series we have seen that the re-normalized stack can be displayed as the $n$-th approximation of the Golden Ratio $\phi_{n}$ over $1$:

2 1 50 Fn 2DUP 2S>F F/ 1e .s \ do 50 iterations and re-normalize
53316291173 32951280099 <-Top 1.6180340E+00 1.0000000E+00 <-FTop  ok
FOVER F. \ pop result 1.61803399  ok

For this to happen the data stack was moved to the floating-point- or F-stack with S>F. Instead we could have iterated on the F-stack from the beginning!

Stack re-normalization Link to heading

Notice that stack re-normalization can be repeated, to the same effect: $$ G = GG $$

Then the question arises: do the $G$ and $F$ operators commute so that $GF = FG$ on re-normalized stacks? In other words can we prove that $[G,F]=0$ in a re-normalized environment?

Commutation means that the order of operations can be inter-changed (enclosing the commutator in $G$s to make sure the stack is always re-normalized): $$ G[G,F]G = G(GF-FG)G = GFG - GFG = 0 $$

With this simple argument we can now write $$ GF^n = (GF) GF^{n-1} = \ldots = (GF)^n $$ and treat $(GF)$ as a compound operator in our iteration. What does that mean?

What we have shown here (solely in operator/action logic, and regardless of operands acted upon!) is that the Golden Ratio can be approximated by the re-normalized Fibonacci iteration. Of course, this just proves that the iteration of $GF$ is a realization of the Continued Fraction

$$ { \phi_{n} = [1;1,1,1,\dots]_{n} = 1+ {\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{{\vphantom {1}} \atop \ddots }}}}}}} } $$

The reason for the Continued Fraction is that $\phi$ is recursively defined: $\phi = 1 + 1 / \phi$.

Compounded Operator Link to heading

So, here is the re-normalized Fibonacci operator for the F-stack and its iteration loop, which still uses the parameter stack for the counter:

: GF ( r1 r2 -- 1 r3) FOVER F+ FSWAP F/ 1e ; \ re-normalized Fibonacci  ok
: GFn ( r r n -- 1 r) 0 DO GF CR i . FOVER F. LOOP ; \ n iterations numbered  ok
2e 1e 10 GFn \ 10 iterations
0 1.50000000
1 1.66666667 
2 1.60000000 
3 1.62500000 
4 1.61538462 
5 1.61904762 
6 1.61764706 
7 1.61818182 
8 1.61797753 
9 1.61805556  ok

The first 10 iterations show how the stack converges to the Golden Ratio. But wait! There is always 1e (floating-point 1.0 on the F-stack) at the top of stack, so we can simplify our colon-definition using just a single starting value:

: GF ( r -- r) FDUP 1e F+ FSWAP F/ ; \ add 1e and divide

Now we can throw any number at GF and iterate. It will always converge to the Golden Ratio!

Recursion Link to heading

Expanding on the approximation of the Golden Ratio, which is the ratio of two consecutive Fibonacci type numbers, we can update until a certain precision is obtained.

With this understanding we are now ready for a recursive definition: GF calling itself, wrapped into GF. (read: GF-dot) which counts and prints each update until the threshold is reached:

: GF ( F: r -- r) FDUP 1e F+ FSWAP F/ ; \ add 1e and divide
: SF. DUP . FDUP F. CR ; \ print S and F TOS
: FTOL< ( F: r1 r2 --) ( -- f) F- FABS 1e-6 ( threshold) F< ; \ tolerance test
: GF. ( n -- n) ( F: r1 -- rn)
\ apply GF and print iterations until threshold reached
  FDUP GF ( F: -- r1 r2) \ update F-stack
  1+ SF. \ count and output
  FSWAP FOVER FTOL< \ reached?
  ?EXIT RECURSE \ portable exit
\ NOT IF RECURSE THEN \ recursive
;
\ example:
0 ( TOS) \ set counter zero
2e ( F: TOS) \ starting value
s" n phi_n" TYPE CR \ print column heads
SF. \ print starting values
GF. \ recurse until tolerance reached
\ bye

Here GF. (which is essentially GF) calls itself with RECURSE. The control structure NOT IF RECURSE THEN is not used but instead abbreviated as ?EXIT RECURSE which is portable.

The recursion is started with a counter (initially set to zero) on the parameter stack and an arbitrary float number (2e, say)¹ as starting value on the F-stack. We can then leave with bye or continue exploring the stack…

If the code is saved in a text file StackingActions.fs it can either be sourced by our Forth Interpreter² with INCLUDE StackingActions.fs. Or it can be sourced on startup and the output piped (with |tee) into the file fib.

sf StackingActions.fs |tee fib	# using SwiftForth (sf)
n phi_n
0 2.00000000 
1 1.50000000 
2 1.66666667 
3 1.60000000 
4 1.62500000 
5 1.61538462 
6 1.61904762 
7 1.61764706 
8 1.61818182 
9 1.61797753 
10 1.61805556 
11 1.61802575 
12 1.61803714 
13 1.61803279 
14 1.61803445 
15 1.61803381 
 ok

After 15 iterations the required precision is reached and the program stops. The stacks are now in a halting state and iterating can be resumed if one so wishes:

.s \ show stack
15 <-Top 1.6180338E+00 <-FTop  ok
GF. \ resume
16 1.61803406  ok

However, only one more update is produced as the recursion has already converged (with tolerance).

For illustration the file fib is plotted to show the convergence of $\phi_{n}$ over $n$, eg. with gnuplot³

gnuplot -e "se t png; se o 'StackingActions.png'; se k a col; p 'fib' w lp"

Conclusion Link to heading

In this article my focus has shifted to the Golden Ratio, an irrational number with infinitely many digits, which is at the crux of the generalized Fibonacci process. We have seen that by re-normalizing the stack updates a single object (a number) can be iterated to any desired precision using a recursive function call. What (numbers) are put on the stack is unimportant, they are just tokens. The action alone defines its form - the fixed point to which the iteration converges.