computing the number of combinations

This is a discussion on computing the number of combinations within the C Programming forums, part of the General Programming Boards category; long long is 64 on mine. From my limits.h file: # define ULLONG_MAX 18446744073709551615ULL Hmm just realized that you can ...

  1. #31
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    long long is 64 on mine.

    From my limits.h file:
    # define ULLONG_MAX 18446744073709551615ULL
    Hmm just realized that you can have a space(s) between the # and the macro type.

    Yes C(70,35) is outside of the range, which is why I said it failed at that point.

  2. #32
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Quote Originally Posted by Thantos
    long long is 64 on mine.

    From my limits.h file:

    Hmm just realized that you can have a space(s) between the # and the macro type.

    Yes C(70,35) is outside of the range, which is why I said it failed at that point.
    Even C(68,34)=28453041475240576740
    is greater than 18446744073709551615 = ULLONG_MAX
    by a factor of 1.5

    The largest C(2n,n) that fits into a unsigned long long is C(66,33)
    Assuming usigned long long is 64 bits wide.

    The code below hopefully should calculate C(n,r) whenever the answer fits in unsigned long long, the reason for that it calculates C(n,r) by combing values which are less than C(n,r). If overflow occurs it should exit giving an error message.

    It gives the correct value for C(67,33)=14226520737620288370.
    The final value it can calculate is C(68,30)=17876288714431443296
    Note, that C(68,31)=21912870037044995008 is
    greater than 18446744073709551615 =ULLONG_MAX
    So, I guess, the following program calculates C(n,r) whenever answer fits in unsigned long long and gives an error otherwise.

    Code:
    #include <stdio.h>
    #include <limits.h>
    #include <stdlib.h>
    
    unsigned long long
    choose1(unsigned long n, unsigned long r) /*non recursive version*/
    {
    	unsigned long long comb=1,num,den;
    	if( 2*r>n) r=n-r;
    	if( (r<0) || (r>n) ) return 0;/*error*/
    	for(num=n-r,den=0;num<n;num++,den++)
    	{
    		unsigned long long q=comb/(den+1);
    		unsigned long long r=comb-q*(den+1);
    		if (   ( ULLONG_MAX/(num+1) < q) ||
    			   (ULLONG_MAX-((r*(num+1))/(den+1)) < (num+1)*q          )
    		   )
    		{
    		   fprintf(stderr,"Overflow detected...exiting\n");
    		   exit(EXIT_FAILURE);
    		}
    		comb = (num+1)*q+((r*(num+1))/(den+1));
    	}
    	return comb;
    }
    
    
    
    int
    main(void)
    {
      unsigned long n,r;
      printf("Give n\n");
      scanf("%lu",&n);
      printf("n=%lu\n",n);
      printf("Give r\n");
      scanf("%lu",&r);
      printf("C(%lu,%lu)=%llu\n",n,r,choose1(n,r));
      return 0;
    }
    The one who says it cannot be done should never interrupt the one who is doing it.

  3. #33
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    To explain what I have done is
    I calculate C(n+1,r+1) from C(n,r) using the formula

    C(n+1,r+1)= (n+1)*C(n,r)/(r+1)

    I break up C(n,r)=q(r+1)+rem
    where

    0<=rem<=r

    So, the above product can be written as the sum of two smaller quatities

    (n+1)*q+ ( (n+1)*rem/(r+1))

    the second term is less than n since rem < r+1 and note that the second term must be an integer

    So, the overflow can only come from (n+1)*q exceeding ULLONG_MAX or the sum exceeding ULLONG_MAX in either case C(n+1,r+1) exceeds ULLONG_MAX.
    Last edited by pinko_liberal; 06-05-2004 at 09:00 PM.
    The one who says it cannot be done should never interrupt the one who is doing it.

  4. #34
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    What if i want to calculate C(200,100) without using special libraries. Any ideas?

  5. #35
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >What if i want to calculate C(200,100) without using special libraries.
    You'll have to duplicate the functionality of those special libraries manually.
    My best code is written with the delete key.

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with this compiler error
    By Evangeline in forum C Programming
    Replies: 7
    Last Post: 04-05-2008, 10:27 AM
  2. Finding a number within a number
    By jeev2005 in forum C Programming
    Replies: 2
    Last Post: 01-10-2006, 08:57 PM
  3. Prime number program problem
    By Guti14 in forum C Programming
    Replies: 11
    Last Post: 08-06-2004, 05:25 AM
  4. parsing a number
    By juancardenas in forum C Programming
    Replies: 1
    Last Post: 02-19-2003, 01:10 PM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21