@logic king..
the matrix exponentiation methos is something similar to the exponentiation
algorithm
where
x^n = x^n/2 * x*n/2 when n is even
x^(n-1)/2 * x^(n-1)/2 * x when x = odd
so in this way.. to calculate the x^63 value.. you need not multiply x 62
times..
but.. x^32, x^16, x^8,x^4,x^2, and the multiplication among these.. at max
it will invove 5-6 multiplications..
so.. complexity is log N
coming to the matrices
[ 1 1 ]
[ 1 0 ]
the above matrix can be used as the fibinocci series.. multipying with it
many times should give you the values
as
f(n+1) f(n)
f(n) f(n-1)
so.. the logic of exponentiation applied on matrices is used.. :)
hence log N complexity.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
