Re: C(n, k): binomial coefficient calculation

From: Chris McMahon (cm1975_at_swbell.net)
Date: 01/27/05 

Date: Thu, 27 Jan 2005 01:08:56 GMT

Dave Seaman wrote:

> On Wed, 26 Jan 2005 02:49:02 GMT, Chris McMahon wrote:
>
>>ok, so if i understand correctly:
>
>
> I think one of us doesn't.
>
>

that would be me, the literature major ;-) sorry...

>>C(7,3) mod 6 = ((7*6*5)/(3*2*1)) mod 6 = 5
>
>
>>can be expressed as:
>
>
>>((7/1) mod 6) * ((6/2) mod 6) * ((5/3) mod 6) = 1 * 3 * 5/3 = 5
>
>
> I don't even know what ((5/3) mod 6) means, since 5/3 is not an integer.
>
>

ok, i didn't know a number had to be an integer to be the object of a
mod function. my calculator doesn't have a hangup with it, but it can't
calculate 50!, either, so...here's what i meant:

(5/3) mod 6 = 1.66667 mod 6 = 1.66667

because i thought y mod x == y when y < x

or this:

(13/2) mod 6 = 6.5 mod 6 = 0.5

is mod the wrong term when the object isn't a whole number? or just in
this context? or am i just nuts?

> My suggestion was simply to compute C(n,k) first and then perform the
> reduction mod x, in which case the value of x makes very little
> difference in the difficulty of the computation. You do gain something
> in ease of computation by performing divisions earlier rather than later.
>
>

i see; you're right: in my case, x is fixed, and the only values i'm
looking for are between 0 and x. so anything that can be done to
minimize the labor considering x would be crucial.