Puzzler: Binomial Coefficients 
Author Message
 Puzzler: Binomial Coefficients

Quote:

> Although the binomial coefficient 10!21 is an integer, the
> straightforward calculation of !21 divided by the product of !10 and !11
> would only approximate an integer, because !21 is not represented to
> full precision. In the first implementation of APL, Larry Breed provided
> precise integers by judicious cancellations.

> The problem posed is to write a corresponding precise calculation of the
> binomial coefficients in some dialect.

For non-negative integers, A!B is (!B){divide}(!A){times}!B-A.  With the
example 10!21, this yields:

        1 2 3 4 5 ... 19 20 21
        ----------------------
        1 2 ... 10  1 2 ... 11

The 1..11 in the denominator cancels 1..11 in the numerator, leaving us
with 12..21 on top and 1..10 on the bottom.  (And we can drop the 1 in
the denominator.)  Vectors N and D representing the terms in the
numerator and denominator can be computed as:

        N{<-}(A{max}B-A){drop}{iota}B
        D{<-}1{drop}{iota}A{min}B-A

        12 13 14 15 16 17 18 19 20 21        N
        -----------------------------
             2 3 4 5 6 7 8 9 10              D

(#IO is assumed to be 1 here.)  Although no more terms can be cancelled,
a reduction of some terms is possible.  For example, the 20 in N and the
10 in D can be reduced to 2 and 1, and likewise for 18:9, 16:8, 14:7,
etc., and the 15:3 can be reduced to 5:1, yielding:

        2 13 2 3 2 17 2 19 2 21
        -----------------------
           2 3 4 1 1 1 1 1 1

After this, more cancellation is possible (and the 1s can be dropped),
giving:

        13 2 2 17 2 19 2 21
        -------------------
                 4

Finally, 2:4 can be reduced to 1:2 and then a 2:2 term cancelled.

   For automatic processing, one way of doing the reductions is by
replacing each term with its prime factors.  The problem is then
simplified to one of matching up and cancelling identical terms.  The
ALLFACTORS function (listed below) takes a vector and returns the prime
factors for all the numbers in the vector:

      + F{<-}ALLFACTORS N
2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 5 5 7 7 13 17 19

      + G{<-}ALLFACTORS D
2 2 2 2 2 2 2 2 3 3 3 3 5 5 7

Corresponding items can be cancelled by dualling subtraction with a
mapping to frequency space.


2 3 5 7 13 17 19



8 4 2 1 0 0 0


8 4 2 1 0 0 0


2 2 3 7 13 17 19



The result of A!B is given by ({times}/X){divide}{times}/Y.

   After coding this up and experimenting a bit, I noticed that all the
denominator terms were cancelled in every case; Y was always empty.
Thinking about this, I realized that this must be true in general.  A!B
returns an integer result for integer arguments, and X and Y are lists
of primes with no numbers in common.  If Y wasn't empty, the ratio of
the times reductions couldn't possibly be an integer, so Y must always
be empty.  Incorporating this observation in the algorithm yielded the
following program:

     {del} Z{<-}A BINOM B;D;F;G;H;N;P;T;U



[4]    P{<-}PRIMESTO {floor}B*.5

[6]    G{<-}P ALLFACTORS D


[9]    U{<-}+/H{jot}.=G

     {del}

On line [4], the list of distinct primes is precalculated and passed to
ALLFACTORS to save a bit of time.  The subroutines are listed below.
(Yes, I know factorization and nub are primitives in J!)

   And then, while browsing in Knuth, I came across an amazing algorithm
for factoring !N:

     {del} Z{<-}P FACTORNF N;M


[3]    {->}(2=#NC'P')/L1

[5]   L1:M{<-}{times}\{transpose}(({floor}2{log}N),{rho}P){rho}P
[6]    Z{<-}(+/{floor}N{divide}M)/P
     {del}

Using this little gem, the binomial program can be written as:

     {del} Z{<-}A BINOM2 B;E;F;G;H;T;U;V

[2]    P{<-}PRIMESTO B

[4]    F{<-}P FACTORNF A
[5]    G{<-}P FACTORNF B-A


[8]    U{<-}H FRCOUNT F
[9]    V{<-}H FRCOUNT G

     {del}

I replaced the frequency-counting idioms (e.g., +/H{jot}.=F) with a more
efficient subroutine (FRCOUNT) because the outer product is rather slow
when you're working with, say 5000 BINOM2 6000.  (Which is around
1.58e1172.  You can't do the final {times}/, but you can look at the
terms and add up the logarithms.)  The nifty FACTORNF algorithm doesn't
save as much time as I thought it would because you have to compute more
primes to use it.  For arguments like 5000 6000, the cost of finding the
extra primes just about equals the savings from more efficient
factoring.

   Nice problem, Ken!  I'm curious about what Larry Breed's algorithm
was.  Anyone care to elaborate?

                                                Jim

Note:  Software is available to automatically un-transliterate and
extract the programs in this message.  For information, point your Web
browser at:

        http://www.*-*-*.com/ ~jimw/a2ardme.html
and
        http://www.*-*-*.com/ ~jimw

Here are the subroutines:

     {del} Z{<-}PRIMESTO N;B;P;#IO

[2]    Z{<-}{iota}#IO{<-}0
[3]    N{<-}N+1
[4]    B{<-}N{take}1 1
[5]   L1:P{<-}B{iota}0
[6]    {->}(P=N)/0
[7]    Z{<-}Z,P
[8]    B{<-}B{or}N{rho}P{take}1
[9]    {->}L1
     {del}

PRIMESTO is cute (it finds primes without using any arithmetic
operations, using the Sieve of Eratosthenes), but it's not very fast.  A
more efficient algorithm would help BINOM2, which needs lots of primes.

     {del} Z{<-}P ALLFACTORS A;B;I;J;N



[4]   L1:Z{<-}0{rho}A{<-},A
[5]    I{<-}1 & N{<-}{rho}P









[15]   N{<-}{neg}1+(P{<=}{floor}(0{max}{max}/A)*.5){iota}0 {+





     {del}

     {del} Z{<-}ONUB A

[2]    A{<-},A
[3]    A{<-}A[{gradeup}A]
[4]    Z{<-}(1,1{drop}A{/=}{neg}1{rotate}A)/A
     {del}

     {del} Z{<-}D FRCOUNT V;B;F;I




[5]    Z{<-}({rho}D){rho}0

     {del}



Sun, 30 Aug 1998 03:00:00 GMT  
 Puzzler: Binomial Coefficients


Jim Weigang writes on Wednesday, March 13:

Quote:
> ...  I'm curious about what Larry Breed's algorithm
> was.  Anyone care to elaborate?

We think it likely that this algorithm would still be in the
interpreter code for x!y in any APL implementation based
on APL\360, such as APL2 or SHARP APL.  Perhaps someone
with access to these interpreter sources can comment.

My guess is that it is unlikely for Breed to have used factoring.



Mon, 31 Aug 1998 03:00:00 GMT  
 Puzzler: Binomial Coefficients
A prime-finder seems like a generally useful tool to have available, so
I wrote an assembler version for APL*PLUS II/386 and +III/Windows.  The
technique is based on Algorithm P in section 1.3.2 of Knuth's "The Art
of Computer Programming", vol 1.

     {del} Z{<-}PRIMESTO N;T

[2]    {->}(T{<-}''{rho}(1,N,#STPTR'Z T')#CALL PRIMESTO{delta}OBJ){drop}0
[3]    #ERROR(3 5 7 8{iota}T){pick}'LENGTH ERROR' 'RANK ERROR' 'VALUE ERROR'{+
   +} 'WS FULL' 'DOMAIN ERROR'
     {del}

{del}.    PRIMESTO{delta}OBJ{<-}1345730611 858915563 {neg}1991316349 {neg}19{+
+}93202588 {neg}1992940476 1715086428 35933321 609519974 {neg}957576422 {neg{+
+}}972945595 {neg}972939451 {neg}973076923 1711283781 1711282360 1711293833 {+
+}1712866697 3163591 28861952 15224832 1476395008 {neg}1267171282 74799184 8{+
+}2561229 1378112767 50873799 {neg}2097152000 2114139773 7179574 178278 5947{+
+}2 777519104 1351186560 {neg}855345832 {neg}16454712 1917985876 611093357 7{+
+}5333682 {neg}2141752062 1963001213 142443353 {neg}1957727742 1160460869 13{+
+}2406 {neg}388956160 {neg}1995946749 1166616645 474334752 491111938 5246663{+
+}69 409832705 243814 59472 777519104 {neg}13518720 1481703423 {neg}92608807{+
+}5 1425999083 376590884 841247883 28515819 62066923 95620331 129173739 1459{+
+}49931 {neg}1070399253 1441383306 {neg}1962934271 2105746557 192807734 {neg{+
+}}1962117749 {neg}201586611 {neg}954471515 519 71812864 3 84428743 {neg}956{+
+}301312 472645 1837957120 79193600 15224832 1476395008 {neg}1128759250 1358{+
+}954494 {neg}855345832 {neg}16454712 {neg}1957551020 {neg}1959648148 278011{+
+}57 {neg}1992294027 {neg}768392635 955 {neg}2081163520 74776826 37897603 69{+
+}9 {neg}1949158656 1077953093 953 {neg}2081294592 57999610 {neg}1962753149 {+
+}2106278477 {neg}406761720 612172546 {neg}947712533 51349764 116621771 9898{+
+}55744 478100045 2238 611648256 {neg}1047801293 {neg}92064009 1004565504 {n{+
+}eg}2083029498 {neg}320142138 {neg}1054573269 {neg}2092498193 2130983549 21{+
+}05757455 142541370 981304143 1325498113 33834438 17122758 17253830 {neg}19{+
+}95407991 1837959293 62416384 15224832 1476395008 {neg}189235154 1358954493{+
+} {neg}855345832 {neg}16454712 257041492 {neg}76414 611093503 611683122 {ne{+
+}g}1962115701 {neg}201586611 409832869 309350 59472 777519104 {neg}37898112{+
+} 1481703423 {neg}926088075 1425999083 1821069860 {neg}1070910940 {neg}1018{+
+}248061 960314 105807

{del}:   PRIMESTO{delta}OBJ[#IO]{<-}(1345730611 2000042035)['3/'{iota}{+
+}#SYSID[#IO+12]]

This runs pretty fast.  On my 486/66, it takes 0.0105 secs to find
primes up to 5000.  (Compared with 2.66 secs for the APL sieve version,
making it about 250 times faster.)

   The assembler code is able to examine a range of numbers for primes,
utilizing the prime list computed in a previous run.  Here's a function
that uses this feature to find the first N primes:

     {del} Z{<-}PRIMESN N;F;P;Q;S;T

[2]    P{<-}{iota}F{<-}0


   +}{times}N)+4{times}Q



[8]   L1:S{<-}''{rho}(F,(F+Q-1),#STPTR'P T')#CALL PRIMESTO{delta}OBJ



[12]   {->}L1

[14]   {->}0
[15]  L3:#ERROR(3 5 7 8{iota}S){pick}'LENGTH ERROR' 'RANK ERROR' 'VALUE {+
   +}ERROR' 'WS FULL' 'DOMAIN ERROR'
     {del}

It took 395 seconds to find the first million primes.  (If you call 2
the first prime, the millionth is 15,485,863.)  Of course, this is
nothing compared with Roger Hui's feat of finding the first 10 _billion_
(1e10) primes, but that took 20 hours on 60-70 workstations.  (See
Vector Vol. 10, No. 4, April 1994, pp 110-113.)

                                                Jim

P.S.  I believe I erred in my previous posting by saying that J has a
built-in factorization primitive.  I can't find it listed in the manual.
Also, the APL sieve function doesn't seem to be terribly inefficient.  I
haven't found a faster technique in APL, including a parallelized
version of Knuth's algorithm.



Mon, 31 Aug 1998 03:00:00 GMT  
 Puzzler: Binomial Coefficients

Quote:
> P.S.  I believe I erred in my previous posting by saying that J has a
> built-in factorization primitive.  I can't find it listed in the manual.

No, the first sentence is wrong.  But the q: factorization function
doesn't appear to be in my manual or on-line help, just listed in
status.txt as "q:  implemented" in version 2.06.

   J also has a function that finds the n-th prime, p: .  And it's quite
a fast implementation, too.  Setting i=.i.669 and finding primes to 5000
with p:i took just 0.0035 secs (with J 2.06 on Win3.1), which is 3 times
faster than my assembler routine.  Finding the first million primes was
also several times faster, but this task caused almost continuous disk
activity, and repeated timings ranged from 92 secs to 160 secs.

   I think Roger must have learned something from finding billions and
billions of primes that weekend at Morgan Stanley.

                                                Jim



Mon, 31 Aug 1998 03:00:00 GMT  
 Puzzler: Binomial Coefficients

Quote:
> Although the binomial coefficient 10!21 is an integer,
> the straightforward calculation of !21 divided by the
> product of !10 and !11 would only approximate an integer,
> because !21 is not represented to full precision. In the
> first implementation of APL, Larry Breed provided
> precise integers by judicious cancellations.
> The problem posed is to write a corresponding precise
> calculation of the binomial coefficients in some dialect.

Jim Weigang gives a solution to this problem, but I found it
too programmatic, and not mathematical enough.

Assume a function "PVEC", which takes an integer, and returns
its representation as a product of powers of primes, only the
exponents would be shown.

      PVEC 2
1
      PVEC 3
0 1
      PVEC 4
2
      PVEC 11
0 0 0 0 1

Where PRIMES {is} 2 3 5 7 11 13...

    N = (PVEC N)+.*({shape}PVEC N){take}PRIMES
from which we can devine a PVECinv.

to slip into J, multiplication becomes addition under PVEC,
division becomes subtraction.

    N!K
thus becomes
    (!N){div}(!N-K){x}(!K)

    PVECinv +/[1]{disclose}(PVEC{each}({iota}N)),-(PVEC
{each}{iota}N-K),(PVEC{each}{iota}K)

    or, by defining a PVECfact: +/[1]{disclose}{iota}{omega}

    PVECinv +/[1]{disclose}(PVECfact N),-(PVECfact N-K),PVECfact K

We can accomplish the result, while preserving the math.

--
|\/| Randy A MacDonald       |"You just ASK them?"

     BSc(Math) UNBF '83      | APL: If you can say it, it's done.

                             | Also http://www.godin.com/godin/
------------------------------------------------<-NTP>----{ gnat }-



Mon, 31 Aug 1998 03:00:00 GMT  
 Puzzler: Binomial Coefficients


Ken Iverson writes on Monday, March 11:

Quote:
> Although the binomial coefficient 10!21 is an integer,
> the straightforward calculation of !21 divided by the
> product of !10 and !11 would only approximate an integer,
> because !21 is not represented to full precision. In the
> first implementation of APL, Larry Breed provided
> precise integers by judicious cancellations.
> The problem posed is to write a corresponding precise
> calculation of the binomial coefficients in some dialect.

Jim Weigang writes on Wednesday, March 13:

Quote:
> For non-negative integers, A!B is (!B){divide}(!A){times}!B-A.  With the
> example 10!21, this yields:

>         1 2 3 4 5 ... 19 20 21
>         ----------------------
>         1 2 ... 10  1 2 ... 11
> ...
>    For automatic processing, one way of doing the reductions is by
> replacing each term with its prime factors.  The problem is then
> simplified to one of matching up and cancelling identical terms.  The
> ALLFACTORS function (listed below) takes a vector and returns the prime
> factors for all the numbers in the vector:
> ...
>      {del} Z{<-}A BINOM B;D;F;G;H;N;P;T;U



> [4]    P{<-}PRIMESTO {floor}B*.5

> [6]    G{<-}P ALLFACTORS D


> [9]    U{<-}+/H{jot}.=G

>      {del}
> On line [4], the list of distinct primes is precalculated and passed to
> ALLFACTORS to save a bit of time.  The subroutines are listed below.
> (Yes, I know factorization and nub are primitives in J!) ...

I had essentially the same algorithm in my J solution:

bc =: 4 : 0
 n=. x.<.y.-x.
 p=. ; q:&.> y.-i.n
 q=. ; q:&.> >:i.n
 e=. (p,q) +//. (p,&#q)#1 _1
 */ e#~.p,q
)

 n=. x.<.y.-x.
