On a platform of your choice, implement the three different methods for computin

Question

On a platform of your choice, implement the three different methods for computing the Fibonacci

numbers (recursive, iterative, and matrix) discussed in lecture. Use integer variables. How fast does

each method appear to be? Give precise timings if possible. (This is deliberately open-ended; give

what you feel is a reasonable answer. You will need to figure out how to time processes on the system

you are using, if you do not already know.) Can you determine the first Fibonacci number where you

reach integer overflow? (If your platform does not have integer overflow – lucky you! – you might

see how far each process gets after five minutes.)

Since you should reach integer overflow with the faster methods quite quickly, modify your programs

so that they return the Fibonacci numbers modulo 65536 = 216. (In other words, make all of your

arithmetic modulo 216 – this will avoid overflow! You must do this regardless of whether or not your

system overflows.) For each method, what is the largest Fibonacci number you can compute in one

minute of machine time?

Explanation / Answer

Fibonacci :

public class F_number {

static int num = 0, n = 8;

public static void main(String[] args) {
// This will print series till 8
fib(0, 1);
}

public static void fib(int a, int b) {
// Terminating condition.
if (a >= n) {
return;
}

else {
System.out.print(" " + no);
num = a + b;
a = b;
b = num;
fib(a, b);
}
}
}

number: 65536

(a + b) (mod n) = (a (mod n) + b (mod n)) (mod n)

e.g. a = 7, b = 4, n = 3
LHS = (7 + 4) (mod 3) = 11 (mod 3) = 2
RHS = ( 7 mod 3 + 4 mod 3 ) mod 3 = ( 1 + 1 ) mod 3 = 2 = LHS

so if we take n = 65536/2, max value of both a (mod n) and b (mod n) is
65536/2 - 1. so the max value of the sum is 65536 - 2, which means it is guaranteed that the sum will not overflow.

the number of times it overflow can be found as such:

x = (7/3) + (4/3) = 2 + 1 = 3
y = ((7 mod 3) + (4 mod 3)) / 3 = ( 1 + 1) / 3 = 0
o = x + y = 3 + 0 = 3

so the number of times it overflow is 3. to get back the real value, we do:

i = 3 * 3 + 2 = 9 + 2 = 11

the basis upon which this work is:
consider that a and b take the following form:

a = g * n + p
b = h * n + q

where n is the modulo factor, p and q are the remainder.
so let's see when we do a/n + b/n:

a/n + b/n = (g*n+p)/n + (h*n+q)/n

where / is the integer division operator (i.e. rounding down the result).

therefore, a/n + b/n = g + h

now let's see (a+b)/n

(a+b)/n = (g*n+p + h*n+q)/n = (g + h) + (p+q)/n

see? we got the first term of the above expression already, now all we have to do is to get the second expression. by definition, p and q are the remainder, i.e.

p = a mod n
q = b mod n

substituting in...

(p+q)/n = ((a mod n) + (b mod n)) / n

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.