Question

You will write a program using 2 threads to calculate the Fibonacci number. Each thread will process one of the values used to calculate the result for the last iteration of the calculation. Each thread will use a recursive function to calculate its value and store its result in a global array. Each thread will return its results in a global array. The main program must wait for both threads to complete before exiting (join method must be used). The main program adds both values from the global array to calculate the value. In python.

Answer 1

We use the formulae of fibonacci that consists of no overlaps, ie

F_n = 4F_n-3 + F_n-6

This way we avoid computing useless values again and again. Comments are provided as required.

Code

#!/usr/bin/python3

import threading

class myThread (threading.Thread):
   def __init__(self, threadID, name, counter):
      threading.Thread.__init__(self)
      self.threadID = threadID
      self.name = name
      self.counter = counter
   def run(self):
      print ("Starting " + self.name)
      threadLock.acquire()
      fibonacci(self.counter)
      threadLock.release()

def fibonacci(counter):
   if counter < 0:
       return 0
   elif fib[counter] == -1:
       fib[counter] = 4*fibonacci(counter - 3) + fibonacci(counter - 6)
   return fib[counter]

threadLock = threading.Lock()
threads = []

print("Enter n : ", end = "")
n = int(input())
fib = [-1 for x in range(max(7, n + 1))]
fib[0] = 0; fib[1] = 1; fib[2] = 1; fib[3] = 2; fib[4] = 3; fib[5] = 5; fib[6] = 8

# Create new threads
thread1 = myThread(1, "Thread-1", n - 1)
thread2 = myThread(2, "Thread-2", n - 2)

# # Start new Threads
thread1.start() ;thread2.start()

# # Add threads to thread list
threads.append(thread1) ;threads.append(thread2)

# Wait for all threads to complete
for t in threads:
   t.join()
ans = fib[n - 1] + fib[n - 2]

print("Fibonacci(", n, ") : ", ans)
print ("Exiting Main Thread")