Saturday, January 07, 2006

Root finding algorithms and their "near similarity" to search algorithms

Just don't know how to get started on this.
Two vast topics and I cant pinpoint the origin of this idea of mine.

This idea sprang up sometime in the 3rd semester of my CS degree during the Applied Mathematics course. No point giving credit to the course because it never exercised my mind.
Back onto the spicy stuff anyway.

The Applied Mathematics course had a section on root-finding algorithms for polynomial equations. I noticed a distinctive similarity between the bisection method to find the root of a polynomial function f(x), and the binary search algorithm to find the position of a key.
For starters, especially those who are not from the CS/Math stream, this might be a bit confusing so I'll provide extensive details as far as possible.

The bisection method is the simplest root finding algorithm. One can find the root of a function f(x)=0 by trying to approximate the range of values of the function in which there is a better probability of finding the root of the function. Read on if you still didn't understand.
Basically any function f(x)=0 can be treated as a series of values that vary with the variable (or parameter) x. So, if you "feed" in different values for x, you should get different values for f(x). The root of the function f(x) is that value of x at which f(x) equals 0. You normally don't have a lot of roots for a function f(x) - the number of roots for f(x) depends solely on the degree of the function f(x).
To demonstrate the similarity between the concept of root finding of a mathematical function f(x), and searching for key in a stream of numbers (a stream or sequence of numbers to which binary search or any other search algorithm can be applied), I make one important assumption :

Any stream of numbers [0, 1, 5, 7 , 14, 76, 196, 256, 983, 1005,.......] can be represented by an imaginary function f(x) - imaginary as in virtual/hallucination, not (-1)^(1/2).
Any function f(x) will have a corresponding stream of "data" that depends on what values of x have been applied to the function to produce the stream.

We'll put this important stumbling block behind us.
Now for the correlation between the word "root" of a function f(x)=0, and the word "key" of the binary search algorithm.

The "root" of the function f(x)=0, is that value of x that will ensure f(x) will produce a value of 0.
The "key" of the binary search algorithm is a possible value among the series of values produced by application of differing values of x to f(x). If the key element has been found in the stream of values, then our search is successful; if it hasn't been found, then the search is simply unsuccessful.
Finding the key in a stream is the same as finding the root of the function f(x) = key, x = 1,2,3,4,5........ :x denotes the position of an element in the stream [ if f(x) has the values 12, 45 , 65, 54 , 43, 78, then f(1) = 12, f(2) = 45, f(3) = 65 , f(4) = 54, f(5) = 43 , and so on].
If we find the key among the stream of values then we can find out the corresponding position in the stream, which is usually what most CS search algorithms have to do.

Similarity between the bisection method and the binary search algorithm

In both these algorithms, we divide the interval of values in half. For the binary search algorithm, the stream of values must be sorted so that it satisfies the requirement for the bisection method that can operate only on a continuous function f(x) !!

The binary search algorithm is definitely not the fastest as we know. But it definitely has predictable behavior as we all know - O(log n).

The question is now of beating this - application of algorithms that can converge on a "key" or the "root of the corresponding function f(x)" faster than binary search or bisection method can.
There are better root-finding methods than bisection method - Newton's method, Secant method, false position, linear interpolation(secant method again), polynomial interpolation(Muller's method), inverse quadratic interpolation, and Brent's method. Phew !!!!!!
Of course not all can be applied for searching, and not all can have predictable O(n) behaviors.
More research is required in this area. And certainly in designing the data structures/ databases that are optimized for such types of searches; certainly in determining if certain functions can be readily applied to existing data structures / databases.
Some theoretical problems too exist and they've been thankfully pointed out by Jim Lyon and Roman Werpachowski. At first glance, these could be ironed out by approximation and tweaking of the algorithms. But it still requires research !! And so I have to end my lecture here.

A discussion of this algorithmic technique can be found at JoS.

No comments: