Taylor Series by Horner's Rule (Using Recursion and loop) in C++

 The value of the Exponential function can be calculated using Taylor Series.

Taylor series is … 

e^x = 1 + x/1! + x^2/2! + x^3/3! + x^4/4!......

Now consider, the

• 1st term i.e. 1 - No multiplications here.
• 2nd term i.e. x/1! -  No multiplications here too
• 3rd term i.e. x^2/2! -  Two multiplications here   (x*x / 1 * 2)
• 4th term i.e. x^3/3!  -   four multiplications here   (x * x * x / 1 * 2 * 3)
• 5th term i.e. x^4/4!  -   six multiplications here   (x * x * x * x / 1 * 2 * 3 * 4)

So, if we go till 4th power of x in Taylor series we have to do 2+4+6 = 12 multiplications.

So this number of multiplications will take us O(n^2)  time. 

But we can reduce the no. of multiplications by using the Horner's rule.

Horner's Rule is just to take common variables and constants outside of the bracket so as to reduce the power the inside the bracket.

We can convert the Taylor series following Horner's Rule to 

e^x = 1 + x/1! + x^2/2! + x^3/3! + x^4/4!......

e^x = 1 + x/1 ( 1 + x/2 + x^2/2*3 + x^3/2*3*4).........

e^x = 1 + x/1 (1 + x/2 (1 + x/3 + x^2 / 3*4) ).....

e^x = 1 + x/1 (1 + x/2 (1 + x/3 ( 1 + x/4 ) ) ).....

As we can see the total number of multiplications is reduced to just 4 from 12.

So, this will give us O(n) time complexity.

Now, we can convert this into a program using a while loop.

C++

#include<iostream>
using namespace std;

//Taylor Series by horner rule using loop
double taylorHornerLoop(int x, int n){
    double s = 1;
    while(n>0){
        s = (1 + (x/n))*s;
        n--;
    }
    return s;
}

//Driver Code
int main(){
    cout<<taylorHornerLoop(4,30)<<endl;
}

Output

60

We can also do this using recursion

C++

#include <iostream>
using namespace std;

//Taylor Series by horner rule using recursion
double taylorHornerRec(int x, int n){
    static double s = 1;
    if(n==0){
        return s;
    }
    else{
        s = (1 + (x/n))*s;
        return taylorHornerRec(x,n-1);
    }
}

//Driver Code
int main(){
    cout<<taylorHornerRec(5,30)<<endl; 
}

Output

144

Read More about data Structures 

and programming in my Github Repos