3 ms·
transforming the recurrence to a matrix then applying the matrix as a transformation of itself can be expressed as multiplication. but AAAAAA doesnt really save
by leecarraher 3y ago
transforming the recurrence to a matrix then applying the matrix as a transformation of itself can be expressed as multiplication. but AAAAAA doesnt really save you much to get the 6th fibonnaci number. the power is in powers of the matrix. Now you can say
AA = A^2 , and A^2A^2 = A^4
still not computationally helpful, but
A^4A^4 = A^8
A^8*A^8 = A^16
...32
...64
and then you've got something useful.