Topic : Horners Algorithm
Author : Ilia Yordanov
Page : 1

How to run the Horner's algorithm


I.Legal

This tutorial is written by Ilia Yordanov, and can't be re-published without a written permission from the author!
If you want to contact me, mail me at: loobian@cpp-home.com

II.Assuming...

I am not assuming that you know C++, but it will be of help! Generally, the algorithm that I will explain can be implemented and ran in any language. Anyway, all the code examples are in C++...


III.About the author...

My name is Ilia Yordanov. Me and Deyan Vitanov are the owners of www.cpp-home.com!
Contact Information:
E-mail: loobian@cpp-home.com
ICQ: 52958267
URL: http://www.cpp-home.com

If you have any suggestions, recommendations and so on, on how to improve this tutorial, please email me!

IV.Introduction

This tutorial don't explain why the algorithm returns true results, but just how the one works... This is great way to convert numbers from one binary system into decimal. The thing that makes this algorithm better than the others, is that you don't need to use powers which is slowly ran. Instead of using powers,  you will use just adding and multipling...

Horner's algorithm


Now, imagine you have the number: 1101101 in binary, and you want to convert it in decimal. Probably the way you know is this: 1*2^6 + 1*2^5 + 0*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0, which returns 109. This way you use powers, which makes the whole process run slow...
The Horner's algorithms works like that:

     1  1  0  1  1  0  1
__|____________________
2  |1  3  6  13 27 54 109

As you see the last number is 109 which is the result in fact...
Here is how it works:

1.Numeric system...
The "2" which you see in the left down corner, is the numeric system that your number is in. In this case, it is in binary system, so we write "2". If it was hex, we should write "16" and so on...

2.Draw the table you see above. It has 4 fields:I- left up
II- right up
III- left down
IV- right down


I will use these numbers for future indication.

3.Filling the table

->The first (I) field is empty...

->The second field (II) should have every digit of the number, and levase some whitespace between the digits... just separate them! For example 1101101 should be written as 1  1  0  1  1  0  1. This is needed because you will need to write values under every digit...

->As said before, in the III field you write the system that your number is in.

->The last field (IV) is explained bellow...

4.Calculations...

This chapter explains how to get the numbers in the fourth field...

The first digit (1)- re-write it from the real number... in this case, the real number is 1101101, so the first digit of your calculations is 1. The second digit is: the numeric system multiplied by the first digit,and to the result add the second digit from the real number. This is: 2*1+1=3.
Now, the algorithm continues the same way to the end... you get the third digit by: multiply the previous digit (3) by 2 (the numeric system) and to the result add the 3th digit of your real number. This is: 2*3+0=6.
You get it?
Let's continue... the 4th digit you get this way: 6*2+1=13, after that 13*2+1=27, next is 27*2+0=54 and the last is 54*2+1=109, which is the real number in decimal value.

If you was converting from hex system, then you should be multipling by 16 but not 2...

5.Example program...

Here is an example program that illiustrates this algorithm...


/*********************************************
* Program : Horner's formula for converting
* to decimal numeric system.
*
* Date : 25 September 2001
* Author : Ilia Yordanov, Loobian
*********************************************/
//Including the libraries #1
#include <iostream.h>
#include <string.h>
//End of #1

//This is the function that makes the convertion
//It takes 3 parameters- char *array, unsigned short int system
//and int size.
//char *array is the array where is stored the number to be
//converted. Every digit of it must be in one cell
//unsigned short int system, stores which numeric system is
//the number in, and int size stores the size of the array
void horner(char *array,unsigned short int system,int size)
{

 int *result;

 result=new int[size];
 result[0]=array[0]-48;

 //Main loop that makes the convertion itself
 for(int g=0;g<size;g++)
  result[g+1]=result[g]*system + (array[g+1]-48);

 cout << "Result in decimal: "<<result[size-1]<<endl;

}


//Main function
void main()
{
 char a[100];
 unsigned short int sys;

 cout << "Enter number: ";
 cin >> a;
 int size=strlen(a); //Get the size of the array
 cout << "What numeric system is your number in? : ";
 cin >> sys;

 horner(a,sys,size);


}



Please, let me know if you have any recommendations, suggestions or comments at all... I can be reached at loobian@cpp-home.com


Copyright © 2001. All rights reserved! No part of this material can be copied without author's permission!


Page : 1