Path: csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Paul Rubin <no.email@nospam.invalid>
Newsgroups: comp.lang.forth
Subject: Re: Rosetta code binomial coefficient
Date: Sat, 07 Nov 2015 19:50:49 -0800
Organization: A noiseless patient Spider
Lines: 32
Message-ID: <87twoxup2e.fsf@nightsong.com>
References: <4fa62f0c-dab1-4bc0-bbda-8c250a6955d4@googlegroups.com> <87mvuqw73j.fsf@nightsong.com> <n1l0mq$qli$1@dont-email.me> <87io5dwy6m.fsf@nightsong.com> <n1liqd$ev$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="1a9f5856d25720e42c135b990c70bebb"; logging-data="32604"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX184HOcXmc5hqONYBKiuCiul"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
Cancel-Lock: sha1:PQjVnLcvGxdAmt6+IgmS2Ggwj4k= sha1:mIn5/gwke1bDZNGjf5vBQTDPOvI=
Xref: csiph.com comp.lang.forth:43340

Bernd Paysan <bernd.paysan@gmx.de> writes:
> Here's a Forth program that creates Pascal's triangle up to the maximum 
> value for unsigned cells (4/8 bytes per cell for desktop Forths): ...
> 6 49 out-of . 13983816
> Looks good.  If you need a lot of binomial coefficients within the range of 
> integers, this approach should be the fastest.

Nice.  Pascal's triangle works ok with Haskell lazy evaluation too:

    triangle = rows [1] where
      rows lastRow = lastRow : rows (shiftAdd lastRow)
      shiftAdd row = zipWith (+) (0 : row) (row ++ [0])

This gives an infinite list where each row is made by putting 0's around
the last row, then adding that result to itself shifted by 1.  So for
example the 10th row is:

    *Main> triangle !! 10
    [1,10,45,120,210,252,210,120,45,10,1]

The 6th element of the 49th row:

    *Main> triangle !! 49 !! 6
    13983816

I guess it's all bignums even for the low entries, but the 100th element
of the 200th row is:

    *Main> triangle !! 200 !! 100
    90548514656103281165404177077484163874504589675413336841320

These all run pretty much instantly.