Please also note that this is not likely to be of use to anyone, I include it in case anyone is interested; please let me know if you read it
From building up from known algorithms for simple problems, we can determine a good algorithm for a more complex problem.
I will look here at problems of such a nature whereby the nth number in a sequence must be found, and the nth number comes from an operation on k previous terms where k is a constant. These sequencess can generally be expressed as a fibonacci-like sequences; they occur commonly in nature.
A simple starting point is a^n (a to the power of n) where n is an integer greater than 0. To find it we can take a and multiply by a (n-1) times. This algorithm is of O(n) time complexity. A much better one relies on the mathematical relation:
a^n = (a^(n/2))^2
By using this recursively we get a O(log(n)) complexity algoritm. It is also possible to use iteration (without a stack). I won't go into this now; it should be covered in any basic introduction to algorithms.
Now we take a slightly more complicated problem: that of Fibonacci numbers. The Fibonacci sequence appears like this:
0, 1, 1, 2, 3, 5, 8, 13 .....
Where Fib(1) = 0, Fib(2) = 1 and Fib(n: n>2) = Fib(n-2) + Fib(n-1). In other words any number in the sequence can be found by adding the two before it. I will note that it is possible to extend the sequence backwards; in this case we find it occurs in reverse and that every second number is negative. That is not important. We want an efficient algorithm to calculate the nth Fibonacci number.
We can get an O(n) algorithm by simply starting with two variables, called a and b, letting them start with 0 and 1, and repeatedly adding b to a and then swapping the two.
A better way is to use the following matrice identity:
- - ^n - - | 0 1 | = | fib(n-1) fib(n) | | 1 1 | | fib(n) fib(n-1) | - - - -
By using the binary powering algorithm this allows us to find fib(n) (as well as fib(n+1) and fib(n-1)) in O(log(n)) time complexity.
by multiplying out the matrices it can be shown that:
Yet where does the 0-1-1-1 matrix come from? It may have been discovered by chance. We can work it out, though, assuming we realise that there is a 2x2 matrice A such that A^n has elements which correspond to fibonacci numbers including and surrounding the nth.
If we take a two-by two matrix multiplication:
- - - - - - | a b | | w x | = | A B | | c d | | y z | | C D | - - - - - -
we see that each of the following is true:
Each of the four can correspond to a fibonacci expression of the form:
fib(n) = fib(n-2) + fib(n-1)
or possibly
fib(n) = fib(n) (if one of the coefficients was zero)
Because of this, we can define some rules that are only slightly arbitrary:
The w-x-y-z matrice is therefore a process by which we increment several fibonacci numbers to the next in the sequence.
Look first at A. The expression for it is aw + by, and we note that it is the next fibonacci number on from a. This means that either:
It is possible to find a working matrice from either the first or second option but I choose the second because it corresponds with the classic 0-1-1-1 matrice. This gives us w=0, x=1 and if a=fib(n-1) then b=fib(n).
Now look at B. We have B = ax + bz = a + bz. We can substitute fibonacci functions to get: fib(n+1) = fib(n-1) + z*fib(n). Clearly z = 1.
For C = cw + dy = dy. We don't yet have a determined meaning for d, but we known it is a fibonacci; we can let y = 1 and then say that if c=fib(k) then d=fib(k+1) (and therefore, C=fib(k+1)).
Finally, D = cx + dz = c + d. c is the fibonacci before d which means that D must be the fibonacci after D.
We now have a w,x,y,z = 0,1,1,1 which went put in a two-by-two matrice and used to multiply a matrice of the form:
- - | fib(k) fib(k+1) | | fib(l) fib(l+1) | - -
then the result will be of the form:
- - | fib(k+1) fib(k+2) | | fib(l+1) fib(l+2) | - -The convenience of having l = k + 1 is that the 0-1-1-1 then becomes a representation of the first three fibonacci numbers, and the 0-1-1-1 matrice can be put to the power of itself n times to obtain fib(n).
Note at this point, that if we redefined fib to be something like:
fib(n) = fib(n-1) + fib(n-2) + fib(n-3)It is possible to create a 3x3 matrice using the same principles as outlined above, and solve the problem in the same way.
Now we want to be able to use this to develop algorithms for functions not in the fibonacci form. I create an example function called Zig. Zig is similar to a fibonacci style function:
Zig(0) = 1, Zig(1) = 2 and Zig(n: n>2) = Zig(n-2) * Zig(n-1)
The Zig sequence is: 1, 2, 2, 4, 8, 32 ....
The general pattern looks familiar. In fact, the Zig sequence can also be expressed as:
2^0, 2^1, 2^1, 2^2, 2^3, 2^5 ....
or: Zig(n) = 2^fib(n). This observation alone allows us to devise an O(log(n)) algorithm to calculate Zig(n). But the pattern was recognised mostly by chance. How would we otherwise get a function of the form:
Zig(n) = Zig(n-1) * Zig(n-2)
into the form:
Func(n) = Func(n-1) + Func(n-2) ??
The log function can be used:
log2(Zig(n)) = log2(Zig(n-1)) + log2(Zig(n-2))
so: Func(n) = log2(Zig(n)), and we can work out a O(log(n)) algorithm for Func; given that Zig(n) = 2^(Func(n)) we have an O(log(n)) algorithm for Zig(n). (the 2^m operation can be done as a left shift, essentially a 0 time complexity operation).