How to resolve the algorithm Fibonacci sequence step by step in the Potion programming language

Published on 12 May 2024 09:40 PM
#Potion

How to resolve the algorithm Fibonacci sequence step by step in the Potion programming language

Table of Contents

Problem Statement

The Fibonacci sequence is a sequence   Fn   of natural numbers defined recursively:

Write a function to generate the   nth   Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion). The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition: support for negative     n     in the solution is optional.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Fibonacci sequence step by step in the Potion programming language

Source code in the potion programming language

recursive = (n):
  if (n <= 1): 1. else: recursive (n - 1) + recursive (n - 2)..

n = 40
("fib(", n, ")= ", recursive (n), "\n") join print

iterative = (n) :
   curr = 0
   prev = 1
   tmp = 0
   n times:
      tmp = curr
      curr = curr + prev
      prev = tmp
   .
   curr
.

sqr = (x): x * x.

# Based on the fact that
# F2n = Fn(2Fn+1 - Fn)
# F2n+1 = Fn ^2 + Fn+1 ^2
matrix = (n) :
   algorithm = (n) :
      "computes (Fn, Fn+1)"
      if (n < 2): return ((0, 1), (1, 1)) at(n).
      
      # n = e + {0, 1}
      q = algorithm(n / 2)  # q = (Fe/2, Fe/2+1)
      q = (q(0) * (2 * q(1) - q(0)), sqr(q(0)) + sqr(q(1)))  # q => (Fe, Fe+1)
      if (n % 2 == 1) :  # q => (Fe+{0, 1}, Fe+1+{0,1}) = (Fn, Fn+1)
         q = (q(1), q(1) + q(0))
      .
      q
   .
   algorithm(n)(0)
.

fibonacci = (n) :
   myFavorite = matrix
   if (n >= 0) :
      myFavorite(n)
   .  else :
      n = n * -1
      if (n % 2 == 1) :
         myFavorite(n)
      . else :
         myFavorite(n) * -1
      .
   .
.

You may also check:How to resolve the algorithm Integer comparison step by step in the SQL PL programming language
You may also check:How to resolve the algorithm Palindrome detection step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Call a function step by step in the Forth programming language
You may also check:How to resolve the algorithm Repeat a string step by step in the Visual Basic programming language
You may also check:How to resolve the algorithm Higher-order functions step by step in the Groovy programming language