Scribd
Upload
20 views3 pages

Fibonacci Sequence in Python Programming

The document discusses algorithms for calculating Fibonacci numbers. It begins by introducing the Fibonacci series and its properties. It then provides two Python programs: 1) A recursive program that calculates the nth Fibonacci number from a command line argument. This is inefficient as values are repeatedly calculated. 2) An extension suggests an iterative program using an algebraic transformation method that "squares" the calculation at each step, making it more efficient than the recursive version.

Uploaded by

mark tranter
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views3 pages

Fibonacci Sequence in Python Programming

The document discusses algorithms for calculating Fibonacci numbers. It begins by introducing the Fibonacci series and its properties. It then provides two Python programs: 1) A recursive program that calculates the nth Fibonacci number from a command line argument. This is inefficient as values are repeatedly calculated. 2) An extension suggests an iterative program using an algebraic transformation method that "squares" the calculation at each step, making it more efficient than the recursive version.

Uploaded by

mark tranter
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithms - a simple introduction in Python: Part Six

... software is the nearest thing to magic that we've yet invented. It's pure "thought stuff" – which
means that it enables ingenious or gifted people to create wonderful things out of thin air. All you
need to change the world is imagination, programming ability and access to a cheap PC.
John Naughton, writing in The Observer

The Fibonacci Series

Leonardo Fibonacci was a brilliant Italian mathematician. It was he who popularised the
use of Arabic numerals (as opposed to Roman numerals) in the West. His most famous
work concerns an interesting series of numbers. The series begins with 0 and 1. Each
following term is made up by adding together the preceding two numbers.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

The numbers in this series turn out to have very interesting properties. For instance, the
further along the series you go, the closer the result of dividing one number by the next
comes to the “golden ratio”. Also, many naturally occurring structures seem to echo the
Fibonacci series - for instance the spirals of the seeds in sunflower heads. 1

Anyway, here we are mainly concerned with generating the numbers themselves. Let’s
say we want a program that, when we give it a number, n, will return the nth Fibonacci
number (zero is the 0th term, 55 the 10th etc.)

# fib_r.py - calculates the Fibonacci series, recursively,


# using command line arguments

import sys

def main():
if (len([Link]) != 2):
usage()
else:
try:
num = int([Link][1])
print("Fibonacci of", num, "is", fib(num))
except ValueError:
usage()

def usage():
"""Tells user how to run the program."""
print("Usage: for some positive integer, n:\nfib_r.py n")

def fib(n):
"""Takes an integer n and returns the nth Fibonacci number"""
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)

# main
if __name__ == "__main__":
main()

This program is different from the ones we have looked at so far in that it uses command-
line arguments.

1 To read more about this, visit: [Link]


To use it, open a terminal in the directory where the file is saved. Then type (assuming
python3 is the command to launch Python):

python3 fib_r.py 11

This runs the program and passes 11 to it. It should then give you the result. To make the
program work this way, we need to import “sys”. Any arguments passed to the program
are stored in a tuple: “[Link]”. The 0th element in the tuple is always the program
name, so we are interested in the next item. The program takes whatever is at [Link]
[1] and tries to turn it into an integer. If there are more or less than 2 items in [Link], or
the program cannot make an integer out of what it finds, the usage() function is called.

Once again I have used a recursive algorithm here. It should work well for small-ish values
of n. However it is very inefficient, not least because having two recursive calls to fib()
means some values are computed many times.

For example:

fib(5) = fib(4) + fib(3)


= fib(3) + fib(2) + fib(2) + fib(1)
= fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1
= fib(1) + fib(0) + 1 + 1+0 + 1+0+1
= 1+0+1 + 1 + 2
= 5

Task

Write a program that asks how many of the Fibonacci numbers the user would like to see.
Use an iterative algorithm to produce the numbers and print them to the screen.

Extension

There’s another nice way to generate Fibonacci numbers.

It turns out that, if we take a to stand for the current Fibonacci value and b to be the
previous one, the following transformation will give us the next pair of terms:

a’ = bq + aq + ap
b’ = bp + aq

The initial values of p and q are 0 and 1. If we use a = 21 and b = 13, we get:

a’ = 13 + 0 + 21 = 34
b’ = 0 + 21 = 21

Now, if we were to perform that transformation twice, we would in effect be squaring the
process. The new transformation has the same form as the old one, but now there are
new values p’ and q’:

p’ = p 2 + q2
q’ = q2 + 2pq
For example, let us take a = 34, b = 21, p = 0 and q = 1.

p’ = 0 + 1
q’ = 1 + 0

If we perform the transformation on a and b using p’ and q’, we get:

a’ = 21 + 34 + 34 = 89
b’ = 21 + 34 = 55

