|
|
|||||
|
|||||
|
Why Horner's Algorithm Works? Also see Horner's Algorithm We start this article with the assumption that you either know what Horner's Algorithm is all about OR you have read my article on the same. Before we start, let me make a fact absolutely clear. Mathematics is no magic. What I intend to say is, that, if you a find a shorter way to solve a given problem, all it means is that, it is a smarter way of solving the problem. This could be achieved by either using a different smart combination of laws than the ones used conventionally (for instance, using ancient Indian Vedic Mathematics instead of the ones that are taught to us at schools), or might be by reducing 'n' similar repeated steps into a single step (for example, use multiplication instead of repeated addition), or might be by splitting a single complicated calculation into multiple simpler calculations (I can't stop referring to Tensors), or invent a radically different new approach altogether (like for instance, Matrices). So, here we go. How do we convert a number containing n digits (say x1, x2, x3 ... xn) from a given base 'b' to base 10? We do it as follows: x1 x bn-1 + x2 x bn-2 + x3 x bn-3 + ... + xn x b0 For example, consider a number in base 8, like 4234(8). This is how we convert it to base 10. 4 x 83 + 2 x 82 + 3 x 81 +4 x 80 = 4 x 8 x 8 x 8 + 2 x 8 x 8 + 3 x 8 +4 x 8 = 4 x 512 + 2 x 64 + 3 x 8 + 4 x 1 = 2048 + 128 + 24 + 4 = 2204(10) So 4234 in base 8, is 2204 in base 10. So, whatz the problem with this approach? Well, as the number of digits increase or as the base to be converted from, gets larger, we have a problem, where in we will be multiplying larger numbers right in the beginning. Horner gave an alternative approach. He said, let us skip this business of raising to the power. Take a closer look at the above mentioned conventional conversion process. We start by multiplying the most significant digit (i.e. the leftmost digit), with a number which is the base raised to its power n-1 times, where n is the position of the digit from the least siginificant digit. We do this to each digit as we pass by. Simplifying this approach would be to remove the requirement of raising a number to its (n-1)th power, (n-2)th power, etc and instead use only normal multiplication. And, that is what Horner did. He just built in the power raising business intrinsically into the calculation process by combining each digit into the next multiplication process, and thus removing the need of raising a base to one of its power explicitly in the calculation process. To get a further clarity, let's re- calculate the above conversion using Horner's Algorithm. 4234(4) is now converted to base 10 using Horner's Algorithm. Step 1: 4 x 8 Step II: 32+2 =
34 Step III: (34 x
8) + 3 = 275 Step IV: (275 x
8) + 4 = 2204 So, to generalize Horner's Algorithm, the formula goes as follows: ((((x1 x b) + x2 ) x b + x3 ) x b ... upto xn-1) + xn So, we have seen why Horner's Algorithm works? Because, it still does what a conventional base n to base 10 conversion process does. But, by avoiding explicit calculations involving raising a base to its power. Observe that in
the above example, in the conventional method, the largest multiplication
we did was 8 x 8 x 8 x 4 While the former involves three multiplications, the simplest last one being 256 x 8, the latter is one straight forward 275 x 8. Having said this, it's up to you to decide which one to use in your calculations. Have a nice day :-) -by Gurudev
|
|||||
| Rate this article | |||||
| Comment on this article: Criticism is most welcomed | |||||
|
Physics - Chemistry - Mathematics - Bio-Sciences - Computers |
|||||
Home
