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

Groups > comp.lang.forth > #43289 > unrolled thread

Rosetta code binomial coefficient

Back to article view | Back to comp.lang.forth

Contents

  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

Page 1 of 2  [1] 2  Next page →

#43289 — Rosetta code binomial coefficient

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!

Krishna

[toc] | [next] | [standalone]

#43291

On Saturday, November 7, 2015 at 7:05:04 AM UTC+1, krishna...@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!

This algorithm must be quite common, in Forth or elsewhere --
I have it in Euler158.frt (2008) as 

: binomial ( n k -- d )
	LOCALS| k n |
	1  k 1+ 1 DO  n I - 1+  I */  LOOP ; 

In Euler113.frt (2008) it is defined using arbitrary precision:

-- result in binom
: binomial ( n k -- binom )
	LOCALS| k n |
	1 binom V!
	k 1+ 1 DO  binom  n I - 1+ VS*
		   binom  I VS/MOD DROP  
	     LOOP 
	binom ; PRIVATE

-marcel

[toc] | [prev] | [next] | [standalone]

#43296

mhx@iae.nl writes:

>On Saturday, November 7, 2015 at 7:05:04 AM UTC+1, krishna...@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!

>This algorithm must be quite common, in Forth or elsewhere --
>I have it in Euler158.frt (2008) as

>: binomial ( n k -- d )
>       LOCALS| k n |
>       1  k 1+ 1 DO  n I - 1+  I */  LOOP ;

I do some more preparation, and save a 1+.

 8 \ For N M return "N OVER M " (N/M)
 9 : CHS >R  R@ - 1 R> 1+ 1 ?DO   OVER I + * I / LOOP NIP ;
10 \ '(./.) ALIAS CHS

Of course I do so many Euler problems that I have it in my library.
I overlooked the possibility to use */, which extends the
range of usable numbers considerably. Damn.

>In Euler113.frt (2008) it is defined using arbitrary precision:

>-- result in binom
>: binomial ( n k -- binom )
>       LOCALS| k n |
>       1 binom V!
>       k 1+ 1 DO  binom  n I - 1+ VS*
>                  binom  I VS/MOD DROP
>            LOOP
>       binom ; PRIVATE

With k single precision.

>-marcel
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#43292

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

[toc] | [prev] | [next] | [standalone]

#43298

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.

[toc] | [prev] | [next] | [standalone]

#43547

WJ wrote:

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

Using recursion:

def choose n,k
  k<1?1:(n-k+1)*choose(n,k-1)/k
end

[toc] | [prev] | [next] | [standalone]

#43293

krishna.myneni@ccreweb.org writes:
> Compare its compactness of implementation with those in
> other languages. 

choose n r = product [n-r+1 .. n] `div` product [1 .. r]

