Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 6985 Views - Last Post: 14 June 2011 - 10:59 AM Rate Topic: -----

#1 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 02:57 AM

Hi, I did this code for finding the n-th Fibonacci number in JAVA and am trying to do this using Dynamic Multi-threading. The program works just fine however, I'm not sure whether I am doing it dynamically, in other words, I would not like to recalculate fib(n-1) and fib(n-2) if it has been done already thus minimizing calculations in each step. Would greatly appreciate your help on this. I used a static Array as an instance/global variable thinking that it will help me do this dynamically.

Following is the code that I did in JGrasp IDE
/*======================================================================================================================
   Author: NIAZ MOHAMMAD
	
	This program finds the nth Fibonacci number using dynamic multi-threading
	(implying divide and conquere strategy)and recursion.
	
   ========================================================================================================================*/
   import java.util.Scanner;
    public class Fibonacci implements Runnable
   {
      static long[] fib;
   
       public static void main(String[] args)
      {
         System.out.println("Enter an integer:(n>0) ");
         Scanner kbd = new Scanner(System.in);
         int n = kbd.nextInt();
         if(n < 0) System.out.println("The " + n + "th Fibonacci number is: "+ 0);//in this program n<0, not defined so print 0
         else if(n==0) System.out.println("The " + n + "th Fibonacci number is: "+ 0);//0th fibonacci number 0
         else if(n==1) System.out.println("The " + n + "st Fibonacci number is: "+ 1);//1st Fibonacci number 1
         else
         {
            long[] answers = new Fibonacci(n).getFib();
            //exception 11th,12th,13th
            if(n==11||n==12||n==13)System.out.println("The " + n + "th Fibonacci number is: "+ answers[n-1]);
            
            //switch has been used to denote cases where the 
            else{
               switch(n%10)
               {
                  case 1://n%10 = 1 print suffix = st
                     System.out.println("The " + n + "st Fibonacci number is: "+ answers[n-1]);
                     break;
                  case 2://n%10 = 2 print suffix = nd
                     System.out.println("The " + n + "nd Fibonacci number is: "+ answers[n-1]);
                     break;
                  case 3://n%10 = 3 print suffix = rd
                     System.out.println("The " + n + "rd Fibonacci number is: "+ answers[n-1]);
                     break;
                  default: //else print suffix = th
                     System.out.println("The " + n + "th Fibonacci number is: "+ answers[n-1]);
               }
            }
         }
         
      }
   
       public Fibonacci(int num)
      {
         this.fib = new long[num];
         new Thread(this).start();
         try
         {
            Thread.sleep(10);
         }
             catch (InterruptedException exception)
            {}
      }
   
       public void run()
      {
         synchronized (this.fib)
         {
            this.fib[0] = 1;
            this.fib[1] = 1;
            for (int i = 2; i < this.fib.length; i++)
            {
               this.fib[i] = this.fib[i - 1] + this.fib[i - 2];
            }
         }
      }
   
       public long[] getFib()
      {
         return this.fib;
      }
   }


Thanks for your time and help.

Is This A Good Question/Topic? 1
  • +

Replies To: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

#2 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2870
  • View blog
  • Posts: 11,021
  • Joined: 15-July 08

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 03:41 AM

I think that you have done this well. The iterative method to solving the solution is O(n), meaning that it increases linearly as you increase n. However, you aren't using recursion as you specify in the comments, AND the way that you attack the problem is not divide and conquer.

This is a good video on the divide and conquer strategy of calculating, though it is rather long:
http://videolectures..._demaine_lec03/

Good luck!
Was This Post Helpful? 1
  • +
  • -

#3 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 03:56 AM

Thanks The ninjaDucky, I'm not an expert on programming and still a beginner, so my teacher was saying that when i call the spawn fib(n-1) and fib(n-2), these are kind of like a recursive call and also since we are creating threads and let them do the job individually, in that sense I said Divide and Conquer strategy. By the knowing that my algorithm works almost in linear time i.e O(n), it's a bit of a sense of satisfaction. However, I'm still little confused about the fact that is my code actually performing dynamically with the use of static fib array, or do I have to get another way of memoization?
Was This Post Helpful? 0
  • +
  • -