Minimum of x. and y.-x.; (x.!y.)=(y.-x.)!y.

 p=. ; q:&.> y.-i.n
 q=. ; q:&.> >:i.n
n!y. is (*/y-i.n) % !n or (*/y-i.n)%*/>:i.n.  The prime factors of
a product are the catenated prime factors of the elements of
the product; therefore, p are the prime factors of the numerator,
and q the prime factors of the denominator.

 e=. (p,q) +//. (p,&#q)#1 _1
For cancellation, the dyad -. is not adequate because a prime
can occur more than once.  Instead:  Using as keys (p,q), the list
of primes (in both the numerator and the denominator), +/ is applied
to a corresponding vector of 1's (for numerator) and _1's
(for denominator), producing a vector of exponents corresponding
to the nub of the keys.

 */ e#~.p,q
Finally, the binomial cofficients are computed by raising the
distinct primes to the exponents, here by copying and then
multiplication, or alternatively by */(~.p,q)^e.  

Tacitly:





exp =: , +//. ,&# # 1 _1"_


   10 bct 21
352716

   10 ind 21
0 1 2 3 4 5 6 7 8 9
   ] p=.10 num 21
3 7 2 2 5 19 2 3 3 17 2 2 2 2 3 5 2 7 13 2 2 3
   ] q=.10 den 21
