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

Groups > comp.lang.forth > #43298

Re: Rosetta code binomial coefficient

Show all headers | View raw

WJ wrote:

> krishna.myneni@ccreweb.org wrote:
> 
> > The Forth entry on Rosetta Code for
> > computing the binomial coefficient is
> > beautiful. Compare its compactness of
> > implementation with those in other
> > languages. This is a very nice code example
> > in Forth. Although it meets the requirements
> > of the entry, single integers for 32 bit
> > word size quickly lead to failure, e.g. "60
> > 30 choose". The implementation is better
> > suited for 64-bit word size.
> > 
> > : choose ( n k -- nCk ) 1 swap 0 ?do over i - i 1+ */ loop nip ;
> > 
> > Good job, whoever submitted this to Rosetta Code!
> 
> Since only stack operations are performed, it is very difficult
> to discern the algorithm.
> 
> Ruby:
> 
> def choose n,k
>   (0...k).reduce(1){|t,i| t*(n-i)/(i+1)}
> end
> 
> choose(8,3)
>     ==>56
> choose(22,9)
>     ==>497420
> choose(60,30)
>     ==>118264581564861424
> choose(99,50)
>     ==>50445672272782096667406248628
> choose(200,100)
>     ==>90548514656103281165404177077484163874504589675413336841320

Shorter:

def choose n,k
  (1..k).reduce(1){|t,i| t*(n-i+1)/i}
end

Explanation:

1..k creates a range of integers (k is the last).

"reduce" is sometimes called "fold" in Lispy languages;
in Ruby, it's also known as "inject".

It iterates over a sequence of items, building up a result
as it goes.

In the code above, the value we are generating is called "t"
(for temporary).  Its initial value is set to 1.
(If we did not specify an initial value, the first item of
the sequence would be used.)

This part
  {|t,i| t*(n-i+1)/i}
is an anonymouse code-block (lambda or "quotation").
It is called for each item in the sequence, receiving two
values.  The first is the value that we have built so far,
and the second is the current item of the sequence.
  t*(n-i+1)/i
represents the new value that we are generating.

When "reduce" finishes, it yields the value that we have
built up.

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