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  
 
 [ 2 post ] 

 Relevant Pages 

1. Puzzler: Binomial Coefficients

2. puzzler: binomial coefficients

3. Puzzler: Binomial Coefficients

4. Puzzler: Binomial Coefficients

5. Binomial coefficients

6. Puzzler : Binomial Coefficients

7. binomial coefficient (by hand)

8. binomial tree

9. LogoFE and binomial distribution

10. ? generating random uniform and binomial random deviates for BIG integers

11. Help to create a binomial distribution

12. Negative Binomial Approximations

 

 
Powered by phpBB® Forum Software