This is precisely what we wanted - the new transformation has given us fib(11) and fib(10)
from an input of fib(9) and fib(8).

Now that we can “square” the transformation, we can write a program that uses the same
“successive squaring” concept that we used in our exponentiation program.

# fib_alg.py Using the algebraic method.

def main():
print(fib(int(input("Fibonacci of: "))))

def square(x):
"""Returns x times x."""
return x * x

def even(x):
"""Returns True only if x is even."""
if x % 2 == 0:
True
else:
False

def fib(x):
"""This function launches fib_iter() with the correct starting values
for a, b, p and q. The user-supplied number is used as a counter."""
return fib_iter(1, 0, 0, 1, x)

def fib_iter(a, b, p, q, count):


"""This function uses successive squaring and the
algebraic method of finding Fibonacci numbers."""
if count == 0:
return b
elif even(count):
return fib_iter(a,b,square(p)+square(q),square(q)+2*p*q,count/2)
else:
return fib_iter(b*q+a*q+a*p,b*p+a*q,p,q,count-1)

# main
if __name__ == "__main__":
main()

As always, type the code in. Make sure you understand how it works and check that it
gives you the expected results.

If you are unclear about anything, remember that all the Python documentation can be
found at [Link].

Common questions

Powered by AI

Command-line arguments allow the user to specify an input number `n` for which the program should calculate the nth Fibonacci number. These arguments are accessed using the `sys.argv` array, where `sys.argv[0]` is the program name and `sys.argv[1]` should be the integer input. The program checks the length of `sys.argv` to determine if a valid argument is present and attempts to convert it to an integer to pass to the Fibonacci calculation function .

'Successive squaring' in the algebraic method leverages matrix exponentiation concepts to compute Fibonacci numbers efficiently. This involves iteratively squaring and transforming pairs of Fibonacci numbers to rapidly compute higher terms. By setting initial values such as `p=0` and `q=1`, the transformation calculates new values `a'` and `b'` that correspond to subsequent Fibonacci numbers. This method significantly reduces the number of operations by transforming and squaring, thus calculating Fibonacci numbers in logarithmic time .

The transformation for generating Fibonacci numbers goes beyond simple addition by using linear transformations, allowing multiple steps of the sequence to be calculated in fewer operations. It employs algebraic expressions that update two Fibonacci numbers simultaneously using matrix-like transformations. This method uses the principle of matrix exponentiation, which aggregates several updates into a single operation, increasing efficiency .

The iterative method for generating Fibonacci numbers improves upon the recursive method by avoiding redundant calculations. It uses a loop with two variables, `a` and `b`, representing the current and previous Fibonacci numbers, and iteratively updates these values to generate the sequence. This method is more efficient as it achieves the result in linear time (`O(n)`) compared to the exponential time complexity of the recursive method .

The primary advantage of the algebraic method for calculating Fibonacci numbers is its efficiency, particularly for large numbers. It employs matrix exponentiation principles to minimize the number of operations needed, allowing the Fibonacci number to be calculated in a logarithmic number of steps, `O(log n)`, compared to the linear or exponential steps required by iterative or naive recursive methods, respectively .

The `fib_iter` function implements the algebraic method by using a recursive helper function that applies the principles of successive squaring. It updates the variables `a`, `b`, `p`, and `q` based on whether the count is even or odd, ultimately reducing the problem size at each step. This function appropriately transforms the current and previous Fibonacci numbers, allowing the computation of the sequence terms using algebraic transformations rather than simple recursion .

To output the entire Fibonacci sequence up to the nth number, you would modify the program to store and print each calculated term within the iterative loop rather than just returning the nth term. In the iterative algorithm, maintain a list or array to append each `a` value during the computation in the loop, and finally output this list after completing the loop. This ensures all previous terms are captured and displayed to the user .

The recursive algorithm for calculating the Fibonacci sequence is considered inefficient because it involves redundant calculations. For instance, the function `fib(5)` in such a recursive approach leads to recalculating `fib(3)` and `fib(2)` multiple times. This occurs because each call to the recursive function results in two more calls, exponentially increasing the number of calculations required as `n` increases .

Using an inefficient algorithm like the recursive Fibonacci sequence in real-world applications can lead to significant performance bottlenecks. As `n` increases, the recursive algorithm's time complexity grows exponentially, which can cause unnecessary use of computational resources, slow down processing times, and become impractical for applications requiring rapid calculations or real-time processing involving large input sizes .

The iterative approach is preferred for larger Fibonacci numbers due to its efficiency and reduced computational complexity. It avoids redundant calculations present in the recursive method, which results in exponential growth of function calls. Instead, the iterative method maintains a running computation using a straightforward loop, achieving `O(n)` complexity compared to the recursive method's exponential `O(2^n)` complexity .

You might also like