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

Groups > comp.lang.forth > #43778

Re: Rosetta code binomial coefficient

From "WJ" <w_a_x_man@yahoo.com>
Newsgroups comp.lang.forth
Subject Re: Rosetta code binomial coefficient
Date 2015-11-25 20:29 +0000
Organization A noiseless patient Spider
Message-ID <n355nb$dfl$1@dont-email.me> (permalink)
References (2 earlier) <n1l0mq$qli$1@dont-email.me> <87io5dwy6m.fsf@nightsong.com> <n1liqd$ev$1@dont-email.me> <87twoxup2e.fsf@nightsong.com> <n1nq3q$2f0$1@dont-email.me>

Show all headers | View raw

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

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