#4 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2870
  • View blog
  • Posts: 11,021
  • Joined: 15-July 08

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 03:58 AM

In the iterative method that you have done it, you don't actually need an array at all...You just need two numbers. The point is that memoization is not necessary because you only touch each number once...not hundreds of times as you would in a recursive process.
Was This Post Helpful? 1
  • +
  • -

#5 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 04:16 AM

View PostDogstopper, on 13 June 2011 - 04:58 PM, said:

In the iterative method that you have done it, you don't actually need an array at all...You just need two numbers. The point is that memoization is not necessary because you only touch each number once...not hundreds of times as you would in a recursive process.


I see what you are saying bro :bigsmile: but I could be wrong, isn't the two threads trying to calculate the same number more than once, in case of, say, fib(5)

Posted Image

and this is what I want my program to avoid, the recalculation
Was This Post Helpful? 0
  • +
  • -

#6 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 05:11 AM

Thanks Dogstopper for your time and great help and others who read this topic
Was This Post Helpful? 0
  • +
  • -

#7 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 05:48 AM

As far as I know the conventional serial algorithmic approach to this problem takes O(Exponential) time whereas, according to this great admin of DIC, Dogstopper, mine takes O(n), just out of curiosity, could this problem of finding n-th Fibonacci number be solved in O(log(n))??

If yes, please enlighten us with details

Thanks
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10376
  • View blog
  • Posts: 38,415
  • Joined: 27-December 08

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 07:58 AM

It can be solved in O(1) time if you solve the recurrence. Multithreading this would serve no other purpose than generating a range of Fibonacci numbers, though.
Was This Post Helpful? 2
  • +
  • -

#9 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 01:18 PM

View Postmacosxnerd101, on 13 June 2011 - 08:58 PM, said:

It can be solved in O(1) time if you solve the recurrence. Multithreading this would serve no other purpose than generating a range of Fibonacci numbers, though.

You are GREAT!!! really googled it as Golden Ratio(since I knew about it from my CS Math class) but didn't know the n-th Fibonacci number could be found so easily in O(1). Wondering why people then worry about dynamic multi-threading approach, this and that then??

Anyways, your help is greatly appreciated and others who helped me learn a lot of new stuffs, thanks to them as well.

You all rock!!! :gunsmilie:

Here are some links I came across while searching for the Golden ratio: hope these helps others too

Dr Math
Ask Dr. Math
Golden Ratio
Golden ration and Fiboancci sequence
Was This Post Helpful? 1
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10376
  • View blog
  • Posts: 38,415
  • Joined: 27-December 08

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 01:39 PM

Quote

Wondering why people then worry about dynamic multi-threading approach, this and that then??

The Threading and memorization techniques are good for non-mathematical recurrences. Things like sorting apply. For linear, homogeneous recurrences like Fibonacci numbers, you can solve those like you would linear, homogeneous, differential equations if you've had or remember that from Diff. Eqs.
Was This Post Helpful? 1
  • +
  • -

#11 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 02:02 PM

well, now I'm satisfied after all these helps I got from all these great guys. I'm a newbie in this forum plus a newbie(considering a lot more to know about)in programming...so I've got a question and that is that I've done a project on Optimal Matrix search(2D) using interpolation search and modified binary search and lots of other methods, the current best(worst case I must say) is O((log(n))^2) as far as I remember...however, I am not that good at finding the time complexities..so should I make a new post about it?? or begin here?? Thanks

This post has been edited by nmohamma: 13 June 2011 - 02:04 PM

Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10376
  • View blog
  • Posts: 38,415
  • Joined: 27-December 08

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 02:09 PM

You're welcome to open a new thread, since it's a different topic. :)
Was This Post Helpful? 0
  • +
  • -

