#
# This software is Copyright 2005 by Elsevier Inc.  You may use it
# under the terms of the license at http://perl.plover.com/hop/LICENSE.txt .
#



###
### fib9
###

## Chapter 5 section 4.3.1

sub fib {
  my $n = shift;
  my ($s1, $return);
  my $BRANCH = 0;
  my @STACK;
  while (1) {
    if ($n < 2) {
      $return = $n;
    } else {
      if ($BRANCH == 0) {
        push @STACK, [ $BRANCH, 0, $n ];
        $n -= 2;
        next;
      } elsif ($BRANCH == 1) {
        push @STACK, [ $BRANCH, $return, $n ];
        $n -= 1;
        $BRANCH = 0;
        next;
      } elsif ($BRANCH == 2) {
        $return += $s1;
      }
    }

    return $return unless @STACK;
    ($BRANCH, $s1, $n) = @{pop @STACK};
    $BRANCH++;
  }
}