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

Groups > comp.lang.forth > #43321

Re: Rosetta code binomial coefficient

Show all headers | View raw

Paul Rubin wrote:

> Bernd Paysan <bernd.paysan@gmx.de> writes:
>> The Forth solution gets pretty far into the binomial coefficients without
>> overflowing integers.  Your solution requires bignums for pretty small
>> coefficients.
> 
> True, maybe there's a simple way to improve that.  Hmm.
> 
>> choose n r = choose n-1 r + choose n-1 r+1
>> choose 0 r = r==0 ? 1 : 0
>> Lazy evaluation assumes that you keep what already has been computed.
> 
> Unfortunately that memoization only happens if there's a data object
> that stays accessible between calls.  Otherwise the above takes
> exponential time like a naive implementation.  There are memoization
> schemes in Haskell that do exploit lazy evaluation by keeping a data
> object around (typically an infinite tree that's computed lazily) that
> are clever and beautiful, but using one would have required loading a
> library and complicating the code somewhat.

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

cell 4 = [IF] 34 [ELSE] 67 [THEN] constant maxchoose#

: tri ( n -- n' )  dup 1+ * 2/ ;
maxchoose# 1+ tri cells buffer: pascal-triangle
1 pascal-triangle !
: tri' ( k n -- addr )   tri + cells pascal-triangle + ;
: out-of ( k n -- result )
    2dup u> IF  2drop 0  ELSE  tri' @  THEN ;
: out-of+ ( k n -- result )
    1- over 1- over out-of -rot out-of + ;
: fill-line ( n -- )
    dup 1+ 0 DO  I over 2dup out-of+ -rot tri' !  LOOP  drop ;
: fill-triangle ( n -- )
    dup 1+ 1 DO  I fill-line  LOOP  drop ;
maxchoose# fill-triangle

Parameter order reversed (fits more naturally to the problem), and therefor 
using OUT-OF as name.  Test on a 64 bit machine:

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.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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