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

Groups > comp.lang.forth > #43307

Re: Rosetta code binomial coefficient

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 08:50:57 -0800
Organization A noiseless patient Spider
Lines 18
Message-ID <87io5dwy6m.fsf@nightsong.com> (permalink)
References <4fa62f0c-dab1-4bc0-bbda-8c250a6955d4@googlegroups.com> <87mvuqw73j.fsf@nightsong.com> <n1l0mq$qli$1@dont-email.me>
Mime-Version 1.0
Content-Type text/plain
Injection-Info mx02.eternal-september.org; posting-host="1a9f5856d25720e42c135b990c70bebb"; logging-data="26845"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/XfQSIl1KevxbjVmgKkGNK"
User-Agent Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
Cancel-Lock sha1:LfswWP3y9X+b+rhTTkozhKsFI8k= sha1:7qo+Ci3hSwb0PNy2+0t9ThQibd0=
Xref csiph.com comp.lang.forth:43307

Show key headers only | View raw

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.

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