Question

2. The Fibonacci sequence is defined as

f(n) = f(n - 1) + f(n - 2)

with f(0) = 0 and f(1) = 1.

Find f(54) by a program or maually. Note that this number must be positive

and f(53) = 53.......73 (starting with 53 and ending with 73). I must admit that

my three machines including a desktop are unable to find f(54) and they

quit during computation.

The answer is f(54) = 86267571272

*/

The Java code:

public class FibonacciTest2 {

​public static long BinaryFibonacci(int k) { // This is long type rather than int here

​​if (k == 1 || k==0)

​​ return k;

​​else

​​ return BinaryFibonacci(k - 1) + BinaryFibonacci(k -2 );

​}

​public static void main (String args[]) {

​​System.out.println(BinaryFibonacci(53));

​}

}

My new computer is able to find

f(53) = 53316291173 and

f(52) = 32951280099.

Therefore,

f(54) = f(53) + f(52) = 86267571272.

Note that if your computer is only able to find f(52), then you need do more calculation.

4. Analyze this code and run it, if there are any issues note them and fix them, if not give the output and Big O notation runtime:

public class PrintBits {

public static void printBits(int a) {

try {

String str = Integer.toBinaryString((Integer) a);

for(int i = 0; i < str.length(); i++){

System.out.print (str.charAt(i));

}

}

catch (ClassCastException e) {

throw new RuntimeException ("Argument is not an Integer");

}

}

public static void main (String[] args){

printBits (-17);

System.out.println();

printBits (17);

System.out.println( );

}

}

Answer 1

Hello there! :)

Answer 2.

You are facing the problem because of the time complexity of the algorithm you are using, that is, it takes too much time. There is a better time complexity algorithm to make it work on almost all modern machines pretty fast, that is, to find the Fibonacci number in a bottom up fashion. You know the values of and . Use them to calculate . Then use and to calculate and so on till you find . Here is a documented code to solve the assignment:

public class FibonacciTest2 {
    public static long BinaryFibonacci(int k) {
        if (k == 0)
            return 0L; // f(0) = 0
        if (k == 1)
            return 1L; // f(1) = 1

        // when k >= 2
        long a = 0L; // f(0)
        long b = 1L; // f(1)
        long c = a + b; // f(2)

        for (int index = 3; index <= k; ++index) {
            a = b;
            b = c;
            c = a + b; // f(index)
        }

        return c; // returning f(k)
    }

    public static void main (String args[]) {
        System.out.println(BinaryFibonacci(54));
    }
}

Here is a snapshot of a demo run showing my system specs, the time to taken to run and the computed value of :

Answer 4.

This one compiles and runs just fine on my system - no issues! :)

Here's the snapshot of the run:

The program computes the binary representation of the argument integer and loops through all the characters in the generated string of bits. Since an integer has a binary representation of a size that is of the order of the logarithm of the number base two, the Big O notation runtime is .

Hope this helps! :)