Binomial Coefficients
Author Message
Binomial Coefficients

Jesse Deutsch writes on Thursday, March 14:

Quote:
> Couldn't binomial coefficients be found
> by some iterative scheme running down Pascal's
> triangle?  Or would the memory requirements
> be unmanageble?  Or is this what was going
> on in the previous posts of unobfuscated APL?

> Trying to avoid multiplications --

I'd previous thought of (and rejected) this scheme.  The problem
is not space but time: With this method, n!m requires m iterations;
for 2!1e9, the cancellation method would do (1e9%2)*1e9-1, whereas
the Pascal's triangle method would do one billion iterations.

On the other hand, a J phrase to generate binomial coefficients
this way, coined by Ken Iverson in 1989-1990 (early in the
history of J), "blew me away":

(0&, + ,&0) ^: 1 ,1
1 1
(0&, + ,&0) ^: 2 ,1
1 2 1
(0&, + ,&0) ^: 3 ,1
1 3 3 1
(0&, + ,&0) ^: 9 ,1
1 9 36 84 126 126 84 36 9 1
(0&, + ,&0) ^: 0 ,1
1

(0&, + ,&0) ^: (i.10) ,1
1 0  0  0   0   0  0  0 0 0
1 1  0  0   0   0  0  0 0 0
1 2  1  0   0   0  0  0 0 0
1 3  3  1   0   0  0  0 0 0
1 4  6  4   1   0  0  0 0 0
1 5 10 10   5   1  0  0 0 0
1 6 15 20  15   6  1  0 0 0
1 7 21 35  35  21  7  1 0 0
1 8 28 56  70  56 28  8 1 0
1 9 36 84 126 126 84 36 9 1

The phrase lives on in the book "J Phrases", m55 in Chapter 2 or
m26 in Chapter 8, located by looking for "binomial coefficients"
or "Pascal's triangle" in the index.

Tue, 01 Sep 1998 03:00:00 GMT
Binomial Coefficients

Keith Smillie writes on Thursday, March 14:

Quote:
>     A simple, but very inefficient, method of calculating binomial
> coefficients that avoids problems with factorials of very large
> numbers may be illustrated by the following example:
>      6 C 4
>      (!6) % (!4) * (!2)
>      (6*5*4*3*2*1) % (4*3*2*1) *(2*1)
>      (6*5*4*3*2*1) % (4*3*2*1*2*1)
>      %/ 6 4 5 3 4 2 3 1 2 2 1 1    NB. Alternate items of left %
>                                    NB.  left and right arg.
>                                    NB.  and find alternating
>                                    NB.  product.
>      15
>      This calculation is given by the verb

> where

> alternates the items of its left and right arguments, and

> gives positive integers. As an example, 20.0": 10000 C 3
> is 166616670000  .

Actually, this approach can be quite efficient, and quite accurate
using double precision floating point arithmetic.  The J interpreter
uses something like it:

num =: ]  - ind            NB. numerator
den =: 1: + ind            NB. denominator

bc  =: [: %/ num alt den

4 bc 6
15
4 num 6
6 5
4 den 6
1 2
4 (num alt den) 6
6 1 5 2
%/ 4 (num alt den) 6
15

3 bc 10000
1.66617e11
20 ": 3 bc 10000
166616670000

3 num 10000
10000 9999 9998
3 den 10000
1 2 3
3 (num alt den) 10000
10000 1 9999 2 9998 3
%/ 3 (num alt den) 10000
1.66617e11

From the same starting point, a method that stays entirely within
the domain of integers can be devised:  Two products are calculated
of the numerator and the denominator, with the partial products
reduced at each step by their GCDs.  Thus:

pair =: num ,. den

4 ! 10
210

4 pair 10
10 1
9 2
8 3
7 4

8 3 multr 7 4
14 3
9 2 multr 14 3
21 1
10 1 multr 21 1
210 1

10 1 multr 9 2 multr 8 3 multr 7 4
210 1
multr/ 4 pair 10
210 1

4 bcm 10
210

The suffix scan f/\. can be used to advantage to produce the partial
results along the way.  Thus:

4 pair 10           multr /\. 4 pair 10
10 1                210 1
9 2                 21 1
8 3                 14 3
7 4                  7 4

13 pair 20          multr /\. 13 pair 20
20 1                77520 1
19 2                 3876 1
18 3                  408 1
17 4                   68 1
16 5                   16 1
15 6                    5 1
14 7                   14 7

Finally, on large arguments, the method is more efficient than one
using factoring, because GCD is much easier than factoring.

Tue, 01 Sep 1998 03:00:00 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages