Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #43340

Re: Rosetta code binomial coefficient

From Paul Rubin <no.email@nospam.invalid>
Newsgroups comp.lang.forth
Subject Re: Rosetta code binomial coefficient
Date 2015-11-07 19:50 -0800
Organization A noiseless patient Spider
Message-ID <87twoxup2e.fsf@nightsong.com> (permalink)
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>

Show all headers | View raw

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.

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-06 22:05 -0800
  Re: Rosetta code binomial coefficient mhx@iae.nl - 2015-11-06 23:24 -0800
    Re: Rosetta code binomial coefficient Albert van der Horst <albert@spenarnc.xs4all.nl> - 2015-11-07 10:58 +0000
  Re: Rosetta code binomial coefficient "WJ" <w_a_x_man@yahoo.com> - 2015-11-07 08:14 +0000
    Re: Rosetta code binomial coefficient "WJ" <w_a_x_man@yahoo.com> - 2015-11-07 14:05 +0000
      Re: Rosetta code binomial coefficient "WJ" <w_a_x_man@yahoo.com> - 2015-11-15 06:18 +0000
  Re: Rosetta code binomial coefficient Paul Rubin <no.email@nospam.invalid> - 2015-11-07 00:23 -0800
    Re: Rosetta code binomial coefficient Bernd Paysan <bernd.paysan@gmx.de> - 2015-11-07 15:11 +0100
      Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-07 07:49 -0800
      Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-07 08:10 -0800
      Re: Rosetta code binomial coefficient Paul Rubin <no.email@nospam.invalid> - 2015-11-07 08:50 -0800
        Re: Rosetta code binomial coefficient Bernd Paysan <bernd.paysan@gmx.de> - 2015-11-07 20:20 +0100
          Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-07 17:45 -0800
          Re: Rosetta code binomial coefficient Paul Rubin <no.email@nospam.invalid> - 2015-11-07 19:50 -0800
            Re: Rosetta code binomial coefficient "WJ" <w_a_x_man@yahoo.com> - 2015-11-08 15:35 +0000
              Re: Rosetta code binomial coefficient "WJ" <w_a_x_man@yahoo.com> - 2015-11-25 20:29 +0000
                Re: Rosetta code binomial coefficient Paul Rubin <no.email@nospam.invalid> - 2015-11-25 12:43 -0800
            Re: Rosetta code binomial coefficient Bernd Paysan <bernd.paysan@gmx.de> - 2015-11-08 18:51 +0100
              Re: Rosetta code binomial coefficient Albert van der Horst <albert@spenarnc.xs4all.nl> - 2015-11-08 18:51 +0000
              Re: Rosetta code binomial coefficient Paul Rubin <no.email@nospam.invalid> - 2015-11-08 19:55 -0800
  Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-08 07:03 -0800
  Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-09 06:57 -0800
    Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-10 03:49 -0800
      Re: Rosetta code binomial coefficient Ron Aaron <rambamist@gmail.com> - 2015-11-10 14:01 +0200
        Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-10 19:13 -0800
          Re: Rosetta code binomial coefficient Ron Aaron <rambamist@gmail.com> - 2015-11-11 07:38 +0200
  Re: Rosetta code binomial coefficient glidedog@gmail.com - 2015-11-14 05:26 -0800
    Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-14 06:19 -0800
      Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-14 06:22 -0800
      Re: Rosetta code binomial coefficient glidedog@gmail.com - 2015-11-14 08:16 -0800
        Re: Rosetta code binomial coefficient krishna.myneni@ccreweb.org - 2015-11-14 11:16 -0800
  Re: Rosetta code binomial coefficient "WJ" <w_a_x_man@yahoo.com> - 2016-06-28 00:02 +0000

csiph-web