(Elegant Fibonacci) In class we saw that the 2×2 matrix F = 0 1 1 1 is a generat
ID: 3888370 • Letter: #
Question
(Elegant Fibonacci) In class we saw that the 2×2 matrix F = 0 1 1 1 is a generator of sorts for the Fibonacci numbers. That is, the lower left entry of F n is exactly Fn, the nth Fibonacci number. The following elegant algorithm, fibel(n), computes the nth Fibonacci number using the matrix F . In particular, if n is a power of 2, the nth power of F is computed by squaring F lg n times. Otherwise, if n is not a power of 2, and say that n = bkbk1 . . . , b2b1 (in binary), then F n is the product of F 2i over all i such that bi = 1. fibel(n) compute n in binary, say n = b[k]b[k-1]. . . b[1], where each b[i] {0, 1}. if b[1]=1 then total:= F else total:=I2 (2 × 2 identity matrix) for i := 2 to k do F := F F if b[i]=1 then total:=totalF return lower left entry of total You may assume that the time it takes to compute n in binary is (lg n). What is the runtime of fibel(n)?
Explanation / Answer
n = bkbk1 . . . , b2b1 (in binary),
then F n is the product of F 2i over all i such that bi = 1.
fibel(n)
compute n in binary, say n = b[k]b[k-1]. . . b[1], ===> Compute n binary which is O(log n)
where each b[i] {0, 1}.
if b[1]=1 then ===> Takes O(1) time
total:= F===> Takes O(1) time
else
total:=I2 (2 × 2 identity matrix) ===> Takes O(1) time
for i := 2 to k ===> Takes O(k) time
do F := F F ==> Takes O(k) time
if b[i]=1 then ==> Takes O(k) time
total:=totalF ==> Takes O(k) time
return lower left entry of total ==> Takes O(k) time
k is the bit length which is log n O(log n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.