1

Like the title say, how I calculate the sum of n number of the form: 1+(1/2!)+⋯(1/n!)? I already got the code for the harmonic series:

#include <stdio.h>

int main( void )
{
    int v=0,i,ch;
    double x=0.;

    printf("Introduce un número paracalcular la suma: ");
    while(scanf("%d",&v)==0 || v<=0)
    {
        printf("Favor de introducir numeros reales positivos: ");
        while((ch=getchar())!='\n')
            if(ch==EOF)
                return 1;
    }
    for (i=v; i>=1; i--)
        x+=1./i;

    printf("EL valor de la serie es %f\n", x);
    getch();
    return 0;
}

The question here is.. I already got the sum as the fraction, but how make the variable "i" factorial?

Note: I´m programming in language C, with DEV -C++ 4.9.9.2

6
  • Vertical tabs? Please...
    – nhgrif
    Jan 14, 2014 at 23:51
  • 4
    Make a function for factorial.
    – haccks
    Jan 14, 2014 at 23:53
  • How would you generate a series from 1 .. N? Use that to make the terms of 1! to N! but just do it upside down. That way you can stop when it underflows.
    – woolstar
    Jan 14, 2014 at 23:53
  • 1
    think about what factorial means, and then write a fuction to do it. Then pass in i. Jan 14, 2014 at 23:55
  • 1
    @KerrekSB exp(1) is ans if n->infinity hence there is loss of precision for small n's like 5 Jan 15, 2014 at 8:31

4 Answers 4

2

You got a slightly more accurate answer for the harmonic summing 1./i + 1./(i-1) ... 1./1. Suggest you stay with that order.

[edit] Rewrite: Thanks to @pablo197 for pointing out the error of my ways.

To calculate harmonic and 1+(1/2!)+…+(1/n!), continue summing the least significant terms together first as that helps to minimize precision loss. Starting with the least significant term 1/n as sum, sum of that and the n-1 term is : sum = (1 + sum)/(n-1) and so on. (See below)

double x = 0.0;
double one_over_factorial_series = 0.0;
for (i = v; i >= 1; i--) {
  x += 1.0/i;
  one_over_factorial_series = (one_over_factorial_series + 1)/i;
}
printf("harmonic:%le\n", x); 
// 2.828968e+00
printf("one_over_factorial:%.10le\n", one_over_factorial_series); 
// 1.7182815256e+00

Add 1.0 or 1/0! to one_over_factorial_series, the result about e = 2.7182818284...

[Edit] Detail showing how direct n! calculation is avoided.

1 + (1/2!) + … + (1/n!) =  
1/n!  +  1/((n-1)!)   +  1/((n-2)!)  +  1/((n-3)!)  + ... + 1 =  
(1/n + 1)/((n-1)!)    +  1/((n-2)!)  +  1/((n-3)!)  + ... + 1 =  
((1/n + 1)/(n-1) + 1)/((n-2)!)       +  1/((n-3)!)  + ... + 1 =  
...
((((1/n + 1)/(n-1) + 1)/(n-2) + 1)/(n-3) + 1)/(n-4) + ... =  
5
  • -1: The OP question is about exponential series. Your code has a dummy factorial calculation that is never used, and the final result is the harmonic series, which the OP has already solved.
    – pablo1977
    Jan 15, 2014 at 1:02
  • @pablo1977 Right you are. Face palm - will need to re-work. Jan 15, 2014 at 1:13
  • I've elimitated my downvote because you now obtain right results, but I am not convinced at all. Your solution it is not pretty clear to me.
    – pablo1977
    Jan 15, 2014 at 6:02
  • 1
    @pablo1977 Some detail added to show how "1 + (1/2!) + … + (1/n!)" is changed to "((((1/n + 1)/(n-1) + 1)/(n-2) + 1)/(n-3) + 1)/(n-4) + ...". Jan 15, 2014 at 15:24
  • Ok. I'd like your idea. First, I did'n trust in it because it seems nice "in abstract", but in practice could be lost of accuracy by the accumulated errors in divisions. However, I have compared your version and the mine, and both give exactly the same results (respect to exp(1) in <math.h>). About efficiency, the number of operations of your algorithm seems to be the same as mine (n * (1 decrement + 1 division + 1 sum + 1 assignment)). However, I have found more speed with the technique of "store factorials in an array". I cannot explain the difference, but it seems not important
    – pablo1977
    Jan 15, 2014 at 21:36
1

If you're just looking for computing the first n factorials, I would suggest just computing them recursively, e.g.

factorial[0] = 1;
for (i = 1; i < n; i++) factorial[i] = factorial[i-1] * i;

However, unless you store them as floating point numbers, the large factorials are going to overflow really quickly.

1
  • This isn't so much a recursive solution as it is a dynamic programming solution.
    – Richard
    Jan 15, 2014 at 3:47
0

Calculating factorial in this case is bad thing to do because it can cause overflow for small values of N . Use following pseudo code to get it in O(N) without overflow.

double sum = 0.0;
double acc = 1;
double error = 0.0000001;

