[algogeeks] Re: Calculating C(n.r)
Very nice solution. Don On Wednesday, April 9, 2014 12:55:43 AM UTC-4, Dave wrote: What you want to do is automate the process of cancelling common factors that you would do if you were calculating nCr by hand. Fill an array a[] with the numerator terms, n, n-1, n-2, ..., n-r+1, and a second array b[] with the denominator terms, 1, 2, 3, ..., r. Inside a double loop with j and i going from 0 to r-1, compute the gcd of a[i] and b[j]. Divide both a[i] and b[j] by the gcd. When the loops finish, you will have cancelled the common factors from all of the terms, and in fact, all of the denominator terms will be 1. In a final loop, compute the product of the numerator terms. There are some obvious optimizations. Dave On Tuesday, April 8, 2014 1:06:47 PM UTC-5, kumar raja wrote: Hi all, I know the way to calculate value of C(n,r) using pascals identity. But i have a different requirement. C(n,r) = n (n-1) (n-2) ... (n-r+1) / r! Suppose the numerator is such that it cant fit into existing data type. So i remember there is a way to strike off the common factors in numerator and denominator then calculate the result of it. But the logic is not striking to me. Googled but could not find much. So please share the clever way to calculate the above value w/o actually computing the factorials and then making division. My actual requirement is to calculate the value of (n1+n2++nk)! / (n1!.n2!.n3!.nk!) . Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Calculating C(n.r)
Thanks for the idea. On 9 April 2014 10:25, Dave dave_and_da...@juno.com wrote: What you want to do is automate the process of cancelling common factors that you would do if you were calculating nCr by hand. Fill an array a[] with the numerator terms, n, n-1, n-2, ..., n-r+1, and a second array b[] with the denominator terms, 1, 2, 3, ..., r. Inside a double loop with j and i going from 0 to r-1, compute the gcd of a[i] and b[j]. Divide both a[i] and b[j] by the gcd. When the loops finish, you will have cancelled the common factors from all of the terms, and in fact, all of the denominator terms will be 1. In a final loop, compute the product of the numerator terms. There are some obvious optimizations. Dave On Tuesday, April 8, 2014 1:06:47 PM UTC-5, kumar raja wrote: Hi all, I know the way to calculate value of C(n,r) using pascals identity. But i have a different requirement. C(n,r) = n (n-1) (n-2) ... (n-r+1) / r! Suppose the numerator is such that it cant fit into existing data type. So i remember there is a way to strike off the common factors in numerator and denominator then calculate the result of it. But the logic is not striking to me. Googled but could not find much. So please share the clever way to calculate the above value w/o actually computing the factorials and then making division. My actual requirement is to calculate the value of (n1+n2++nk)! / (n1!.n2!.n3!.nk!) . Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Calculating C(n.r)
Use the fact that a*b*c*d = exp(log a + log b + log c + log d) double sum = 0.0; double x; for(x = n-r+1.0; x = n; x += 1.0) sum += log(x); for(x = 2; x = r; x += 1.0) sum -= log(x); result = exp(sum); Don On Tuesday, April 8, 2014 2:06:47 PM UTC-4, kumar raja wrote: Hi all, I know the way to calculate value of C(n,r) using pascals identity. But i have a different requirement. C(n,r) = n (n-1) (n-2) ... (n-r+1) / r! Suppose the numerator is such that it cant fit into existing data type. So i remember there is a way to strike off the common factors in numerator and denominator then calculate the result of it. But the logic is not striking to me. Googled but could not find much. So please share the clever way to calculate the above value w/o actually computing the factorials and then making division. My actual requirement is to calculate the value of (n1+n2++nk)! / (n1!.n2!.n3!.nk!) . Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Calculating C(n.r)
Note that my example is for C(n,r), but you can use the same method for your second formula. Just add up the logs of whatever you multiply in the numerator and subtract the logs of the factors of the denominator. Then the result is exp of the resulting sum. Don On Tuesday, April 8, 2014 2:15:06 PM UTC-4, Don wrote: Use the fact that a*b*c*d = exp(log a + log b + log c + log d) double sum = 0.0; double x; for(x = n-r+1.0; x = n; x += 1.0) sum += log(x); for(x = 2; x = r; x += 1.0) sum -= log(x); result = exp(sum); Don On Tuesday, April 8, 2014 2:06:47 PM UTC-4, kumar raja wrote: Hi all, I know the way to calculate value of C(n,r) using pascals identity. But i have a different requirement. C(n,r) = n (n-1) (n-2) ... (n-r+1) / r! Suppose the numerator is such that it cant fit into existing data type. So i remember there is a way to strike off the common factors in numerator and denominator then calculate the result of it. But the logic is not striking to me. Googled but could not find much. So please share the clever way to calculate the above value w/o actually computing the factorials and then making division. My actual requirement is to calculate the value of (n1+n2++nk)! / (n1!.n2!.n3!.nk!) . Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Calculating C(n.r)
What you want to do is automate the process of cancelling common factors that you would do if you were calculating nCr by hand. Fill an array a[] with the numerator terms, n, n-1, n-2, ..., n-r+1, and a second array b[] with the denominator terms, 1, 2, 3, ..., r. Inside a double loop with j and i going from 0 to r-1, compute the gcd of a[i] and b[j]. Divide both a[i] and b[j] by the gcd. When the loops finish, you will have cancelled the common factors from all of the terms, and in fact, all of the denominator terms will be 1. In a final loop, compute the product of the numerator terms. There are some obvious optimizations. Dave On Tuesday, April 8, 2014 1:06:47 PM UTC-5, kumar raja wrote: Hi all, I know the way to calculate value of C(n,r) using pascals identity. But i have a different requirement. C(n,r) = n (n-1) (n-2) ... (n-r+1) / r! Suppose the numerator is such that it cant fit into existing data type. So i remember there is a way to strike off the common factors in numerator and denominator then calculate the result of it. But the logic is not striking to me. Googled but could not find much. So please share the clever way to calculate the above value w/o actually computing the factorials and then making division. My actual requirement is to calculate the value of (n1+n2++nk)! / (n1!.n2!.n3!.nk!) . Regards, Kumar Raja. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
