Member Avatar for SammyHasibi

I have written a program with 2 functions which compute factorials & combinations. The functions work perfectly when called but I cannot insert a for loop at the end which sums up the combos. This part works (I have omitted the functions because they work when called for).

long factorial(int n);
long combination(int n, int k);
int main ()
{
    int n=0,k=0;
 
    while(n<=0)
    {
        printf("Enter value for n:");
        scanf("%i", &n);
        if(n<=0)
            printf("Please enter a positive integer value for n.\n");
    }
 
    while(k<=0||k>n)
    {
        printf("Enter value for k:");
        scanf("%i", &k);
        if(k<=0)
            printf("Please enter a positive integer value for k.\n");
        else if (k>n)
            printf("k must be less than or equal to n.\n");
    }
 
    long f = factorial(n);
    long c = combination(n,k);
 
    printf("n! = %i\n", f);
    printf("C(n,k) = %i\n", c);
    system("pause");
    return 0;
}

But when I insert this piece of code in the main body it goes haywire.

unsigned long sum=0;
int i;
for(i=0;i<=n;i++)
{
sum+=combination(n,i);
}
printf("sum=%un",sum);

What am I doing wrong? The sum of the combos should equal 2^n.
thanks!:eek:

  • 2 Contributors
  • 2 Replies
  • 108 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by SammyHasibi

Dani AI

Generated

Two likely causes for the “haywire” behavior are already hinted at in the thread: mismatched printf format specifiers and integer overflow from computing factorials. correctly called out the format-specifier problem — passing a long or unsigned long to printf with %i or a wrong specifier gives undefined behavior and can scramble later results. confirmed n=6,k=2 gives correct individual outputs, which shows the combination formula works for small inputs but the summation fails once types/overflow kick in.

Factorials blow up fast. On many common compilers (Windows/MSVC) long is 32-bit: 12! fits in 32-bit signed but 13! does not, so a factorial-based combination that computes factorial(n) will overflow long long before you get to the division. Two practical fixes: use a larger integer type (e.g. uint64_t/unsigned long long) and stop using full factorials to compute binomial coefficients.

A robust approach is the multiplicative method (multiply then divide at each step) which avoids computing full factorials and keeps intermediates smaller. Example (use <inttypes.h> for portable printing):

#include <inttypes.h>
#include <stdint.h>

uint64_t choose(unsigned n, unsigned k) {
    if (k > n) return 0;
    if (k > n - k) k = n - k;
    uint64_t r = 1;
    for (unsigned i = 1; i <= k; ++i) {
        r = r * (n - k + i) / i;
    }
    return r;
}

Use a 64-bit accumulator for the sum and print with the matching specifier, e.g. printf("sum = %" PRIu64 "\n", sum);. To check the identity sum_{i=0..n} C(n,i) = 2^n, compare with 1ULL << n only when n < 64 (shifting by the width or more is undefined). If you need exact results for much larger n, switch to a big-integer library (GMP) or arbitrary-precision routines.

Checklist: fix printf format-specifiers to match types, use a 64-bit type (uint64_t/unsigned long long) for sums, replace factorial-based combination with the multiplicative method, and test with small n before increasing.

Recommended Answers

All 2 Replies

Member Avatar for ~s.o.s~

Factorial values may easily go out of hand and overflow due to their exponential nature. So if you insert very high values of "n" the output might overflow.

Please paste your output along with the input you giving, along with the function combination def. (just in case).

Also dont use system("pause") to stop the screen. Use getchar() to achieve the same function.

Long values are printed using the format specifier %ld which i dont see in your program.

Nothing more can be said unless you post your combination function along with the input which you supplied to it.

Member Avatar for SammyHasibi

Thanks, s.o.s. I will change the specifier to ld and system("pause").
My 2 functions are below in code. I will change the specifiers on those as well to prevent overflow.
I place the value "6" for n & "2" for k & I get display
"n! = 720
C(n,k) = 15"
which are both correct.
I want "n" to be fixed & then I want the summation of the combo to go from 0 to n for k/i.
Thank you for reading.

long factorial(int n) 
{
    if (n<0)
        return MATH_FUNCTION_ERROR;
    else if(n==0)
        return 1;
    else
    {
        long result=1;
        int i;
        for(i=1;i<=n;i++)
            result*=i;
        return result;
    }
}
//returns (n!)/(k!*(n-k)!)
long combination(int n, int k) 
{
    if(n>=k)
        return factorial(n)/(factorial(k)*factorial(n-k));
    else
        return MATH_FUNCTION_ERROR;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.