2 3 2 2 5 2 3 7 2 2 2 3 3 2 5

   p exp q
1 1 2 0 1 1 1
   p ,&# q
22 15
   (p,&#q) # 1 _1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 _1 _1 _1 _1  ...
   (p,q) +//. (p,&#q) # 1 _1
1 1 2 0 1 1 1
   (p,q)  ]/. (p,&#q) # 1 _1    NB. using identity fn in key
1 1  1  1 1 _1 _1 _1 _1 0  0  0  0  0  0  0  0  0
1 1 _1  0 0  0  0  0  0 0  0  0  0  0  0  0  0  0
1 1  1  1 1  1  1  1  1 1 _1 _1 _1 _1 _1 _1 _1 _1
1 1 _1 _1 0  0  0  0  0 0  0  0  0  0  0  0  0  0
1 0  0  0 0  0  0  0  0 0  0  0  0  0  0  0  0  0
1 0  0  0 0  0  0  0  0 0  0  0  0  0  0  0  0  0
1 0  0  0 0  0  0  0  0 0  0  0  0  0  0  0  0  0

   p nub q
3 7 2 5 19 17 13
   (p exp q) # (p nub q)
3 7 2 2 19 17 13
   */ (p exp q) # (p nub q)
352716

Thus, as Jim Weigang noted, the primitives nub ~. and factor q:
are indeed useful.  Moreover, the "key" adverb f/. is also useful
for computing the differences in the frequencies (the exponents).

For large arguments, neither the APL nor the J solution is
efficient, because factoring large integers is a very hard problem.  
For example, if the right argument is moderately large, as in 5!_1+2^53,
a solution involving factoring would grind for quite some time.  
In such cases, the method described at the beginning of Jim's msg
is better, because remaindering is much easier than factoring:

- Show quoted text -

Quote:
>         12 13 14 15 16 17 18 19 20 21        N
>         -----------------------------
>              2 3 4 5 6 7 8 9 10              D

> (#IO is assumed to be 1 here.)  Although no more terms can be cancelled,
> a reduction of some terms is possible.  For example, the 20 in N and the
> 10 in D can be reduced to 2 and 1, and likewise for 18:9, 16:8, 14:7,
> etc., and the 15:3 can be reduced to 5:1, yielding:

>         2 13 2 3 2 17 2 19 2 21
>         -----------------------
>            2 3 4 1 1 1 1 1 1

> After this, more cancellation is possible (and the 1s can be dropped),
> giving:

>         13 2 2 17 2 19 2 21
>         -------------------
>                  4

bcc =: 4 : 0
 n=. x.<.y.-x.
 p=. y.-i.n
 q=. >:i.n
 cancel p;q
)

cancel =: 3 : 0
 m=.#p=. \:~>0{y.
 n=.#q=. \:~>1{y.
 i=. _1
 while. n>i=.>:i do.
  d=. i{q
  if. m>j=.(d|p) i. 0 do.
   p=. p j}~ (j{p) % d
   q=. q i}~ 1  
  end.
 end.
 p ;&(-.&1) q
)

   ] pq=.10 bcc 21
