Need suggestion on sum of factorials.

Here is the problem:

Write a program to solve to following expression:
S=(1!/2)+(2!/4)+(3!/6)+....+(N!/2N)

- N read from keyboard.

This is my solution:

Code:

---

#include <stdio.h>
#include <conio.h>

long inputNumber, x;
double fact=1, sum=0;

void main()
{
    clrscr();
    printf("Enter number: ");
    scanf("%ld", &inputNumber);

    if(inputNumber==0)
    printf("\nPlease enter number from 1 up.");

    else
    {
    for(x=1; x<=inputNumber; ++x)
      {
      fact=(fact*x)/(2*inputNumber);
      sum+=fact;
      }
      printf("\nThe sum is %lf", sum);
    }
    getch();
}

---

Any suggestion to make this program better.

Quote:

---

This is my solution:

---

A quick test shows that your solution is incorrect.

Quote:

---

Any suggestion to make this program better.

---

For starters, change void main() to int main(), and remove your dependence on the non-standard <conio.h> by removing the unnecessary calls to clrscr() and getch().

Now, for actually solving the problem, you can make use of the fact that for any integer n > 0, n!/(2n) = (n-1)!/2.

I never know about this relation. Could you show me how to implement it in my code ?

Quote:

---

I never know about this relation.

---

It is just simple arithmetic. n! = (n-1)! * n, therefore you can simplify as such. Actually, there is a further simplification, but that may actually complicate your code a slightly instead, so perhaps it is better to leave it for later.

Quote:

---

Could you show me how to implement it in my code ?

---

First, implement a loop to sum from 1 to (n-1)! inclusive.

I suggest creating a function that returns the factorial of a number.

n! = (n - 1)! * n

A recursive function might be:

Code:

---

int fact(int n)
{
    if (n <= 1)
          return(1);
    return(fact(n - 1) * n);
}

---

Quote:

---

Originally Posted by noops

I suggest creating a function that returns the factorial of a number.

n! = (n - 1)! * n

A recursive function might be:

Code:

---

int fact(int n)
{
    if (n <= 1)
          return(1);
    return(fact(n - 1) * n);
}

---

---

But it is often better to let the poster figure those things out him-/herself, as that is touching many more parts of the brain, and thus makes it easier to remember, v.s. selecting an area of text and pasting it into their editor.

--
Mats

Not to mention that using such a function is inefficient.

It's not efficient, but it's quite simple. I mean, if the OP has already problems getting a correct solution, we shouldn't ask about getting the most efficient solution, shouldn't we ?

The only wrong thing I see with this function is the parameter and return type; I would definitely use an unsigned integer instead of a signed one, since the definition of factorial is only good for non-negative number.

By writing the factorial as a seperate function I believe that the OP would not learn everything that they should be learning. They will get a solution, but will not have learned how to properly implement an algorithm that performs according the more desireable and easily achieveable O(n) Big-Oh notation.

I found the mistake !
In my code, just make change to the statement in the for loop like this:

Code:

---

for(x=1; x<=inputNumber; ++x)
      {
      fact=(fact*x)/(2*x);
      sum+=fact;
      }

---

Tested and it works!

Quote:

---

Tested and it works!

---

it is really strange - it should not

Quote:

---

Tested and it works!

---

Sorry, it still does not work. For example, an input of 5 gives the result 0.96875, but clearly the answer is 17.

I don't know why it become like this, but when in typed in 3, it gives the result 2, which is the correct answer.

Quote:

---

Originally Posted by chhay

I don't know why it become like this, but when in typed in 3, it gives the result 2, which is the correct answer.

---

And do you also get the correct result for 4 or 5? It may be coincidence that 3 gives the correct result, despite the calculation itself being incorrect [and I agree that it most likely is].

--
Mats

Quote:

---

Originally Posted by chhay

I don't know why it become like this, but when in typed in 3, it gives the result 2, which is the correct answer.

---

In the words of Dijkstra: "Testing can only reveal the presence of bugs, not their absence". In other words, getting a correct answer for a single test doesn't mean that the whole program works.

QuantumPete

Quote:

---

I don't know why it become like this, but when in typed in 3, it gives the result 2, which is the correct answer.

---

With your updated code, an input of 3 gives a sum of 0.875. It is your original code that gives a sum of 2 for an input of 3. In any case, a single incorrect result is sufficient to prove that your implementation is incorrect.

I think it could be the data type problem.
Any idea about data type ?

Quote:

---

Originally Posted by chhay

I think it could be the data type problem.
Any idea about data type ?

---

When your numbers don't come out right, it's the algorithm. Not the data type. Don't blame C for getting incorrect results! ;)

QuantumPete

Quote:

---

I think it could be the data type problem.
Any idea about data type ?

---

I have written a version that uses unsigned long, but as it is the data types you chose can be used.

You are on the right track, but the main problem seems to be that you have not figured out how to correctly sum the factorials. Pretend that there is no divisor, and just compute the sum of the factorials. In other words, write a program to compute the sum of 1! + 2! + ... + N!. Actually, as I have pointed out, you only need to sum until (N-1)!.

Becasue when I follow the loop and calculate it on a paper it gives the correct result. Input 5 will get 17.

Quote:

---

Becasue when I follow the loop and calulate it on a paper it gives the correct result. Input 5 will get 17.

---

As I said, you are on the right track. In fact, you are very close... so it is likely that the algorithm you followed on paper differs slightly from the algorithm you implemented. This is a matter of the divisor being in the wrong place, which is why I suggested that you backtracked a little to get the sum of factorials part done correctly.

The sum of factorials part is correct. When i input 5, the result is 153, this sum of factorials is correct.

Quote:

---

The sum of factorials part is correct. When i input 5, the result is 153, this sum of factorials is correct.

---

That's great. So what was the code that you used?

Here the code:

Code:

---

for(x=1; x<=inputNumber; ++x)
      {
      fact=fact*x;
      sum+=fact;
      }

---

It find the sum of factorials. But if i add the dividen part like the following it doesn't give the correct answer.

Code:

---

for(x=1; x<=inputNumber; ++x)
      {
      fact=(fact*x)/(2*x);
      sum+=fact;
      }

---

Notice variable fact and x have different data type.

Quote:

---

But if i add the dividen part like the following it doesn't give the correct answer.

---

Now, look at where you added the divisor. By writing "fact=(fact*x)/(2*x)", you are saying that a factorial is computed with the divisor. But clearly, the factorial is not computed with the divisor. Rather, the sum is computed by adding the factorial divided by the divisor. Therefore, you should write:

Code:

---

fact=fact*x;
sum+=fact/(2*x);

---

Or more succinctly:

Code:

---

fact *= x;
sum += fact / (2 * x);

---

Thanks, laserlight.

I didn't keep my eyes on the second line in the loop. I'm so stupid.

It's working correctly at the moment. Thank you very much.:D You are the best. Now i can focus on my Maths exam on the next day.

Quote:

---

It's working correctly at the moment. Thank you very much. Now i can focus on my Maths exam on the next day.

---

When you have the time, you might want to look into using the (N-1)!/2 idea. It allows you to move the division out of the loop (so you only divide once) and reduces the number of iterations by 1.

Thanks, i will try using the (N-1)!/2 idea later.