for(i=1;i<=n;i++) {
   acc = acc/i;
   if(acc<error)
       break;
   sum = sum + acc; 
}

print(sum);

More acurrate way of doing it though i feel it is unnecessary in case of factorials : -

double sum = 0.0;
double acc = 1;

for(i=n;i>=1;i--) {

   sum = (sum + 1)/i;
}

print(sum);

Note:- Because the above method is built in reverse it more accurate but unfortunately more time consuming because it is O(N) even for higher values whereas the gain in accuracy is negligible as factorial function grows very fast hence error keeps on decreasing quickly.

2
  • This approach may benefit from reading about Kahan summation. (Although in my test program the answers were the same out to 19 decimal digits of precision.)
    – Richard
    Jan 15, 2014 at 15:47
  • @Richard The factorial function grows extremely fast hence i dont think there is need to such an optimization because the error generated in each iteration decrease by large factor. Jan 15, 2014 at 16:00
-1

The number n! is equal to the product of n and the preceding factorial, that is, (n - 1)!.
If you calculate n! in an iteration, you are doing n products.
In the next step, say n+1, you repeat again these n products followed by the multiplication by n+1.
This means that you are repeating the same operations again and again.

It is a better strategy to hold the previous factorial that was calculated in the step n, and then, in the step n+1, just to multiply the n! by n+1. This reduces the number of products to 1 in each iteration.

Thus, you can calculate the series in the following way:

 int max_n = 20;     /* This value can come from another point of the program */

 int n;                  /* Initial value of the index */
 double factorial_n = 1; /* It has to be initialized to 1, since the factorial of 0 is 1 */
 double sum = 0.0;       /* It has to be initialized to 0, in order to calculate the series */

 for (n = 0; n <= max_n; )
  {
      sum += 1.0/factorial_n;
      n++;
      factorial_n *= n;
  }

 printf("Series result: %.20f\n", sum);

There are some numerical issues with this approach, but this go beyond the scope of your question.

About overflow: It is necessary to be carefull about the overflow of factorials after several iterations. However, I will not write code to handle overflow.

EDIT

I think that you have not to follow the suggestions of those people that advice to use a factorial function. This approach is very unefficient, since a lot of products are done in every iteration.
IN comparisson with that approach, the mine is better.

However, if you have plans to calculate these series very often, then my approach is not efficient anymore. Then, the right technique is that pointed out in the Bli0042's answer, that is: to hold the factorials in an array, and then just use them every time you need, without need to calculate them again and again in the future.

The resulting program would be this:

#include <stdio.h> 

#define MAX_N 100

double factorial[MAX_N+1]; 

void build_factorials(double *factorial, int max)
{
    factorial[0] = 1.0;
    for (int j = 0;  j <= max; )
     {
       j++;
       factorial[j] = factorial[j-1] * j;
     }
}

double exp_series(int n)
{
    int j;
    double sum;
    if (n > MAX_N)  /* Error */
       return 0.0;

    sum = 0.0;   
    for (j = n; j >= 0; j--)
       sum += 1.0/factorial[j];
    return sum;
}

int main(void) 
{

 int n; 
 double sum; 

  build_factorials(factorial, MAX_N);

  printf("Series (up to n == 11): %.20f\n", exp_series(11));
  printf("Series (up to n == 17): %.20f\n", exp_series(17));
  printf("Series (up to n == 9):  %.20f\n", exp_series(9));

  getchar();    
}

The iteration is done in reverse order inside the function exp_series() in order to improve the numerical issues (that is, to amortiguate the loss of precision when summing small terms).

The last code has side effects, because an external array is invoked inside the function exp_series().
However, I think that handling this would become my explanation more obscure.
Just, take it in account.

8
  • However the algorithm is fast and accurate.
    – pablo1977
    Jan 15, 2014 at 6:11
  • @pablo1977 factorial will overflow for larger values and give unpredictable values , why not divide by numbers rather then multiply at least the higher values will be 0 and will not cause side effects. Jan 15, 2014 at 12:56
  • @VikramBhat: I avoid to divide by j in each iteration because this introduce numerical issues. On the other hand, the product of integer numbers is precise, and one only has to be care about overflow, as you pointed out. I think that handling overflow will become obscure my exposition. However, a little comment can be added.
    – pablo1977
    Jan 15, 2014 at 13:37
  • @pablo1977, since the algorithm is neither fast nor accurate due to the obfuscation you've applied, I maintain that this is poor coding practise. Playing code golf rarely increases execution speed, but often decreases the brain speed of someone trying to understand the code.
    – Richard
    Jan 15, 2014 at 15:22
  • @Richard: "Rarely" is not applied to my code, because the speed and accuracy of it is due to the way in the "operations" are done. I can accept your criticism about the "style", but you are wrong in judging speed and accuracy, because you are not doing the required mathematical analysis of the problem. Perhaps you prefer O(N^2) and errors in the last digits. I prefer O(N) with arithmetical errors reduced to the minimum.
    – pablo1977
    Jan 15, 2014 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.