+-------------------+-+
|19 2 17 2 3 14 13 2|4|
+-------------------+-+
   */ >0{pq
1.41086e6
   */ >1{pq
4
   (*/>0{pq) % */>1{pq
352716
   %/&:(*/&>) pq
352716

   #&> t=. 5000 bcc 6000
975 340
   #&> t=. cancel |. t
262 429
   #&> t=. cancel |. t
421 58
   #&> t=. cancel |. t
58 412
   #&> t=. cancel |. t
412 50
   #&> t=. cancel |. t
50 412
   #&> t=. cancel |. t
412 50


   $x
2
   #&>x
412 50
   t -: x
1

   10{.&>t
5987 5981 5953 5939 5927 5923 5903 5897 5881 5879
 681  669  604  548  369  333  243  225  213  160
   _10{.&>t
 6  6  6  6  6  6  6  6  6  6
21 20 16 16 16 16 15 15 15 10

(This last example on 5000!6000 is only to show that the method
can fail to completely cancel the denominator.  For a number
as small as 6000, factoring would be faster.)

Quote:
> I replaced the frequency-counting idioms (e.g., +/H{jot}.=F) with a more
> efficient subroutine (FRCOUNT) because the outer product is rather slow
> when you're working with, say 5000 BINOM2 6000.  (Which is around
> 1.58e1172.  You can't do the final {times}/, but you can look at the
> terms and add up the logarithms.)  ...

5000!6000 is 15774075422263882095...4382657744.


Mon, 31 Aug 1998 03:00:00 GMT  
 Puzzler: Binomial Coefficients
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 --

Jesse



Mon, 31 Aug 1998 03:00:00 GMT  
 Puzzler: Binomial Coefficients

Quote:

> Jim Weigang gives a solution to this problem, but I found it
> too programmatic, and not mathematical enough.

> Assume a function "PVEC", which takes an integer, and returns
> its representation as a product of powers of primes, only the
> exponents would be shown.
[...]
> multiplication becomes addition under PVEC, division becomes
> subtraction.

Nice solution!  The math could be highlighted even more if the prime
power vectors weren't of variable length.  Although this sacrifices
generality, you could have functions PFN (powers from number) and NFP
(number from powers) use a global variable PRIMES and return a fixed-
length vector of prime exponents.  PRIMES would be set up beforehand to
contain all the necessary primes.  Defining PFNF N as PFN !N would allow
you to state the original formula

            (!B){divide}(!A){times}!B-A
as:
            NFP (PFNF B)-(PFNF A)+PFNF B-A

For example:

      PRIMES{<-}PRIMESTO 13

      N{<-}115615500
      + P{<-}PFN N

      NFP P

      PFNF 12

      NFP PFNF 12
479001600
      !12
479001600

      10 BINOM6 21
352716
      10!21
352716

The new functions are listed below.  See my previous messages for
any missing subroutines.  Enhancing these functions to handle higher
rank arguments is left as an exercise for the reader!

                                                Jim

     {del} Z{<-}A BINOM6 B;PRIMES

[2]    PRIMES{<-}PRIMESTO B
[3]    Z{<-}NFP (PFNF B)-(PFNF A)+PFNF B-A
     {del}

     {del} P{<-}PFNF N;M

[2]    M{<-}{times}\{transpose}(({floor}2{log}1{max}N),{rho}PRIMES){rho}PRIMES
[3]    P{<-}+/{floor}N{divide}M
     {del}

PFNF here uses Knuth's algorithm for factoring !N.  (See the FACTORNF
function in my previous message, and note a recent bug fix: 1{max} needs
inserted in FACTORNF before taking the log.)  However, given a fast
factoring routine (like q: in J), I think it would be more efficient to
factor each element of {iota}N separately, because this would require
primes only up to Sqrt(N) instead of N.  (Time for another Fastfn...)

     {del} N{<-}NFP P

[2]    N{<-}{times}/P/PRIMES
     {del}

     {del} P{<-}PFN N

[2]    P{<-}PRIMES FRCOUNT ALLFACTORS N
     {del}



Tue, 01 Sep 1998 03:00:00 GMT  
 Puzzler: Binomial Coefficients
NNTP-Posting-Host: 199.117.27.22

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 --

{rem} NextPascalRow
   {del}r{is}npr x
[1] r{is}(0,x)+(x,0)
   {del}

   npr 1
1 1
   npr 1 1
1 2 1
   npr 1 2 1
1 3 3 1
   npr 1 3 3 1
1 4 6 4 1
...

  {del}r{is}pr n
[1] r{is}1
[2] {goto}(n=1)/0
[3] r{is}npr pr n-1
  {del}

or in J or if APL had tacit definition, and the power conjunction:

 pr n <-> npr{power}n  1

--
|\/| Randy A MacDonald       |"You just ASK them?"

     BSc(Math) UNBF '83      | APL: If you can say it, it's done.

                             | Also http://www.godin.com/godin/
------------------------------------------------<-NTP>----{ gnat }-



Wed, 02 Sep 1998 03:00:00 GMT  
 
 [ 9 post ] 

 Relevant Pages 

1. Puzzler: Binomial Coefficients

2. puzzler: binomial coefficients

3. Puzzler: Binomial Coefficients

4. Puzzler : Binomial Coefficients

5. Binomial Coefficients

6. 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