#13 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 02:23 PM

One last question: where can I submit suggestions/comments about this site if I may have any :rolleyes2:
Was This Post Helpful? 0
  • +
  • -

#14 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2870
  • View blog
  • Posts: 11,021
  • Joined: 15-July 08

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 13 June 2011 - 03:23 PM

If you have feedback, please use our Site Feedback forum.. Otherwise, if you have a question, use the Site Support & Questions forum.
Was This Post Helpful? 1
  • +
  • -

#15 nmohamma  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 26
  • Joined: 13-June 11

Re: Finding the n-th Fibonacci number using Dynamic Multithreading in JAVA

Posted 14 June 2011 - 07:16 AM

With all the help received from this forum members and guest visitors, and some research online, I came up with another version of solution to the same problem by incorporating java.math.BigInteger to support Fibonacci numbers well beyond the range of long data type. The underlying approach remains the same as before. This is provided so that others can get help if they require so.

N.B: This version is been tested for at most 2000 th Fibonacci number, however,

Quote

I have had problems finding the result at the first attempts, after some other inputs been tested, it gives the desired results. If anybody can resolve this problems, please do so at your own interest, and please let us know about the corrected approach
.

Thanks...

   /*======================================================================================================================
   Author: NIAZ MOHAMMAD
	
	This program finds the nth Fibonacci number using dynamic multi-threading
	(implying divide and conquere strategy)and recursion.
	
   ========================================================================================================================*/
   import java.util.Scanner;
   import java.math.BigInteger;
    public class Fibonacci implements Runnable
   {
      static BigInteger[] fib;
   
       public static void main(String[] args)
      { //long start=0,end=0;
         System.out.println("Enter an integer:(n>0) ");
         Scanner kbd = new Scanner(System.in);
         int n = kbd.nextInt();
         if(n<=1) System.out.println("The " + n + "th Fibonacci number is: "+ BigInteger.ONE);
         /*else if(n==1) System.out.println("The " + n + "st Fibonacci number is: "+ 1);//1st Fibonacci number 1
         else
         {*/
         else{
            //start = System.currentTimeMillis();
            BigInteger[] answers = new Fibonacci(n).getFib();
            //end = System.currentTimeMillis();
            //System.out.println("Elapsed time: " + (end-start));
            //exception 11th,12th,13th
            if(n==11||n==12||n==13)System.out.println("The " + n + "th Fibonacci number is: "+ answers[n-1]);
            
            //switch has been used to denote cases where the 
            else{
               switch(n%10)
               {
                  case 1:
                     System.out.println("The " + n + "st Fibonacci number is: "+ answers[n-1]);//n%10 = 1 print suffix = st
                     break;
                  case 2:
                     System.out.println("The " + n + "nd Fibonacci number is: "+ answers[n-1]);//n%10 = 2 print suffix = nd
                     break;
                  case 3:
                     System.out.println("The " + n + "rd Fibonacci number is: "+ answers[n-1]);//n%10 = 3 print suffix = rd
                     break;
                  default:
                     System.out.println("The " + n + "th Fibonacci number is: "+ answers[n-1]);//else print suffix = th
                     //System.out.println("Elapsed time: " + (end-start)+ " milli Second");
               }
            }
         }
         
      }
   
       public Fibonacci(int num)
      {
         this.fib = new BigInteger[num];
         new Thread(this).start();
         try
         {
            Thread.sleep(10);
         }
             catch (InterruptedException exception)
            {}
      }
   
       public void run()
      {
         synchronized (this.fib)
         {
            this.fib[0] = BigInteger.ONE;
            this.fib[1] = this.fib[0].add(BigInteger.ONE);
            for (int i = 2; i < this.fib.length; i++)
            {
               this.fib[i] = this.fib[i - 1].add(this.fib[i - 2]);
            }
         }
      }
   
       public BigInteger[] getFib()
      {
         return this.fib;
      }
   }

This post has been edited by nmohamma: 14 June 2011 - 07:17 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2