Hacker News Reader

I think I've seen something similar for computing fibinocci values by converting the sequence into a series of matrix multiplications which can then be done in parallel because they are commutative (?). Each mareix is 2x2 with 1 in 3 cells and 0 in the last, representing the first fib numbers. Very cool transformation

View on HN

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.

Reply on news.ycombinator.com