@dave: a(n)=a(n-1)+a(n-2)-a(n-5)-2 is not the same as b(n) = b(n-1) + b(n-2) - b(n-5) with b(n)=a(n)-2. b(n) = b(n-1) + b(n-2) - b(n-5) =>a(n)-2=a(n-1)-2+a(n-2)-2-a(n-5)+2 =>a(n)=a(n-1)+a(n-2)-a(n-5) which is not the same as original relation.
however the classic approach is still fine, we can have | a(n+1) | | 1 1 0 0 0 -1 -2| | a(n) | | a(n) | | 1 0 0 0 0 0 0 | | a(n-1) | | a(n-1) | | 0 1 0 0 0 0 0 | | a(n-2) | | a(n-2) | = | 0 0 1 0 0 0 0 | x | a(n-3) | | a(n-3) | | 0 0 0 1 0 0 0 | | a(n-4) | | a(n-4) | | 0 0 0 0 1 0 0| | a(n-5) | | 1 | | 0 0 0 0 0 0 1| | 1 | to complete the operation in O(log(n)) -- 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.