looks more natural to me (that's Haskell fwiw).

[toc] | [prev] | [next] | [standalone]

#43299

Paul Rubin wrote:

> krishna.myneni@ccreweb.org writes:
>> Compare its compactness of implementation with those in
>> other languages.
> 
> choose n r = product [n-r+1 .. n] `div` product [1 .. r]
> 
> looks more natural to me (that's Haskell fwiw).

The Forth solution gets pretty far into the binomial coefficients without 
overflowing integers.  Your solution requires bignums for pretty small 
coefficients.

With the concept of lazy evaluation, you could do much better in terms of 
computation speed, as the building rule of Pascal's triangle only requires 
the + operation.

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.

I.e. just compute all of Pascal's triangle instead of trying to generate 
every binomial coefficient on the fly; most of the numbers stay small, and 
the operation is very simple, just +.

-- 
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/

[toc] | [prev] | [next] | [standalone]

#43302

On Saturday, November 7, 2015 at 8:11:47 AM UTC-6, Bernd Paysan wrote:
> Paul Rubin wrote:
> 
> > krishna.myneni@ccreweb.org writes:
> >> Compare its compactness of implementation with those in
> >> other languages.
> > 
> > choose n r = product [n-r+1 .. n] `div` product [1 .. r]
> > 
> > looks more natural to me (that's Haskell fwiw).
> 
> The Forth solution gets pretty far into the binomial coefficients without 
> overflowing integers.  Your solution requires bignums for pretty small 
> coefficients.
> 

The Forth solution permits up to n = 33, for all valid k, for 32-bit cell size. The growth of the factorials, thought, don't extend this range very far even for 64-bit cell size. I haven't determined where it fails, but it is for n < 100 on 64 bits.

Also, it would be interesting to compare speed of evaluation in some of the higher level languages such as Haskell, with that of the Forth version.

> With the concept of lazy evaluation, you could do much better in terms of 
> computation speed, as the building rule of Pascal's triangle only requires 
> the + operation.
> 
> 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.
> 
> I.e. just compute all of Pascal's triangle instead of trying to generate 
> every binomial coefficient on the fly; most of the numbers stay small, and 
> the operation is very simple, just +.
>

Yes. It's not clear to me that the entire tree needs to be computed either, up to the needed row and column.
 
> -- 
> 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/


Krishna

[toc] | [prev] | [next] | [standalone]

#43304

On Saturday, November 7, 2015 at 8:11:47 AM UTC-6, Bernd Paysan wrote:
...
> With the concept of lazy evaluation, you could do much better in terms of 
> computation speed, as the building rule of Pascal's triangle only requires 
> the + operation.
> 
> choose n r = choose n-1 r + choose n-1 r+1
> choose 0 r = r==0 ? 1 : 0
> 

What is "lazy evaluation"? Isn't the above just recursion, as is implemented in the Julia version on Rosetta code?

function binom(n,k)
  n >= k || return 0              #short circuit base cases
  n == 1 && return 1
  k == 0 && return 1
 
  binom(n-1,k-1) + binom (n-1,k)  #recursive call
end


Krishna

[toc] | [prev] | [next] | [standalone]

#43307

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.

[toc] | [prev] | [next] | [standalone]

#43321

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/

[toc] | [prev] | [next] | [standalone]

#43338

On Saturday, November 7, 2015 at 1:20:54 PM UTC-6, Bernd Paysan wrote:
> 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/


Nice. I'm adding this to my toolbox. In fact, I think it would make a good module for the FSL, perhaps named pascalt.x. Some additional words I would
add are shown below.

Krishna

============

\ Validate the triangle: each row must sum to 2^row
: tri-linesum ( n -- sum )
    0 over 1+ 0 do over i swap tri' @ + loop nip ;

: validate-triangle ( -- )
    cell 4 = if 32 else 64 then
    0 do i tri-linesum 1 i lshift
	 <> ABORT" Invalid Pascal's Triangle!"
    loop ;

validate-triangle

\ Display the triangle up to row n.
: tri. ( n -- )
    0 ?do I 1+ 0 do I J tri' @ . 2 spaces loop cr loop ;

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

#43367

Paul Rubin wrote:

> 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.

Ruby:

def triangle n
  (1..n).reduce([1]){|row| [0,*row,0].each_cons(2).map{|a,b| a+b}}
end

triangle 10
    ==>[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]

triangle(49)[6]
    ==>13983816

triangle(200)[100]
    ==>90548514656103281165404177077484163874504589675413336841320

These all run pretty much instantly.

-- 
The report card by the American Society of Civil Engineers showed the national
infrastructure a single grade above failure, a step from declining to the point
where everyday things simply stop working the way people expect them to. ---
washingtonpost.com/local/trafficandcommuting/us-infrastructure-gets-d-in-annual-report/2013/03/19/c48cb010-900b-11e2-9cfd-36d6c9b5d7ad_story.html

[toc] | [prev] | [next] | [standalone]

#43778

WJ wrote:

> Paul Rubin wrote:
> 
> > 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.
> 
> Ruby:
> 
> def triangle n
>   (1..n).reduce([1]){|row| [0,*row,0].each_cons(2).map{|a,b| a+b}}
> end
> 
> triangle 10
>     ==>[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]
> 
> triangle(49)[6]
>     ==>13983816
> 
> triangle(200)[100]
>     ==>90548514656103281165404177077484163874504589675413336841320
> 
> These all run pretty much instantly.

In Ocaml, ints don't automatically transition into bigints.
So we have to use the Num module.
The addition operator is "+/".

#load "nums.cma" ;;
open Num ;;

let triangle n =
  let rec newrow = function [n] -> [n] | m::n::ns -> m+/n :: newrow (n::ns)
  and go row = function
      0 -> row
    | n -> go (newrow (Int 0::row)) (n-1)
  in go [Int 1] n ;;

# triangle 10;;
- : Num.num list =
[Int 1; Int 10; Int 45; Int 120; Int 210; Int 252; Int 210; Int 120;
 Int 45; Int 10; Int 1]

# string_of_num (List.nth (triangle 200) 100);;
- : string = "90548514656103281165404177077484163874504589675413336841320"


For timing, compile this file:


(*  compile with
ocamlopt nums.cmxa Pascal_triangle.ml
*)

open Num ;;

let triangle n =
  let rec newrow = function [n] -> [n] | m::n::ns -> m+/n :: newrow (n::ns)
  and go row = function
      0 -> row
    | n -> go (newrow (Int 0::row)) (n-1)
  in go [Int 1] n ;;

print_endline ( string_of_num (List.nth (triangle 200) 100));;


let start = Sys.time() in
  for i = 0 to 99 do
    ignore (List.nth (triangle 200) 100)
  done;
  Printf.printf "%.3f seconds\n" (Sys.time() -. start);;


----------

0.343 seconds on an old winXP laptop.


-- 
The report card by the American Society of Civil Engineers showed the national
infrastructure a single grade above failure, a step from declining to the point
where everyday things simply stop working the way people expect them to. ---
washingtonpost.com/local/trafficandcommuting/us-infrastructure-gets-d-in-annual-report/2013/03/19/c48cb010-900b-11e2-9cfd-36d6c9b5d7ad_story.html

[toc] | [prev] | [next] | [standalone]

#43779

"WJ" <w_a_x_man@yahoo.com> writes:
> let start = Sys.time() in
>   for i = 0 to 99 do
>     ignore (List.nth (triangle 200) 100)
>   done;
>   Printf.printf "%.3f seconds\n" (Sys.time() -. start);;

This stuff should go in comp.lang.functional.  It would be much less
annoying there.

[toc] | [prev] | [next] | [standalone]

#43374

Paul Rubin wrote:

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

Yes, that looks elegant.

> 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.

Can you benchmark that vs. the 200 multiplications which generate really big 
intermediate results and one division for these really big numbers?  These 
are 10k additions on pretty small bignums (200*100/2), supposed you do only 
that query (once done, it's precomputed, and much cheaper).

With bignum multiplications each going with O(n²), I suppose, the 10k 
additions are actually faster.

-- 
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/

[toc] | [prev] | [next] | [standalone]

#43381

Bernd Paysan <bernd.paysan@gmx.de> writes:

>Paul Rubin wrote:

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

>Yes, that looks elegant.

>> 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.

>Can you benchmark that vs. the 200 multiplications which generate really big
>intermediate results and one division for these really big numbers?  These
>are 10k additions on pretty small bignums (200*100/2), supposed you do only
>that query (once done, it's precomputed, and much cheaper).

>With bignum multiplications each going with O(n²), I suppose, the 10k
>additions are actually faster.

In euler problems you often need the binomials modulo a prime.
Although it is possible to divide modulo a prime, the addition
method is much faster, sometimes to the point that a solution
is unfeasible without it. Often one needs all the intermediate
results anyway.

>--
>Bernd Paysan

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#43399

Bernd Paysan <bernd.paysan@gmx.de> writes:
> Can you benchmark that vs. the 200 multiplications

I'll try to do this soon.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.forth

csiph-web