On 11/8/2012 10:48 AM, Daniel Pitts wrote:

> On 11/8/12 9:10 AM, Eric Sosman wrote:

>> On 11/7/2012 11:53 PM, (E-Mail Removed) wrote:

>>> On Wednesday, November 7, 2012 8:28:19 PM UTC-6, (E-Mail Removed) wrote:

>>>> I would like to create a program that will do problems like

>>>> (xa+yb)^z. But I would need to do things like (5!/3!(5-3)!) How would

>>>> I get this done?

>>>

>>> rslt = 1;

>>> for(i = e; i > 0; i --)

>>> {

>>> rslt *= i;

>>> }

>>>

>>> I asked my brother and he helped me. e in this program is a user input

>>> so you may replace it as you see fit.

>>

>> A warning: If `e' is greater than 12, this calculation will

>> produce values too large for an `int':

>>

>> 479001600 = 12!

>> 2147483647 = Integer.MAX_VALUE

>> 6227020800 = 13!

>>

>> You can go somewhat higher by making `rslt' a `long':

>>

>> 2432902008176640000 = 20!

>> 9223372036854775807 = Long.MAX_VALUE

>> 51090942171709440000 = 21!

>>

>> ... but for anything over 20 even `long' will not suffice. You

>> should make sure `e' is 20 or smaller (12 or smaller for `int'),

>> or take a look at the BigInteger class.

>>

>

> Or, since you are dividing by factorials, you can factor them out to

> start with.

>

> 5!/3!(5-3)! =

> 5*4*3*2*1/(3*2*1)(2*1) =

> (5*4)/(2*1) * (3*2*1)/(3*2*1) =

> 5*4/2

>

> The general formula being n!/r!(n-r)!
One good way to arrange this is

n / 1 * (n-1) / 2 * (n-3) / 3 * ... * (n-r+1) / r

It's easy to see that all the divisions have remainder zero.

> I believe it is possible to keep the results in the range of integers,

> if the final result is.
Let's see: After "times (n-k+1) divided by k" we've calculated

C(n,k). The next product is C(n,k)*(n-k) before dividing by

(k+1) knocks it back down, so it looks like the product could be

somewhat larger than the eventual result, maybe too large. Hmm:

If we try to calculate C(30,15) this way, we'll get as far as

C(30,14) = 145422675

and then multiply by 16

C(30,14)*16 = 2326762800 > Integer.MAX_VALUE

and then divide by 15

C(30,14)*16/15 = C(30,15) = 155117520 < Integer.MAX_VALUE

So although we're much better off than by dividing factorials,

caution is still needed. (This is also a reason to begin by

setting `r = Math.min(r,n-r)': Not only does it make for fewer

iterations, but it helps avoid the central area where the numbers

get big. C(30,2) = C(30,2

mathematically, but 30/1*29/2 won't

get into trouble while 30/1*29/2*...*3/28 will.)

--

Eric Sosman

(E-Mail Removed)d