Computing Fibonacci number in FORM.

fibonacci.frm

* Procedures converting f(n) to the corresponding Fibonacci number:
*   F(1) = 1, F(2) = 1, F(n+2) = F(n) + F(n+1).

S fibN,fibX1,fibX2;
CF fibF;

* A straightforward implementation using the downward recursion.
* It generates many terms exponentially and becomes very slow for large n.
*
#procedure Fibonacci1(f)
  repeat id `f'(fibN?{>2}) = `f'(fibN-1) + `f'(fibN-2);
  id `f'(1) = 1;
  id `f'(2) = 1;
#endprocedure

* A better way to compute Fibonacci numbers with caching two lower values.
* It suffers the workspace limit in `Generator'; fails to compute f(994)
* with the default setting on Linux 64bit machines.
*
#procedure Fibonacci2(f)
  id `f'(1) = 1;
  id `f'(2) = 1;
  id `f'(fibN?{>2}) = fibF(fibN-2,1,1);
  repeat id fibF(fibN?{>0},fibX1?,fibX2?)
    = fibF(fibN-1,fibX1+fibX2,fibX1);
  id fibF(0,fibX1?,fibX2?) = fibX1;
#endprocedure

* A workaround for the workspace limit using (local) temporary $-variables.
*
#procedure Fibonacci3(f,tmp1,tmp2,tmp3,tmp4,tmp5)
  id `f'(1) = 1;
  id `f'(2) = 1;
  while (match(`f'(fibN?{>2}$`tmp1')));
    $`tmp2' = $`tmp1'-2;
    $`tmp3' = 1;
    $`tmp4' = 1;
    while ($`tmp2');
      $`tmp5' = $`tmp3';
      $`tmp3' = $`tmp3' + $`tmp4';
      $`tmp4' = $`tmp5';
      $`tmp2' = $`tmp2' - 1;
    endwhile;
    id `f'($`tmp1') = $`tmp3';
  endwhile;
#endprocedure

CF f;

L F = f(30);

#call Fibonacci1(f)
*#call Fibonacci2(f)
*#call Fibonacci3(f,tmp1,tmp2,tmp3,tmp4,tmp5)

P;
.end